全源最短路
给定一个有向图或无向图，求任意两点之间的最短路径。
Floyd算法
1.算法思想：Floyd算法的本质是动态规划，所以只要找到动态转移方程，就可以按照转移方程很简单地写出代码。
从任意节点i到任意节点j的最短路经有两种可能：
（1）从节点i直接到节点j；
（2）从节点i经过若干个节点k到节点j。
所以，我们假设d[i,j]为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查d[i,k] + d[k,j] < d[i,j]是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置d[i,j]=d[i,k] + d[k,j] ，这样一来，当我们遍历完所有节点k，d[i,j]中记录的便是i到j的最短路径的距离。
因此动态转移方程为：
d[i,j]=min(d[i,j],d[i,k]+d[k,j])；
2.算法流程：
（1）初始化d[i][j]为正无穷，d[i][i]=0，建立邻接矩阵。
（2）按照动态转移方程进行转移。
代码如下：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=3e2+5;
4 int d[N][N],m,n;
5 void floyd()
6 {
7 for(int k=1;k<=n;k++)//k放最外层
8 for(int i=1;i<=n;i++)
9 for(int j=1;j<=n;j++)
10 d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
11 }
12 int main()
13 {
14 cin>>n>>m;
15 memset(d,0x3f,sizeof(d));
16 for(int i=1;i<=n;i++) d[i][i]=0;//初始化
17 for(int i=1;i<=m;i++)
18 {
19 int u,v,w;
20 cin>>u>>v>>w;
21 d[u][v]=min(d[u][v],w);//直接把d数组初始化为邻接矩阵
22 }
23 floyd();
24 for(int i=1;i<=n;i++)
25 {
26 for(int j=1;j<=n;j++)
27 cout<<d[i][j]<<" ";
28 cout<<endl;
29 }
30 return 0;
31 }
3.注意事项：
枚举k的for循环必须放在最外层，因为是对于每一个节点k，我们检查d[i,k] + d[k,j] < d[i,j]是否成立，所以k相当于是阶段，只有当一个阶段执行完成后，才能进入下一个阶段。时间复杂度为O（n3），适用于较稠密的图，不能处理有负环的图。
4.例题：洛谷P1119 灾后重建 https://www.luogu.com.cn/problem/P1119
这是一道很裸的floyd求最短路的问题，题目意思可简化为：给定所有边，按照时间顺序更新每一个可用的点（即修建好村庄），对于每个时间点进行两点之间询问，求对于目前建设的所有村庄来说任意两点之间的最短路，不正好就是Floyd算法中使用前k个节点更新最短路的思维吗？出题人还是很良心的，保证所有的数据都是用时间顺序给出的，所以我们只用读取+操作就可以了，不用再储存＋排序。
因此该题的大致思路如下：
（1）读入，存下每个村庄修复的时间；
（2）读入所有的边并使用邻接矩阵存图；
（3）初始化
（4）对于每次询问，将在当前时间前的所有点全部用Floyd更新；
（5）特殊判断并输出。
特别注意一下这里的点编号是从0开始的，如果像我一样习惯从1开始的标下标的话要特别注意这一点。
AC代码如下：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=205;
4 int n,m,q,t[N],d[N][N];
5 void Floyd(int k)
6 {
7 for(int i=1;i<=n;i++)
8 for(int j=1;j<=n;j++)
9 d[i][j]=d[j][i]=min(d[i][j],d[i][k]+d[k][j]);
10 return ;
11 }
12 int main()
13 {
14 cin>>n>>m;
15 for(int i=1;i<=n;i++) cin>>t[i];
16 memset(d,0x3f,sizeof(d));
17 for(int i=1;i<=n;i++) d[i][i]=0;//初始化
18 while(m--)
19 {
20 int x,y,w;
21 cin>>x>>y>>w;
22 x++;
23 y++;//因为题目编号从零开始，我这里是从1开始的，所以要++
24 d[x][y]=w;
25 d[y][x]=w;//无向图，双向存边
26 }
27 cin>>q;
28 int now=1;
29 while(q--)
30 {
31 int x,y,z;
32 cin>>x>>y>>z;
33 x++;
34 y++;//同23行
35 while(t[now]<=z&&now<=n) Floyd(now),now++; //将在当前时间前的所有点全部用Floyd更新
36 if(t[x]>z||t[y]>z)
37 {
38 cout<<"-1"<<endl;
39 continue;//村庄未建好
40 }
41 if(d[x][y]==0x3f3f3f3f) cout<<"-1"<<endl;//两点不连通
42 else cout<<d[x][y]<<endl;
43 }
44 return 0;
45 }
Johnson算法
上文讲的Floyd算法处理不了含有负环的图，且时间复杂度较高，对于稀疏图来说，效率不高。因此我们这里介绍一种新的算法——Johnson算法。
1.算法思想：利用重赋权值的方法把一个原问题带负权的图转化为权值非负的图，然后再利用n次Dijkstra算法（堆优化）求出全源最短路径，时间复杂度为O(nmlogm)。
现在主要问题就转化为如何将原问题带负权的图转化为权值非负的图？
我们这里新建一个虚拟节点s（在这里我们就设它的编号为 0）。从这个点向其他所有点连一条边权为 0 的边。
接下来用spfa算法求出从0号节点到其他所有节点i的最短路，记为h[i]。
假如存在一条从u点到v点，边权为w的边，则我们将该边的边权重新设置为w+h[u]+h[v] 。
那么为什么这样重新标注边权的方式是正确的呢？
在重新标记后的图上，从u点到v点的一条路径u→p1→p2→⋯→pk→v的长度表达式如下：
(w(u,p1)+hu−hp1)+(w(p1,p2)+hp1−hp2)+⋯+(w(pk,v)+hpk−hv)
化简后得到：
w(s,p1)+w(p1,p2)+⋯+w(pk,v)+hu−hv
无论我们从u到t走的是哪一条路径，hs−ht 的值是不变的,这与物理中的重力势能有异曲同工之处。
因此原图上u→v 的最短路与新图上u→v 的最短路相对应。
又根据三角形不等式，新图上任意一边(u,v) 上两点满足：hv≤hu+w(u,v) 。这条边重新标记后的边权为w′(u,v)=w(u,v)+hu−hv≥0 。
这样我们证明了新图上的边权均非负。
接下来我们以每个点为起点，跑n轮 Dijkstra 算法即可求出任意两点间的最短路了。
2.算法流程：
（1）重赋权值：
a.建新图，增设一虚点s，由s往各点连一条权值为0的边.
b.使用spfa求出点s到所有点的最短路，用h ( i )表示,同时判断是否存在负环.
c.对于每条边，w(u,v)将其变成w ( u , v ) ' = w ( u , v ) + h ( u ) − h ( v ) ;
（2）以每个点为起点，跑n轮Dijkstra 算法。
3.注意事项：最后计算答案时要将重赋权值是多加的h ( u ) − h ( v ) 减去。
4.例题：洛谷P5905 https://www.luogu.com.cn/problem/P5905
AC代码如下：
1 #include<bits/stdc++.h>
2 #define pa pair<int,int>
3 using namespace std;
4 const int N=1e5+5,inf=2147483647;
5 int n,m,vis[N],cnt[N];
6 long long d[N],h[N];
7 vector<pa >g[N];
8 queue<int>q;
9 int spfa(int s)
10 {
11 fill(h,h+N,inf);
12 h[s]=0;
13 q.push(s);
14 vis[s]=1;
15 while(q.size())
16 {
17 int u=q.front();
18 q.pop();
19 vis[u]=0;
20 if(++cnt[u]>=n) return 0;//判断负环
21 for(int i=0;i<g[u].size();i++)
22 {
23 int v=g[u][i].first,w=g[u][i].second;
24 if(h[v]>h[u]+w)
25 {
26 h[v]=h[u]+w;
27 if(vis[v]==0)
28 {
29 q.push(v);
30 vis[v]=1;
31 }
32 }
33 }
34 }
35 return 1;
36 }
37 priority_queue<pa,vector<pa>,greater<pa> >qq;
38 void dijkstra(int s)
39 {
40 memset(vis,0,sizeof(vis));
41 fill(d,d+N,inf);
42 d[s]=0;
43 cnt[s]=1;
44 qq.push(make_pair(0,s));
45 while(qq.size())
46 {
47 pa t=qq.top();
48 qq.pop();
49 int u=t.second;
50 if(vis[u]) continue;
51 vis[u]=1;
52 for(int i=0;i<g[u].size();i++)
53 {
54 int v=g[u][i].first,w=g[u][i].second;
55 if(d[v]>d[u]+w)
56 {
57 d[v]=d[u]+w;
58 qq.push(make_pair(d[v],v));
59 }
60 }
61 }
62 }
63 int main()
64 {
65 int s;
66 cin>>n>>m;
67 int x,y,w;
68 for(int i=1;i<=m;i++) cin>>x>>y>>w,g[x].push_back(make_pair(y,w));
69 for(int i=1;i<=n;i++) g[0].push_back(make_pair(i,0));//初始化，建新图，增设一虚点0，由0往各点连一条权值为0的边
70 if(!spfa(0))
71 {
72 cout<<-1<<endl;
73 return 0; //用spfa求出点s到所有点的最短路，判断负环
74 }
75 for(int i=1;i<=n;i++)
76 for(int j=0;j<g[i].size();j++)
77 g[i][j].second+=h[i]-h[g[i][j].first];//w(u,v)将其变成w ( u , v ) ' = w ( u , v ) + h ( u ) - h ( v )
78 for(int i=1;i<=n;i++)
79 {
80 long long ans=0;
81 dijkstra(i);//以每个点为起点，跑n轮Dijkstra 算法
82 for(int j=1;j<=n;j++)
83 {
84 if(d[j]==inf) ans+=1ll*j*1000000000;
85 else ans+=j*(d[j]+h[j]-h[i]);//注意最后要将前面多加上去的h(i)−h(j)减去
86 }
87 cout<<ans<<endl;
88 }
89 return 0;
90 }
转载请注明原文链接：全源最短路