最短路径--Dijkstra算法详解

keyipatience:个人主页作者简介C/C后端开发学习者专栏传送门《c》《linux》《c高阶数据结构》《c数据结构与算法》⭐️patience is key in lifeDijkstra邻接矩阵版(O(n^2)核心工作前提无负权维护三组数组dist[]源点到每个顶点当前预估最短距离vis[]标记顶点是否已经确定最短路径ppath[]记录每个点的前驱顶点用于还原路径重复 n 轮顶点总数 ① 在还没确定最短路径的顶点中选出预估距离dist最小的顶点 u ② 标记vis[u]true锁定 u 的最短距离无负权边保证不会有更短路径 ③松弛用 u 去更新它所有邻接点。如果源→u→邻点比之前记录的距离更短就更新距离同时记录前驱。最终得到源点到全部顶点的最短距离借助前驱数组反向回溯就能得到完整路径。一句话速记每次挑离源点最近的未确定点锁定它再拿它去更新邻居的预估最短距离。一步步代码实现void Dijkstra(const V src, vectorW dist, vectorint ppath) {函数作用传入源点 src输出 dist 最短距离数组、ppath 前驱数组第 1 段获取顶点、初始化变量int n _vertexs.size(); int srci GetVertexIndex(src); dist.resize(n, MAX_W); ppath.resize(n, -1); vectorboolvis(n, false); dist[srci] W();n _vertexs.size()拿到图里顶点总个数srci GetVertexIndex(src)把源点名字比如 A转成数组下标dist.resize(n, MAX_W)dist 数组全部初始成无穷大表示暂时不可达ppath.resize(n, -1)前驱数组全部 - 1代表暂时没有前驱vectorboolvis(n, false)标记数组false 该点最短路径还没确定dist[srci] W()源点到自己距离为 0第 2 段外层主循环循环 n 次每次确定 1 个点for (int i 0; i n; i) {一共有 n 个顶点最多需要选 n 次每一轮选出 1 个点确定它的最短路径子段 A贪心查找找未访问中 dist 最小的点 uW min MAX_W; int u 0; for (int j 0; j n; j) { if (!vis[j] dist[j] min) { min dist[j]; u j; } }min用来记录当前最小距离u保存找到的顶点下标j 遍历全部顶点条件!vis[j]这个点还没确定最短路径并且 dist [j] 比当前 min 更小满足就更新 min记录 u作用挑出当前离源点最近还没确定的点 uvis[u] true;核心标记 uu 的最短路径确定后续不再改动子段 B松弛操作用 u 更新其他点for (int k 0; k n; k) { if (_matrix[u][k] ! MAX_W !vis[k] dist[u] _matrix[u][k] dist[k]) { dist[k] dist[u] _matrix[u][k]; ppath[k] u; } } } }k 遍历所有顶点_matrix[u][k] ! MAX_Wu 到 k 存在边!vis[k]k 还没有确定最短路径dist[u] _matrix[u][k] dist[k]走「源→u→k」比原来记录的更近三个条件全满足更新 dist [k] 为更短的距离ppath[k]u记录 k 的前驱是 u后面用来回溯路径配套路径打印函数分段讲解void PrintShortPath(const V src, const vectorW dist, const vectorint ppath) { int srci GetVertexIndex(src); int n _vertexs.size();拿到源点下标顶点总数for (int i 0; i n; i) { vectorintpath; int parent i;遍历每一个终点 ipath 存路径parent 从终点 i 开始反向找while (parent!srci) { path.push_back(parent); parent ppath[parent]; } path.push_back(srci);循环不断找 parent 的前驱直到追到源点出循环后把源点放进 path。此时 path 是逆序终点 → ... → 源点reverse(path.begin(), path.end());反转数组变成正向源点 → ... → 终点for (auto e : path) { cout _vertexs[e] -; } cout dist[i] endl; } }循环输出路径上每个顶点最后输出这条路径的最短距离。整体代码void Dijkstra(const V src, vectorW dist, vectorint ppath) { int n _vertexs.size(); int srci GetVertexIndex(src); dist.resize(n, MAX_W);//dist[]的含义目前我们已经探索过的路径里起点 s 到这个点的最短距离 ppath.resize(n, -1); // 初始化ppath数组全部为-1 vectorboolvis(n, false); dist[srci] W();//源点到自己的 为0 //ppath[srci] srci; //一共有n个顶点要走n次 for (int i 0; i n; i) { W min MAX_W; int u 0; for (int j 0; j n; j) { if (!vis[j] dist[j] min) { min dist[j]; u j; } } //贪心为什么不选10要选5为什么可以把vis[y]true锁死确定一定是最短的 vis[u] true; //松弛 for (int k 0; k n; k) { //如果srci-u u-k 比 srci-k更短 则进行更新 if (_matrix[u][k] ! MAX_W !vis[k] dist[u] _matrix[u][k] dist[k]) { //!vis[k]k 已经确定最短路径的话就不用再松弛它了 //一旦 vis [k]truek 的最短路径就确定死了再也不会变短。 //!!! dist[k] dist[u] _matrix[u][k]; ppath[k] u; } } } } void PrinrtShotPath(const V src, const vectorW dist, const vectorint ppath) { int srci GetVertexIndex(src); int n _vertexs.size(); for (int i 0; i n; i) { vectorintpath; int parent i;//下面要打印dist[i]所以不要动i while (parent!srci) { path.push_back(parent); parent ppath[parent]; } path.push_back(srci); reverse(path.begin(), path.end()); for (auto e : path) { cout _vertexs[e] -; } cout dist[i] endl; } }测试例子void TestGraphDijkstra() { const char* str syztx; Graphchar, int, INT_MAX, true g(str, strlen(str)); g.AddEdge(s, t, 10); g.AddEdge(s, y, 5); g.AddEdge(y, t, 3); g.AddEdge(y, x, 9); g.AddEdge(y, z, 2); g.AddEdge(z, s, 7); g.AddEdge(z, x, 6); g.AddEdge(t, y, 2); g.AddEdge(t, x, 1); g.AddEdge(x, z, 4); vectorint dist; vectorint parentPath; g.Dijkstra(s, dist, parentPath); g.PrinrtShotPath(s, dist, parentPath); }结果贪心为什么不选10要选5即为什么选dist最小的并且就能直接锁定5就是最短的为什么不能有负权值贪心规则在还没锁定的点就是vis[i]为假里面选 dist 最小的那个第一轮的时候W min MAX_W; size_t u 0; //遍历j0~4 j0S[j]falsedist[0]0 MAX_W min0u0 j1SfalsedistMAX_W不小于0跳过 j2SfalsedistMAX_W跳过 j3SfalsedistMAX_W跳过 j4SfalsedistMAX_W跳过s的dist0min0选s源点第二轮的时候W min MAX_W; size_t u0; j0: Strue跳过 j1: Sfalsedist[1]5 MAX_W → min5, u1 j2: distMAX_W不更新 j3: dist10105不成立 j4: distMAX_Wy 的 dist 5t 的 dist 10 5 10所以选 y不选 t。为什么要这样先看这张图第二轮的状态起点 s 已经被涂黑放进集合 SS [s]true dist 数组s0锁定y5 s→y边权 5t10s→t边权 10z∞x∞剩下没有涂黑Sfalse的顶点y、t、z、x 它们的预估 disty5t10z 无穷x 无穷假设存在一条路径 s→…→v → y总长度 5也就是有一条更短的路到 y1.这条路径在到达 y 之前最后经过的点叫 vv 一定是不在 S 里面没涂黑的点。因为s→…→v → y是一条更短的路如果v在S里面已经就用来松弛更新dist[v]了。2.这条假设路径总长度 dist [v] w (v→y) 因为边权 w ≥ 0所以 dist [v] w (v→y) ≥ dist [v]我们假设整条路径长度 5代入上面不等式 5 dist [v] w (v→y) ≥ dist [v] 可以推出 dist [v] 5矛盾当前所有未涂黑的点 y (5)、t (10)、z (∞)、x (∞) 没有任何一个未涂黑的 vdist [v] 是小于 5 的。 我们假设的这个 v 根本不存在也就不存在这条比 5 还短的路径为什么负权边的时候上面这套推理直接失效、核心w 可以是负数dist[v]w(v→y) ≥ dist[v]这个不等式不再成立如果 w (v→y) 是负数dist [v] w (v→y) dist [v]举个例子 假设 v就是 tdist [t]10有一条边 t→y权值-7那么dist[t] (-7) 10-73 5也就是 哪怕所有未锁定点的 dist 全都 ≥5依然可以配上一条负边得到一条更短的到 y 的路径。 那我们就不能保证 dist [y]5 是真实最短路径不能提前锁定 y。所以这个算法必须保证权值不能有负数对比 t 为什么不能锁t 现在dist10。 候选集合里还有 yy 的dist5比 10 更小。 y 还没被锁定y 到 t 有边。 后面把 y 选中、加入 S 之后就会松弛dist[y]w(y→t)算出来 8能把 t 的距离从 10 更新成更小的 8。所以现在还不能锁定宏观整体理解前提所有边权 ≥ 0无负权边一旦选出 u注意是未访问点里 dist 最小的不可能后面再找到一条更短路径到 u因为后面任何其他点到 u 的路径都要经过其他点而其他点的 dist 本身就≥dist [u]dist[u]就是未访问点最小的再加正数边权只会更大。 → 所以 u 的最短距离永久确定打上 vis 标记不再处理。如果有负权边这个结论直接失效Dijkstra 不能用。