简介
Johnson算法是求解多源最短路的算法之一，核心操作是re-weight，适用于不包含负环（负权回路）的图。时间复杂度$O(nm+nmlogm)$。
Johnson算法
全源最短路常用方法是Floyd算法，时间复杂度$O(n^{3})$。当然我们也可以对每个顶点跑单源最短路。如果对每个顶点求一次Bellman-Ford算法，时间复杂度是$O(n^{2}m)$，似乎不如Floyd算法。如果是对每个顶点求一次Dijkstra算法，时间复杂度是$O(nm+nmlogm)$，看起来优于Floyd算法了。但是如何去除负边权的影响呢？
考虑一下直接把所有边权加个正数，但是显然不满足原图性质了：
这里提出一个re-weight操作，首先加上一个源点，并使其与所有顶点连通，新边权赋值为0，如下图：
然后以新加顶点为源，跑Bellman-Ford算法，求出到其它顶点的最短路：
记录下最短路径长度h[] = {0, -3, 0, 0}，删除刚刚新增加的结点。然后对原图边权进行处理，使用以下方法更新边权：$w’(u, v) = w(u, v) + (h[u] - h[v])$。
这时，负边权的影响就被消除了，可以愉快的使用Dijkstra算法了。（懒一下，正确性请自行证明）。
模板
1const int inf = 0x3f3f3f3f;
2const int mxn = 1e3 + 5;
3
4struct E {
5 int to, next, w;
6} e[mxn];
7
8int H[mxn], tot;
9
10void add(int from, int to, int w) {
11 e[tot] = {to, H[from], w};
12 H[from] = tot++;
13}
14
15void graph_init(int n)
16{
17 for(int i=1; i<=n; i++)
18 H[i] = -1;
19 tot = 0;
20}
21
22int h[mxn], num[mxn];
23bool vis[mxn];
24queue<int> q;
25
26void spfa_init(int n)
27{
28 for(int i=1; i<=n; i++){
29 h[i] = inf;
30 num[i] = 0;
31 }
32}
33
34int spfa(int s, int n)
35{
36 h[s] = 0; q.push(s);
37 num[s] = vis[s] = 1;
38 while(!q.empty())
39 {
40 int u = q.front(); q.pop(); vis[u] = 0;
41 for(int i=H[u]; ~i; i=e[i].next){
42 int v = e[i].to, w = e[i].w;
43 if(h[u]+w < h[v]){
44 h[v] = h[u]+w;
45 if(!vis[v]){
46 q.push(v), vis[v] = 1;
47 if(++num[v] > n) return -1;
48 }
49 }
50 }
51 }
52 return 0;
53}
54
55int dis[mxn];
56priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
57
58void dijkstra_init(int n)
59{
60 for(int i=1; i<=n; i++){
61 vis[i] = 0;
62 dis[i] = inf;
63 }
64}
65
66void dijkstra(int s, int n)
67{
68 pq.push({dis[s]=0, s});
69 while(!pq.empty()){
70 int u = pq.top().second; pq.pop();
71 if(vis[u]) continue;
72 vis[u] = 1;
73 for(int i=H[u]; ~i; i=e[i].next){
74 int v=e[i].to, w=e[i].w;
75 if(!vis[v] && dis[u]+w < dis[v]){
76 dis[v] = dis[u]+w;
77 pq.push({dis[v], v});
78 }
79 }
80 }
81}
82
83int DIS[mxn][mxn];
84
85int main()
86{
87 int n, m;
88 scanf("%d %d", &n, &m);
89 graph_init(n);
90
91 for(int i=1; i<=m; i++)
92 {
93 int u, v, w;
94 scanf("%d %d %d", &u, &v, &w);
95 add(u, v, w);
96 }
97
98 for(int i=1; i<=n; i++)
99 add(0, i, 0);
100
101 spfa_init(n);
102 if(spfa(0, n) == -1)
103 {
104 printf("包含负权回路\n");
105 }
106 else
107 {
108 for(int u=1; u<=n; u++){
109 for(int i=H[u]; ~i; i=e[i].next){
110 e[i].w += h[u] - h[e[i].to];
111 }
112 }
113
114 for(int i=1; i<=n; i++){
115 dijkstra_init(n);
116 dijkstra(i, n);
117 for(int j=1; j<=n; j++){
118 DIS[i][j] = dis[j] - h[i] + h[j];
119 printf("%d ", DIS[i][j]);
120 }
121 printf("\n");
122 }
123 }
124
125 return 0;
126}
127
128
129/*
130Sample Input:
131
1324 5
1331 2 -3
1342 3 2
1351 4 3
1362 3 4
1373 4 1
138
139
140Sample Output:
141
1420 -3 -1 0
1431061109570 0 2 3
1441061109568 1061109565 0 1
1451061109567 1061109564 1061109566 0
146
147*/