1 简介
最短路问题分为两类:单源最短路 和多源最短路 。前者只需要求一个固定的起点 到各个顶点的最短路径,后者则要求得出任意两个顶点 之间的最短路径。
单源 Dijkstra算法 :
优点 :时间复杂度稳定O ( n 2 ) O(n^2) O ( n 2 ) ,堆优化能达到O ( E l o g E ) O(ElogE) O ( E l o g E ) ;也可解决多源最短路,总的时间复杂度也是O ( n 3 ) O(n^3) O ( n 3 )
缺点 :不能处理负边
单源 Bellman-Ford算法 :
优点 :其优于Dijkstra算法的方面是边的权值可以为负数、实现简单
缺点 :时间复杂度过高,高达O ( V ∗ E ) O(V*E) O ( V ∗ E ) ;但算法可以进行若干种优化,提高了效率。
单源 SPFA算法 :
优点 :快于Bellman-Ford,据说随机数据下期望时间复杂度是O ( m + n l o g n ) O(m+nlogn) O ( m + n l o g n )
缺点 :时间复杂度不稳定 ,最坏情况可以被卡成Bellman-Ford,也就是O ( V ∗ E ) O(V*E) O ( V ∗ E )
全源 Floyd算法 :
优点 :算法简洁,可以解决负权图
缺点 :时间复杂度为O ( n 3 ) O(n^3) O ( n 3 ) ,空间复杂度为O ( n 2 ) O(n^2) O ( n 2 ) ,都比较高,所以只适用于数据规模较小的情形;不能解决负环图
全源 Johnson算法 :
优点 :相对于Floyd算法时间复杂度低,O ( n m l o g m ) O(nmlogm) O ( n m l o g m ) ;
缺点 :无负环图、算法较繁琐
BFS算法 :
2 单源 Dijkstra算法
贪心 的思想,不断取出离顶点最近 而没有被访问过 的点,松弛它和它能到达的所有点。
对于每个顶点v∈V,都设置一个属性d[v],用来描述从源点s到v的最短路径上权值的上界,称为最短路径估计(shortest-pathestimate)。
π[v]代表S到v的当前最短路径中v点之前的一个点的编号,我们用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化。
在松弛一条边(u,v)的过程中,要测试是否可以通过u,对迄今找到的v的最短路径进行改进;如果可以改进的话,则更新d[v]和π[v]。一次松弛操作可以减小最短路径估计的值d[v],并更新v的前趋域π[v](S到v的当前最短路径中v点之前的一个点的编号)。
打印路径 :只需要用一个pre[]数组存储每个点的父节点 即可。(单源最短路的起点是固定的,所以每条路有且仅有一个祖先节点,一步步溯源上去的路径是唯一的。相反,这里不能存子节点 ,因为从源点下去,有很多条最短路径)
参考:https://zhuanlan.zhihu.com/p/96621396
朴素Dijkstra :时间复杂度是 O ( n 2 + m ) O(n^2+m) O ( n 2 + m ) , n n n 表示点数,m m m 表示边数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 const int maxn = 5e2 + 5 ;int g[maxn][maxn]; int dist[maxn]; bool st[maxn]; int n; int dijkstra () { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; for (int i = 0 ; i < n - 1 ; i ++ ) { int t = -1 ; for (int j = 1 ; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; for (int j = 1 ; j <= n; j ++ ) dist[j] = min (dist[j], dist[t] + g[t][j]); st[t] = true ; } if (dist[n] == 0x3f3f3f3f ) return -1 ; return dist[n]; }
堆优化Dijkstra :时间复杂度 O ( m l o g n ) O(mlogn) O ( m l o g n ) , n n n 表示点数,m m m 表示边数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 const int maxn = 1.5e5 + 5 ;typedef pair<int , int > PII;int n; int h[maxn], w[maxn], e[maxn], ne[maxn], idx; int dist[maxn]; bool st[maxn]; void add (int x, int y, int c) { w[idx] = c; e[idx] = y; ne[idx] = h[x]; h[x] = idx++; } int dijkstra () { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; priority_queue<PII, vector <PII>, greater<PII>> heap; heap.push({0 , 1 }); while (heap.size ()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue ; st[ver] = true ; for (int i = h[ver]; i != -1 ; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f ) return -1 ; return dist[n]; }
3 单源 Bellman-Ford算法
一维数组dist[]来存储每个点到起点的距离,初始化dist[S] = 0,其他初始化为INF。
找到从起点到某个点的最短路,设起点为S,终点为D,那这条最短路一定是S − > P 1 − > P 2 − > . . . − > D S->P_1->P_2->...->D S − > P 1 − > P 2 − > . . . − > D 的形式,假设没有负权环 ,那这条路径上的点的总个数一定不大于n 。
定义对点x, y的松弛操作是:
1 dist[y] = min (dist[y], dist[x] + e[x][y]);
松弛操作就相当于考察能否经由x点 使起点到y点 的距离变短。
所以要找到最短路,只需要进行以下步骤:
先松弛S S S , P 1 P_1 P 1 ,此时d i s t [ P 1 ] dist[P_1] d i s t [ P 1 ] 必然等于e [ S ] [ P 1 ] e[S][P_1] e [ S ] [ P 1 ]
再松弛P 1 , P 2 P_1, P_2 P 1 , P 2 ,因为S − > P 1 − > P 2 S->P_1->P_2 S − > P 1 − > P 2 是最短路的一部分,最短路的子路也是最短路 (这是显然的),所以d i s t [ P 2 ] dist[P_2] d i s t [ P 2 ] 不可能小于d i s t [ P 1 ] + e [ P 1 ] [ P 2 ] dist[P_1]+e[P_1][P_2] d i s t [ P 1 ] + e [ P 1 ] [ P 2 ] ,因此它会被更新为d i s t [ P 1 ] + e [ P 1 ] [ P 2 ] dist[P1]+e[P1][P2] d i s t [ P 1 ] + e [ P 1 ] [ P 2 ] ,即e [ S ] [ P 1 ] + e [ P 1 ] [ P 2 ] e[S][P1]+e[P1][P2] e [ S ] [ P 1 ] + e [ P 1 ] [ P 2 ] 。
再松弛P 2 , P 3 P2, P3 P 2 , P 3 ,……以此类推,最终d i s t [ D ] dist[D] d i s t [ D ] 必然等于e [ S ] [ P 1 ] + e [ P 1 ] [ P 2 ] + . . . e[S][P1]+e[P1][P2]+... e [ S ] [ P 1 ] + e [ P 1 ] [ P 2 ] + . . . ,这恰好就是最短路径。
把所有边松弛n-1遍!
https://zhuanlan.zhihu.com/p/96621396
https://blog.csdn.net/luomingjun12315/article/details/50377525
4 单源 SPFA算法
SPFA算法 ,也就是队列优化 的Bellman-Ford算法,维护一个队列。
5 全源 Floyd算法
求出每一对顶点之间的最短路径。Floyd本质上是一个动态规划 的思想,每一次循环更新经由k点,i到j的最短路径 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void floyd () { for (int i = 1 ; i <= n; i ++ ) for (int j = 1 ; j <= n; j ++ ) if (i == j) d[i][j] = 0 ; else d[i][j] = inf; for (int k = 1 ; k <= n; k ++ ) { for (int i = 1 ; i <= n; i ++ ) { for (int j = 1 ; j <= n; j ++ ) { if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; } } } } }
6 全源 Johnson算法
7 BFS算法
该算法求单源最短路径只适用于无权图,或所有边的权值都相同的图。
练习
acwing模板题目——Dijkstra求最短路 I
Dijkstra求最短路 II