首页 > 代码库 > 最短路(floyd/dijkstra/bellmanford/spaf 模板)
最短路(floyd/dijkstra/bellmanford/spaf 模板)
floyd/dijkstra/bellmanford/spaf 模板：
1. floyd(不能处理负权环，时间复杂度为O(n^3), 空间复杂度为O(n^2))
floyd算法的本质是dp，用dp[k][i][j]表示以(１....k)为中间点，i, j之间的最短距离为多少，dp[0][i][j]即为原矩阵图。
dp[k][i][j]可以由dp[k-1][i][j]转移得到，即不经过 k 点i, j之间的最短距离为多少，
也可以由dp[k-1][i][k]+dp[k-1][k][j]转移得到，即经过 k 点i, j之间的最短距离为多少。
那么动态转移方程式为:
dp[k][i][j]=min(dp[k][i][j], dp[k-1][i][k]+dp[k-1][k][j])
很显然实现过程中我们只要开二维数组就可以了，并不需要存储前面那个k的信息，因为k的状态直接就可以由k-1的状态得出。
事实上以上内容也解释了代码中 k 这层循环为什么在最外层。
代码：
1 #include <bits/stdc++.h> 2 #define MAXN 210 3 using namespace std; 4 5 const int inf=1e9; 6 int mp[MAXN][MAXN]; //***记录从i点到j点的最短距离，若不可达则标记为inf 7 int path[MAXN][MAXN]; //***通过后继节点记录路劲 8 9 //***注意这里节点是从0开始计数的 10 void floyd(int n){ 11 memset(path, -1, sizeof(path)); 12 for(int k=0; k<n; k++){//***注意最外层循环是 k 13 for(int i=0; i<n; i++){ 14 for(int j=0; j<n; j++){ 15 if(mp[i][j]>mp[i][k]+mp[k][j]){ 16 mp[i][j]=mp[i][k]+mp[k][j]; 17 path[i][j]=k; //***将路劲信息通过队列倒序输出即为最短路劲 18 } 19 } 20 } 21 } 22 } 23 24 //***要求输出字典序最小的路劲 25 /* 26 void floyd(int n){ 27 memset(path, -1, sizeof(path)); 28 for(int k=0; k<n; k++){//***注意最外层循环是 k 29 for(int i=0; i<n; i++){ 30 for(int j=0; j<n; j++){ 31 if(mp[i][j]>mp[i][k]+mp[k][j]){ 32 mp[i][j]=mp[i][k]+mp[k][j]; 33 path[i][j]=k; //***将路劲信息通过队列倒序输出即为最短路劲 34 }else if(mp[i][j]==mp[i][k]+mp[k][j]&&path[i][j]>path[i][k]){ 35 path[i][j]=path[i][k]; //***记录字典序最小的路劲 36 } 37 } 38 } 39 } 40 } 41 */ 42 43 int main(void){ 44 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 45 int n, m; 46 while(cin >> n >> m){ 47 for(int i=0; i<n; i++){ //***初始化 48 for(int j=0; j<n; j++){ 49 if(i==j){ 50 mp[i][j]=0; 51 }else{ 52 mp[i][j]=inf; 53 } 54 } 55 } 56 int x, y, z; 57 while(m--){ 58 cin >> x >> y >> z; 59 mp[x][y]=mp[y][x]=min(mp[x][y], z); 60 } 61 int s, e; 62 cin >> s >> e; 63 floyd(n); 64 if(mp[s][e]>=inf){ 65 cout << "-1" << endl; 66 }else{ 67 cout << mp[s][e] << endl; 68 //********下面输出路劲*********** 69 stack<int> st; 70 int cnt=e; 71 while(path[s][cnt]!=-1){ 72 st.push(cnt); 73 cnt=path[s][cnt]; 74 } 75 st.push(cnt); 76 st.push(s); 77 while(!st.empty()){ 78 cout << st.top() << " "; 79 st.pop(); 80 } 81 cout << endl; 82 } 83 } 84 return 0; 85 }
2. dijkstra(不能有负权边，时间复杂度O(n^2), 空间复杂度O(n^2))
PS: 找了下不能处理负权边的证明，然而网上博客大都写的是不能处理负权环的证明：负环会破坏dijkstra的贪心策略，例如，假设用dijkstra求得图中mp[s][k]的最短距离dist[k]为distancek, 那么此时点k会被标记, 即dist[k]不能再被更新，如果存在一条足够小的负权边，那么s经过这条边到k的距离显然是可以小于distancek的（显然这需要k和连接负权边的点在同一个环中），我们接着用这个错误的dist[k]去更新后面的点，那么得到的答案也就不能保证是正确的咯．．．
另外，还有一种更简单的例子：假如一张图里有一个总长为负数的环，那么Dijkstra算法有可能会沿着这个环一直绕下去，绕到地老天荒．．．
对于负权边的证明：
假设一张加权图，有的边长为负数。假设边长最小为-10，我们把所有的边长都加上10，就这就可以得到一张无负值加权图。此时用Dijkstra算法算出一个从节点s到节点t的最短路径L，L共包括n条边，总长为t；那么对于原图，每条边都要减去10，所以原图中L的长度是t-10*n。这是Diskstra算法算出的结果。
那么问题来了：对于加上10之后的图，假设还有一个从s到t的路径M，长度为t1，它共包括n1条边，比L包含的边长多，那么还原回来之后，每条边需要减去10，那么M的总长就是t1-10*n1。那么，是不是M的总长一定比L的总长更长一些呢？不一定。假如n1>n，也就是说M的边数比L的边数更多，那么M减去的要比L减去的更多，那么t1-10*n1<t-10*n是可能的。此时Dijkstra算法是不成立的。
另外，如果一张图里有负数边，但没有总长为负数的环，此时可以用Bellman-Ford算法计算。虽然它比Dijkstra慢了一些，但人家应用范围更广啊。
dijkstra算法和最小生成树的prim有点像，prim算法是将所有点分成两个点集s, w，初始时s中只有一个点，然后依次将w中距离s集合最近的点加入s集合中，直至w为空集．．
这两个算法的区别是prim算法中更新的是w点集中的点到s点集的最小距离，dijkstra算法是以s点集中的点为中间节点更新w点集中所有点到出发点的最小距离．．．
a. 单源最短路代码：
1 #include <bits/stdc++.h> 2 #define MAXN 210 3 using namespace std; 4 5 const int inf=0x3f3f3f3f; 6 int mp[MAXN][MAXN], pre[MAXN], dist[MAXN]; 7 bool vis[MAXN]; 8 //***mp存储图, pre[i]记录i的父亲节点，dist[i]记录源点到 i 的最短距离 9 //***vis[i]标记节点 i 是否被访问过 10 11 int dijkstra(int n, int s, int e){ //***注意节点从0开始 12 for(int i=0; i<n; i++){ 13 dist[i]=mp[s][i]; 14 pre[i]=-1; 15 vis[i]=false; 16 } 17 dist[s]=0; 18 vis[s]=true; 19 for(int i=0; i<n; i++){ 20 int min=inf, k=0; 21 for(int j=0; j<n; j++){//***更新距离 22 if(!vis[j]&&dist[j]<min){ 23 min=dist[j]; 24 k=j; 25 } 26 } 27 if(min==inf){ 28 break; 29 } 30 vis[k]=true; 31 for(int j=0; j<n; j++){ //***进行松驰操作 32 if(!vis[j]&&dist[j]>dist[k]+mp[k][j]){ 33 dist[j]=dist[k]+mp[k][j]; 34 pre[i]=k; //***记录路径 35 } 36 } 37 } 38 return dist[e]; 39 } 40 41 int main(void){ 42 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 43 int n, m; 44 while(cin >> n >> m){ 45 for(int i=0; i<n; i++){ 46 for(int j=0; j<n; j++){ 47 mp[i][j]=mp[j][i]=inf; 48 } 49 } 50 int x, y, z; 51 while(m--){ 52 cin >> x >> y >> z; 53 if(mp[x][y]>z){ //***处理重边 54 mp[x][y]=mp[y][x]=z; 55 } 56 } 57 int s, e; 58 cin >> s >> e; 59 int ans=dijkstra(n, s, e); 60 if(ans>=inf){ 61 cout << -1 << endl; 62 }else{ 63 cout << ans << endl; 64 cout << s << " "; 65 while(pre[s]!=-1){ //***输出路径 66 cout << pre[s] << " "; 67 s=pre[s]; 68 } 69 cout << e << endl; 70 } 71 } 72 return 0; 73 }
b. 存在边权值，求最短路中边权值最小的路径的距离及其权值和
代码：
1 const int inf=0x3f3f3f3f; 2 int mp[MAXN][MAXN], dist[MAXN], val[MAXN]; 3 int cost[MAXN][MAXN]; 4 bool vis[MAXN]; 5 //***mp存储图, pre[i]记录i的父亲节点，dist[i]记录源点到 i 的最短距离, 6 //***cost[i][j]存储 i 节点到 j 节点的花费， val[i]记录源点到 i 点最短路的最小费用 7 //***vis[i]标记节点 i 是否被访问过 8 9 int dijkstra(int n, int s, int e){ //***注意节点从0开始 10 for(int i=0; i<n; i++){ 11 dist[i]=mp[s][i]; 12 val[i]=cost[s][i]; 13 vis[i]=false; 14 } 15 dist[s]=0; 16 vis[s]=true; 17 for(int i=0; i<n; i++){ 18 int MIN=inf, k=0; 19 for(int j=0; j<n; j++){//***更新距离 20 if(!vis[j]&&dist[j]<MIN){ 21 MIN=dist[j]; 22 k=j; 23 } 24 } 25 if(MIN==inf){ 26 break; 27 } 28 vis[k]=true; 29 for(int j=0; j<n; j++){ //***进行松驰操作 30 if(!vis[j]&&dist[j]>dist[k]+mp[k][j]){ 31 dist[j]=dist[k]+mp[k][j]; 32 val[j]=val[k]+cost[k][j]; 33 }else if(!vis[j]&&dist[j]==dist[k]+dist[k][j]){//***取花费小的节点进行松驰 34 val[j]=min(val[j], val[k]+cost[k][j]); 35 } 36 } 37 } 38 cout << dist[e] << " " << cost[e] << endl; 39 }
c. 存在节点权值，求最短路中权值最小的路径的距离及其权值
代码：
1 const int INF=0x3f3f3f3f; 2 int mp[MAXN][MAXN], low[MAXN], tag[MAXN], n, m, rank[MAXN], vis[MAXN]; 3 // low[j]记录出发点到点j的最短距离，tag[j]标记点j是否被选中过, vis[j]记录出发点到点j的最大权值 4 5 void dijkstra(int s, int e){ 6 for(int i=0; i<n; i++){ //初始化 7 low[i]=mp[s][i]; 8 } 9 vis[s]=rank[s]; 10 low[s]=0; 11 for(int i=0; i<n; i++){ 12 int MIN=INF; 13 for(int j=0; j<n; j++){ 14 if(low[j]<MIN&&!tag[j]){ 15 MIN=low[j]; 16 s=j; //s为当前选中的点 17 } 18 } 19 tag[s]=1; 20 for(int j=0; j<n; j++){ //更新各点到出发点的最小距离 21 if(low[j]>mp[s][j]+low[s]){ 22 low[j]=mp[s][j]+low[s]; 23 vis[j]=vis[s]+rank[j]; 24 }else if(low[j]==mp[s][j]+low[s]){ //若距离相等则更新权值更小的点 25 vis[j]=min(vis[s]+rank[j], vis[j]); 26 } 27 } 28 } 29 cout << low[e] << " " << vis[e] << endl; 30 }
d. dijkstra堆优化(时间复杂度O(n*(log*(m), 空间复杂度为n*n)
对于边数远小于n*n的情况其耗时远少于未优化情况
操作：
1. 将与源点相连的点加入堆，并调整堆。
2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
3. 处理与u相邻的，未被访问过的，满足三角不等式的顶点
1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
2):若该点不在堆里，加入堆，更新堆。
4. 若取到的u为终点，结束算法；否则重复步骤2、3。
代码：
1 #include <bits/stdc++.h> 2 #define MAXN 210 3 using namespace std; 4 5 vector<pair<int, int> > mp[MAXN]; //***记录图 6 int dist[MAXN]; //***记录源点此时到 i 的最短距离 7 bool vis[MAXN]; //***标记该点是否在堆中 8 const int inf=0x3f3f3f3f; 9 10 struct node{ //***重载比较符使优先队列非升序排列 11 int point, value; 12 friend bool operator< (node a, node b){ 13 return a.value>b.value; 14 } 15 }; 16 17 int dijkstra_heap(int s){ 18 priority_queue<node> q; 19 memset(dist, 0x3f, sizeof(dist)); 20 memset(vis, false, sizeof(vis)); 21 dist[s]=0; 22 q.push({s, dist[s]}); 23 while(!q.empty()){ 24 node u=q.top(); 25 int point=u.point; 26 q.pop(); 27 if(vis[point]){ 28 continue; 29 }else{ 30 vis[point]=true; 31 } 32 for(int i=0; i<mp[point].size(); i++){ 33 int v=mp[point][i].first; 34 int cost=mp[point][i].second; 35 if(!vis[v]&&dist[v]>dist[point]+cost){ //***松驰操作 36 dist[v]=dist[point]+cost; 37 q.push({v, dist[v]}); 38 } 39 } 40 } 41 } 42 43 int main(void){ 44 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 45 int n, m; 46 while(cin >> n >> m){ 47 while(m--){ 48 int x, y, z; 49 cin >> x >> y >> z; 50 mp[x].push_back({y, z}); 51 mp[y].push_back({x, z}); 52 } 53 int s, e; 54 cin >> s >> e; 55 dijkstra_heap(s); 56 if(dist[e]>=inf){ 57 cout << -1 << endl; 58 }else{ 59 cout << dist[e] << endl; 60 } 61 for(int i=0; i<n; i++){ 62 mp[i].clear(); 63 } 64 } 65 return 0; 66 }
不难发现其代码与之前的写法并没有很大区别，只是将点集s存入优先队列中，这样我们在取dist[k]时只需要取堆顶元素即可，只需O(1)的时间，另外需要log(m)的时间维护优先队列，再加上遍历节点的时间O(n)，总共耗时O(n*log(m)).....
3. bellmanford(可以处理负权边情况，并能判断是否存在负权边环．时间复杂度O(n*m), 空间复杂度O(n*n)) 其中m为边数
bellman-ford算法进行n-1次更新（一次更新是指用所有节点进行一次松弛操作）来找到到所有节点的单源最短路。bellman-ford算法和dijkstra其实有点相似，该算法能够保证每更新一次都能确定一个节点的最短路，但与dijkstra不同的是，并不知道是那个节点的最短路被确定了，只是知道比上次多确定一个，这样进行n-1次更新后所有节点的最短路都确定了（源点的距离本来就是确定的）。
现在来说明为什么每次更新都能多找到一个能确定最短路的节点：
1）.将所有节点分为两类：已知最短距离的节点和剩余节点。
2）.这两类节点满足这样的性质：已知最短距离的节点的最短距离值都比剩余节点的最短路值小。（这一点也和dijkstra一样）
3）.有了上面两点说明，易知到剩余节点的路径一定会经过已知节点
4）.而从已知节点连到剩余节点的所有边中的最小的那个边，这条边所更新后的剩余节点就一定是确定的最短距离，从而就多找到了一个能确定最短距离的节点，不用知道它到底是哪个节点。
其判断负权环的机制为：在没有负权环的情况下进行n-1次更新必定能得到所有节点到源点的最短距离，反之则必有负权环（负权环能无限次进行松弛操作嘛）．．
代码：
1 #include <bits/stdc++.h> 2 #define MAXN 210 3 using namespace std; 4 5 const int inf=0x3f3f3f3f; 6 int dist[MAXN], pre[MAXN]; //**dist[i]记录此时源点到i的最短距离，pre[i]记录i的前驱节点，即倒序输出为最短路径 7 struct edge{ 8 int u, v; 9 int cost; 10 }mp[MAXN*MAXN*2]; //***mp记录所有边及其权值 11 12 bool bellman_ford(int n, int m, int s){ 13 memset(dist, 0x3f, sizeof(dist)); 14 dist[s]=0; 15 for(int i=1; i<n; i++){//***更新n-1次 16 int flag=true; 17 for(int j=0; j<m; j++){ 18 if(dist[mp[j].v]>dist[mp[j].u]+mp[j].cost){ 19 dist[mp[j].v]=dist[mp[j].u]+mp[j].cost; //***松驰 20 pre[mp[j].v]=mp[j].u; //**记录前驱节点 21 flag=false; 22 } 23 } 24 if(flag){ //***若所有节点都不再更新，则已得到源点到所有节点的最短距离 25 break; 26 } 27 } 28 for(int j=0; j<m; j++){ //***判断是否存在负权环 29 if(dist[mp[j].v]>dist[mp[j].u]+mp[j].cost){ 30 return false; 31 } 32 } 33 return true; 34 } 35 36 int main(void){ 37 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 38 int n, m; 39 while(cin >> n >> m){ 40 int x, y, z; 41 for(int i=0; i<m; i++){ 42 cin >> x >> y >> z; 43 mp[i].u=x, mp[i].v=y, mp[i].cost=z; 44 mp[i+m].u=y, mp[i+m].v=x, mp[i+m].cost=z; //***无向图 45 } 46 int s, e; 47 cin >> s >> e; 48 bellman_ford(n, m<<1, s); 49 if(dist[e]>=inf){ 50 cout << -1 << endl; 51 }else{ 52 cout << dist[e] << endl; 53 } 54 } 55 return 0; 56 }
4. spfa（可以处理负权边并能判断负权环，时间复杂度为O(k*m), 空间复杂度为O(n*n)）其中m为边数，k为所有节点的平均进队次数，一般<=2n, k是一个常数，随图的确定而确定. spfa是bellman_ford 的队列优化形式，但其稳定性较差．．．
代码：
1 #include <bits/stdc++.h> 2 #define MAXN 210 3 using namespace std; 4 5 const int inf=0x3f3f3f3f; 6 bool vis[MAXN]; //***标记点是否在队列中 7 int cnt[MAXN]; //***cnt[i]记录i节点入队次数，判断是否存在负权环 8 int dist[MAXN]; //**dist[i]记录此时源点到i的最短距离，pre[i]记录i的前驱节点，即倒序输出为最短路径 9 vector<pair<int, int> >mp[MAXN]; 10 11 bool spfa(int n, int s){ 12 memset(vis, false, sizeof(vis)); 13 memset(dist, 0x3f, sizeof(dist)); 14 memset(cnt, 0, sizeof(cnt)); 15 queue<int> q; 16 q.push(s); 17 dist[s]=0; 18 cnt[s]+=1; 19 vis[s]=true; 20 while(!q.empty()){ 21 int u=q.front(); 22 q.pop(); 23 vis[u]=false; 24 for(int i=0; i<mp[u].size(); i++){ 25 int point=mp[u][i].first; 26 if(dist[point]>dist[u]+mp[u][i].second){ //**松驰操作 27 dist[point]=dist[u]+mp[u][i].second; 28 if(!vis[point]){ //***若此点不在队列中则将其入队 29 vis[point]=true; 30 q.push(point); 31 cnt[point]++; 32 if(cnt[point]>n){ //***判断是否存在负权环 33 return false; 34 } 35 } 36 } 37 } 38 } 39 return true; 40 } 41 42 int main(void){ 43 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 44 int n, m; 45 while(cin >> n >> m){ 46 int x, y, z; 47 for(int i=0; i<m; i++){ 48 cin >> x >> y >> z; 49 mp[x].push_back({y, z}); 50 mp[y].push_back({x, z}); 51 } 52 int s, e; 53 cin >> s >> e; 54 spfa(n, s); 55 if(dist[e]>=inf){ 56 cout << -1 << endl; 57 }else{ 58 cout << dist[e] << endl; 59 } 60 for(int i=0; i<MAXN; i++){ //***多重输入记得情况容器 61 mp[i].clear(); 62 } 63 } 64 return 0; 65 }
最短路(floyd/dijkstra/bellmanford/spaf 模板)