从BFS到Dijkstra算法
视频地址：https://www.bilibili.com/video/av25829980?t=520
1，代码
相对正月老师的存图方法，我用的是 链式前向星 方法，存图（如果不懂，并觉的我讲的还不错的话，可以看一下：https://www.cnblogs.com/asdfknjhu/p/12505173.html ）
由于要用链式前向星，我把 ABC 一律换为 123，但图总体是没变的
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<queue> using namespace std; #define N 100 typedef struct Edge { int to; int w; int pre; }eg; eg e[N]; typedef struct node // 队列里要放的应该是 点的 id 和 distance ，而不是一条边 { int id; int dis; node(int a, int b) :id(a), dis(b) {} friend bool operator <(const node &a,const node &b) // < 的重载 { return a.dis > b.dis; } }st; int tot = 0, last[N], vis[N]; int dist[N], p[N]; // 记录距离和前一个点的 id void add(int from, int to, int w) { tot++; e[tot].to = to; e[tot].w = w; e[tot].pre = last[from]; last[from] = tot; } void Dijkstra(int start) { priority_queue <st>q; // 小于号的重载是对于优先队列 来说 q.push(st(start, 0)); // 起点为 1 dist[start] = 0, p[start] = -1; while (q.size()) { st vertex = q.top(); q.pop(); vis[vertex.id] = 1; // 出栈的时候标记 for (int i = last[vertex.id]; ~i; i = e[i].pre) //遍历这个点相邻的边 { st next = { e[i].to,e[i].w + vertex.dis }; if (vis[next.id] == 0) //如果下一个点还没有走过 { if (dist[next.id] > next.dis) //如果新来的点距离更近 更新 距离和前一个点的 id, { p[next.id] = vertex.id; dist[next.id] = next.dis; q.push(next); } } } } } void show(int end) { if (p[end] != -1) show(p[end]); printf("%d ", end); } int main(void) { int n; scanf("%d", &n); memset(last, -1, sizeof(last)); memset(vis, 0, sizeof(vis)); memset(dist, 0x3f, sizeof(dist)); tot = 0; while (n--) { int from, to, w; // 起点 终点 权值 scanf("%d%d%d", &from, &to, &w); add(from, to, w);
if (to != from) add(to, from, w); // 无向图 } Dijkstra(1); // 起点 printf("路线："); show(6); //终点 printf(" 距离：%d ", dist[6]); system("pause"); return 0; } /* 测试数据 8 1 2 5 1 3 1 2 3 2 2 4 1 3 4 4 3 5 8 4 5 3 4 6 6 */
2，优先队列 的排序是按照 从起点到各点的距离大小
由于 A->C->B 小于 A->B，所以 到达 B 点 应用 A->C->B 这条路径
所以 在优先队列后面插一个 （B，3），就可以让原来 （B，5）无效了，因为（B，3）会插队在（B，5）前面
3，ditance 和 p 数组
ditance：记录从起点到达各点的最短路径的 距离
p：记录到达当前点的最短路径上的前一个点的 编号
4，有点贪心的意思，
看点 E，因为一直走的是最短的路，所以 ACBDE，这条点较多的较短路径
才能赶上 ACE这条点较少较长的路径，避免 (E ,8) 点出队之前，(E,7) 点进入队列，成功插队，
所以，需要标记一个点是否 visted, 是在这个点出栈的时候，而不是入栈的时候
5，每次 while 之后 队列里的元素
一个小细节： ②权值5 这一点比 ④权值5 先进的队列，最后是 ④ 排在 ② 前面
其实，，在画图时才发现，因为有dist数组，所以有无 vis数组 并不影响结果，只是可以减少循环次数
========== ========= ======= ======= ====== ===== ==== === == =
木玉成约 叶迷
青楼斜影疏，良人如初顾。
纤手如玉脂，淡妆胜罗敷。
引君入香堂，言词论今古。
君心城切切，妾意情楚楚。
盟定三生约，共谱月下曲。
岂料鸳鸯棒，分飞相思苦。
纵有抱柱信，不能容世俗。
君子世无双，陌上人如玉。
不能同世生，但求同归土。