五种基础的最短路算法总结与证明

朴素版dijkstra : 进行 n-1 次松弛操作, 每次都用当前 dist 最小的点更新, 这样就能保证经过了 n-1 次松弛之后, 起点到其他点的距离一定是最短的 (On^2)

堆优化版dijkstra : 每次都堆顶取出元素(确保了它是当前 dist 最小的点), 然后遍历该点的所有邻边, 当所有的点都进行了松弛操作过后, 一定能够得到最短距离 (Omlogn, 因为每个点遍历的是周围的邻边)

bellman-ford : 进行 k 次松弛操作, 每次松弛操作都遍历整张图, 因此效率很低, 时间复杂度为 (nm). k 次松弛操作的实际含义是 起点到其他点在经过不超过 k 条边的最短距离 (因此需要 backup数组, 防止有串联的情况发生)

spfa : 每个点能够进行多次松弛操作的 dijkstra 算法, 这也是能够处理负权边的原因, 只要该点的 dist 发生了变化, 那么就将它加入队列中, 等待进行松弛操作, 这也是比 bellman-ford 快的原因, bellman 是让所有的点都进行一次松弛操作, 但是 spfa 只会在 dist 改变后才进行松弛操作 ⇒ 确保了每次都是在做有用功, 这也有关于它 dist 数组的定义 (该点是否已经在队列中), 由于该算法会在点出队列之后将它的标记置为 false , 因此如果让一个点重复入队的话, 那么它之后进行的松弛操作大部分都是无用功!!!

floyd : 基于动态规划. 证明: f[k][i][j] 表示 经过若干个不超过 编号为 k 的节点, 从 i 到 j 的最短路的长度, 这样就能够求出 1~k 的节点中所有节点两两之间的最短路径了. 该状态集合能够划分为两种情况 : 1. i → j 的路径上不经过 k . 2. i → j 的路径上经过节点 k. 因此就会有两个集合 ( 1. i → j 其中所有经过的节点不超过 k-1, 因为它不经过 k. 2. i → k → j , 可以发现 i → k 和 k → j 这两个集合是互不影响的, 因此前面的路径为 f[k-1][i][k], 后面的路径为 f[k-1][k][j] ) . 因此就能够进行状态的转移 ⇒ f[k][i][j] = min(f[k-1][i][k] + f[k-1][k][j], f[k-1][i][j]) , 再优化掉第一维, 状态转移就变成了 f[i][j] = min(f[i][k] + f[k][j], f[i][j]) . 其中它的初始为 f[0][i][j] = g[i][j] , 因为 i→j 不会经过其他任何的点, 所以可以直接在 g 数组之上直接进行状态计算. 最终所有的 i → j 都能得到最短距离 (中间路径经过若干点, 且节点编号不超过 n 的最短距离)