一，BFS層次最短路
/*題目描述
題目描述
給出一個 N 個頂點 M 條邊的無向無權圖，頂點編號為 1～N。
問從頂點 1 開始，到其他每個點的最短路有幾條。
輸入格式
第一行包含 2 個正整數 N,M，為圖的頂點數與邊數。
接下來 M 行，每行 2 個正整數 x,y，表示有一條連接頂點 x 和頂點 y 的邊，請注意可能有自環與重邊。
輸出格式
共 N 行，每行一個非負整數，第 i 行輸出從頂點 1 到頂點 i 有多少條不同的最短路，由于答案有可能會很大，
你只需要輸出 ans mod 100003 后的結果即可。如果無法到達頂點 i 則輸出 0。
https://www.luogu.com.cn/problem/P1144
https://vjudge.net/contest/737432#problem/D
*/#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const long long mod = 1e5 + 3;int n, m, s, dis[maxn];
long long cnt[maxn];
vector<int> g[maxn];void bfs() {queue<int> que;fill(dis+1, dis+n+1, -1);dis[1] = 0;cnt[1] = 1;que.push(1);while (!que.empty()) {int u = que.front();que.pop();for (auto v : g[u]) {if (dis[v] == -1) {dis[v] = dis[u] + 1;cnt[v] = cnt[u]; // u = 3que.push(v);}else if (dis[v] == dis[u] + 1) // u == 7cnt[v] = (cnt[v] + cnt[u]) % mod;}}
}int main() {scanf("%d%d", &n, &m);for (int i = 0, u, v; i < m; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}bfs();for (int i = 1; i <= n; i++)printf("%lld\n", cnt[i]);return 0;
}我認為BFS層次最短路最關鍵的特征有兩個，首先是層次（通過隊列先入先出的特征來實現），其次是邊權為1，如果邊權不是1的話那么同樣走一步就會有的步伐大有的步伐小，根本無法判斷那條路最短。
二，dijkstra單源最短路
/*題目描述
題目描述
如題，給出一個有向圖，請輸出從某一點出發到所有點的最短路徑長度。
輸入格式
第一行包含三個整數 n,m,s，分別表示點的個數、有向邊的個數、出發點的編號。
接下來 m 行每行包含三個整數 u,v,w，表示一條 u→v 的，長度為 w 的邊。
輸出格式
輸出一行 n 個整數，第 i 個表示 s 到第 i 個點的最短路徑，若不能到達則輸出 2^31?1。
https://www.luogu.com.cn/problem/P4779
https://vjudge.net/contest/737432#problem/B
*/#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, inf = INT_MAX;
int n, m, s, dis[maxn];
bool vis[maxn];
struct Edge {int v, w;
};
vector<Edge> edge[maxn];struct Node {int u, dist;bool operator < (const Node& b) const {return dist > b.dist; // 小根堆（優先隊列默認是大根堆，這里取反）}
};
priority_queue<Node> quenode;void dijkstra(int s) {fill(dis + 1, dis + n + 1, inf);dis[s] = 0;quenode.push({ s, 0 });while (!quenode.empty()) {int u = quenode.top().u;quenode.pop();if (!vis[u]) { // 已經處理過的節點直接跳過vis[u] = true;for (auto& e : edge[u]) {int v = e.v;int w = e.w;// 松弛操作：如果通過u到v的路徑更短，則更新if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;quenode.push({ v, dis[v] });}}}}
}int main() {scanf("%d%d%d", &n, &m, &s);for (int i = 0, u, v, w; i < m; i++) {scanf("%d%d%d", &u, &v, &w);edge[u].push_back({ v, w });}dijkstra(s);for (int i = 1; i <= n; i++)printf("%d ", dis[i]);return 0;
}反觀dijstra在這方面就有優異的表現，dijstra算法通過根據邊權進行提前排序，以及優先隊列存儲被更新過的新路徑進行高效且簡單地求出單源最短路，但可以說正是因為dijstra的高效，它無法處理負權邊的問題，這是因為dijstra高效在 vis 數組會把一些節點視作“永久節點”，即不會出現更短的路徑通向該節點因此“永久節點”不會再被更新，但是負權邊的存在使得“永久節點”不再永久，有可能會出現比通向該節點的“最短邊”更短的邊，另外，如果一個環的權值之和是負的那么通過這個環的“代價”將變成“動力”，因此會出現死循環。
三，Floyd算法求多源最短路
/*題目描述
給出一張由 n 個點 m 條邊組成的無向圖。
求出所有點對 (i,j) 之間的最短路徑。
輸入格式
第一行為兩個整數 n,m，分別代表點的個數和邊的條數。
接下來 m 行，每行三個整數 u,v,w，代表 u,v 之間存在一條邊權為 w 的邊。
輸出格式
輸出 n 行每行 n 個整數。
第 i 行的第 j 個整數代表從 i 到 j 的最短路徑。
https://www.luogu.com.cn/problem/B3647
*/#include <bits/stdc++.h>
using namespace std;
int n, m, dis[105][105];
int main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dis[i][j] = (i == j) ? 0 : 1e9;while (m--) {int u, v, w;cin >> u >> v >> w;dis[u][v] = dis[v][u] = min(dis[u][v], w);}for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++)cout << dis[i][j] << " ";cout << endl;}return 0;
}其實 Floyd 算法更像是動態規劃，邏輯上很好理解，dis[i][j] 代表了從 i 到 j 的最短路，然后分類討論途徑第 k 條路徑的最短路，但是我更想介紹的是Floyd算法的一類衍生問題，傳遞閉包。
附：傳遞閉包
/*題目描述
https://www.luogu.com.cn/problem/B3611
*/
#include <bits/stdc++.h>
using namespace std;
int n, a;
bitset<100> f[100];
// f[i][j] = 1/0 目前能不能從i到j
int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {scanf("%d", &a);if (a)f[i][j] = 1;}}for (int i = 0; i < n; i++) // 經過編號 [0,i] 的點for (int j = 0; j < n; j++) // 對于頂點j來說if (f[j][i])f[j] |= f[i];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)printf("%d ", (int)f[i][j]);putchar('\n');}return 0;
}簡單來說傳遞閉包問題就是判斷任意兩個節點之間是否可以到達，與Floyd相同的地方在于都是多源的問題，不同點在于數組只會存儲 0 或 1 ，所以我們可以用bitset優化一下，大約省了幾十倍的空間，最核心的段落就是if (f[j][i]) f[j] |= f[i]; 這一判斷，當發現 i 與 j 可到達時，i 所能到達的節點 j 也能到達，反之亦然。
四，bellman-ford算法
/*題目描述
https://www.luogu.com.cn/problem/P3385
*/
#include <bits/stdc++.h>
using namespace std;
// bellman-ford判負環
const int maxn = 2e3 + 5, maxm = 3e3 + 5, inf = (1 << 29);int T, n, m, dis[maxn];
struct Edge {int u, v, w;
} e[maxm];int main() {scanf("%d", &T);while (T--) {scanf("%d%d", &n, &m);dis[1] = 0;fill(dis + 2, dis + n + 1, inf);for (int i = 0; i < m; i++)scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);// bellman-fordint c = 0;for (int i = 1; i <= 2 * n; i++) {for (int j = 0; j < m; j++) {int u = e[j].u;int v = e[j].v;int w = e[j].w;if (dis[u] < inf && dis[v] > dis[u] + w)c = i, dis[v] = dis[u] + w;if (w >= 0 && dis[v] < inf && dis[u] > dis[v] + w)c = i, dis[u] = dis[v] + w;}if (c != i)break;}puts(c == 2 * n ? "YES" : "NO");}return 0;
}理論上來說，同為單源最短路算法，所有dijkstra算法能用的題目bellman-ford也能用，可以理解為一個更容易實現，一個更全面，以上是一個一般的bellman-ford算法，我一般不用，以下是一個隊列優化后的bellman-ford算法，它還有一個響當當的名字（SPFA）。
附：SPFA
#include <bits/stdc++.h>
using namespace std;
// SPFA判負環
const int maxn = 2e3 + 5, maxm = 3e3 + 5, inf = (1<<29);int T, n, m, dis[maxn], cnt[maxn];
bool inq[maxn];
struct Edge {int v, w;
};
vector<Edge> g[maxn];void init() {for (int i = 1; i <= n; i++)g[i].clear();
}bool spfa() {queue<int> que;dis[1] = cnt[1] = 0;fill(dis + 2, dis + n + 1, inf);que.push(1);fill(inq + 1, inq + n + 1, false);inq[1] = true;while (!que.empty()) {int u = que.front();que.pop();inq[u] = false;for (auto &g : g[u]) {if (dis[g.v] > dis[u] + g.w) {dis[g.v] = dis[u] + g.w;cnt[g.v] = cnt[u] + 1;if (cnt[g.v] >= n)return true;if (!inq[g.v])inq[g.v] = true, que.push(g.v);}}}return false;
}int main() {scanf("%d", &T);while (T--) {scanf("%d%d", &n, &m);init();for (int i = 0, u, v, w; i < m; i++) {scanf("%d%d%d", &u, &v, &w);g[u].push_back({v, w});if (w >= 0)g[v].push_back({u, w});}puts(spfa() ? "YES" : "NO");}return 0;
}?bellman-ford 算法和SPFA算法的核心都是“松弛”（意思就是變短），簡單點來說就是，只有一個終端節點（隊頭節點）的最短距離被更新（松弛）過之后，它將作為開始節點入隊。因為在一個有 n 個頂點的圖中，最短路徑最多包含 n-1 條邊（否則必然存在環），所以我們只需要開一個數組 cnt 記錄每條路徑經過幾個節點，當 cnt[i]?大于等于 n 時說明存在環，而又由于我們算的是最短路徑，正常情況下來講算最短路是不可能算出環的，如果出現環那就一定是負環，詳見代碼。
)
