理論

全源最短路算法

1. Floyd 算法，時間復雜度為 O(n3)
2. 跑 n 次 Bellman - Ford 算法，時間復雜度是 O(n2m)
3. 跑 n 次 Heap - Dijkstra 算法，時間復雜度是 O(nmlogm)
   第 3 種算法被 Johnson 做了改造，可以求解帶負權邊的全源最短路。

Johnson（約翰遜）算法
4. 新建一個虛擬源點 0，從該點向其他所有點連一條邊權為 0 的邊，再用spfa 算法求出從 0 號點到其他所有點的最短路 h(i)。
5. 將新圖的邊權改造為 w(u,v) + h(u) - h(v)，這樣能確保邊權非負。
6. 以每個點為起點，跑 n 輪 Heap - Dijkstra 算法，求出任意兩點間最短路。

7. 以下是結合Johnson算法對這幅圖的分析：
   1. 構建虛擬源點及初始操作
   圖中節點0是Johnson算法里新添加的虛擬源點 ，從它向節點1、2、3、4分別連了邊權為0的邊（綠色邊）。接下來要用SPFA算法求從0號虛擬源點到其他所有節點的最短路$h(i)$ 。比如從節點0到節點1的邊權為0 ，如果不存在更短路徑，$h(1)$ 初始就是0 ；從節點0到節點4邊權為0 ，若沒有其他路徑干擾，$h(4)$ 也為0 ；從節點0到節點2邊權為-5 ，0 ->3->2。圖中綠色數字即為初始操作(SPFA)后虛擬節點到個其余各個點的距離。
   2. 邊權改造
   根據Johnson算法，需要將圖中各邊的邊權改造為$w(u,v)+h(u)?h(v)$ ，以此確保邊權非負。例如，對于節點1到節點2這條邊，原始邊權$w(1,2)$ 為-1 ，$h(1)=0$ ，$h(2)=??5$ ，則新邊權為$0+?1?(?5)=4$ 。途中紅色數字為改造后的邊權，黑色數字為改造前的邊權。
   3. 計算全源最短路
   完成邊權改造后，以每個點為起點，運行n輪Heap - Dijkstra算法（n為圖中節點數，這里n = 4 ，不包含虛擬源點0 ），從而求出圖中任意兩點間的最短路。

各個最短路算法分析：

	BFS	Heap-Dijkstra	SPFA	Floyd	Johnson
最短路類型	最少步數	單源	單源	全源	全源
建圖	鄰接矩陣	鄰接表	鄰接表	鄰接矩陣	鄰接表
算法		貪心，松弛	貪心，松弛	插點法	貪心，松弛
優化	隊列	優先隊列	隊列		優先隊列
負邊權		不能	能	能	能
判負環		不能	能	能	能
時間復雜度	O(n + m)	O(mlogm)	O(nm)	O(n3)	O(nmlogm)
圖的大小	大/中 n=10?, m=10?	大/中 n=10?, m=10?	中/小 n=103, m=10?	小 n=102	中/小 n=103, m=103

例題

https://www.luogu.com.cn/problem/P5905

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9;
// 定義邊的結構體，包含目標節點 v 和邊的權重 w
struct edge { int v, w; };
// 鄰接表存儲圖，e[i] 存儲從節點 i 出發的所有邊
vector<edge> e[N];
// vis 數組用于標記節點是否在隊列中，cnt 數組用于記錄每個節點入隊的次數
int vis[N], cnt[N];
// h 數組用于存儲從虛擬源點到各節點的最短路，d 數組用于存儲從某個源點到各節點的最短路
long long h[N], d[N];
int n, m;// 使用 SPFA 算法計算從虛擬源點 0 到其他所有節點的最短路
void spfa() {// 定義一個隊列用于存儲待處理的節點queue<int> q;// 初始化 h 數組為一個很大的值，memset(63) 相當于將每個元素初始化為一個較大的數memset(h, 63, sizeof h);memset(vis, false, sizeof vis);// 虛擬源點到自身的距離為 0h[0] = 0;// 標記虛擬源點在隊列中vis[0] = 1;// 將虛擬源點加入隊列q.push(0);while (q.size()) {int u = q.front();q.pop();// 標記該節點不在隊列中vis[u] = 0;// 遍歷從節點 u 出發的所有邊for (auto ed : e[u]) {// 獲取目標節點 v 和邊的權重 wint v = ed.v, w = ed.w;// 如果通過節點 u 到達節點 v 的距離更短，則更新 h[v]if (h[v] > h[u] + w) {h[v] = h[u] + w;// 更新節點 v 的入隊次數cnt[v] = cnt[u] + 1;// 如果某個節點入隊次數超過 n 次，說明存在負環if (cnt[v] > n) {printf("-1\n");// 存在負環，程序退出exit(0);}// 如果節點 v 不在隊列中，則將其加入隊列if (!vis[v]) {q.push(v);vis[v] = 1;}}}}
}// 使用 Dijkstra 算法計算從源點 s 到其他所有節點的最短路
void dijkstra(int s) {// 定義一個優先隊列，用于存儲待處理的節點，按照距離從小到大排序priority_queue<pair<long long, int>> q;// 初始化 d 數組為無窮大for (int i = 1; i <= n; i++) {d[i] = INF;}// 初始化 vis 數組為 false，表示所有節點都未被處理memset(vis, false, sizeof vis);// 源點到自身的距離為 0d[s] = 0;// 將源點加入優先隊列q.push({ 0,s });// 當優先隊列不為空時進行處理while (q.size()) {// 取出隊首節點int u = q.top().second;q.pop();// 如果該節點已經被處理過，則跳過if (vis[u]) {continue;}// 標記該節點已被處理vis[u] = 1;// 遍歷從節點 u 出發的所有邊for (auto ed : e[u]) {// 獲取目標節點 v 和邊的權重 wint v = ed.v;int w = ed.w;// 如果通過節點 u 到達節點 v 的距離更短，則更新 d[v]if (d[v] > d[u] + w) {d[v] = d[u] + w;// 如果節點 v 未被處理，則將其加入優先隊列if (!vis[v]) {q.push({ -d[v],v });}}}}
}int main() {cin >> n >> m;// 輸入每條邊的信息，并將其加入鄰接表for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;e[a].push_back({ b,c });}// 從虛擬源點 0 向其他所有節點添加一條邊權為 0 的邊for (int i = 1; i <= n; i++) {e[0].push_back({ i,0 });//加虛擬邊}// 調用 SPFA 算法計算從虛擬源點到其他所有節點的最短路spfa();// 對圖的邊權進行重新計算，確保所有邊權非負for (int u = 1; u <= n; u++) {for (auto& ed : e[u]) {ed.w += h[u] - h[ed.v];//構造新邊}}// 以每個節點為源點，調用 Dijkstra 算法計算最短路for (int i = 1; i <= n; i++) {dijkstra(i);long long ans = 0;// 計算從源點 i 到其他所有節點的最短路的加權和for (int j = 1; j <= n; j++) {// 如果節點 j 不可達，則使用無窮大計算if (d[j] == INF) {ans += (long long)j * INF;}// 否則，使用實際距離計算else {ans += (long long)j * (d[j] + h[j] - h[i]);}}// 輸出結果printf("%lld\n", ans);}return 0;
}