flowchart TD
A["最短路"] --> B["单源最短路(只有一个起点)"]
A --> C["多源汇最短路"]
B --> D["所有边权都是正数"]
B --> E["存在负权边"]
D --> F["朴素Dijkstra算法
O(n^2) (稠密图常用)"]
D --> G["堆优化版的Dijkstra算法
O(m log n)(稀疏图常用))"]
E --> H["Bellman-Ford
O(nm)
(一般存在次数限制)"]
E --> I["SPFA
一般O(m), 最坏O(nm)
"]
C --> J["Floyd算法
O(n^3)"]
最小生成树与二分图算法结构图：
graph TD
A["最小生成树"] --> B["普利姆算法 (Prim)"]
A --> C["克鲁斯卡尔算法 (Kruskal) O(m log m)"]
B --> D["朴素版Prim
O(n^2)"]
B --> E["堆优化版Prim
O(m log n)"]
F["二分图"] --> G["染色法
O(n + m)"]
F --> H["匈牙利算法
O(mn), 实际运行一般远小于"]
朴素版 Dijkstra
适用于：边权全为正的稠密图（m≈n2 ），使用邻接矩阵存储。
思路
1 2 3 4
Dijkstra 是基于贪心策略的单源最短路算法，要求所有边权为正。 1. 维护集合 S：S 中的点已确定最短路径。 2. 初始化：源点 dist[1] = 0，其余为 INF。 3. 重复 n 次：从 S 外选出 dist 最小的点 t（贪心选择），将 t 加入 S（此时 dist[t] 已是最短路），再用 t 松弛其所有邻接点（尝试通过 t 缩短其他点的距离）。
for (int i = 1; i <= n; i++) { // 在未确定最短路的点中找 dist 最小的 int t = -1; for (int j = 1; j <= n; j++) if (!visited[j] && (t == -1 || dist[j] < dist[t])) t = j;
visited[t] = true; // 加入集合 S，最短路已确定
// 用 t 更新所有邻接点（邻接矩阵遍历所有点） for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]); }
while (m--) { int x, y, c; scanf("%d%d%d", &x, &y, &c); add(x, y, c); }
cout << dijkstra() << endl;
return0; }
Bellman-Ford 算法
适用于：存在负权边、限制路径边数、检测负环前驱
思路
1 2 3 4
Bellman-Ford 算法通过“松弛操作”对所有边进行最多 k 轮更新（k 为允许的最多边数）。 1. 初始化：源点距离为 0，其余为无穷大。 2. 进行 k 次循环，每次用上一轮的距离（用备份数组 back 保证不发生“串联更新”）去尝试松弛每条边。 3. 若某轮没有发生任何更新，可提前终止（但通常不加，因 k 有限）。
intbellman_ford(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i++) { // 最多 k 条边 memcpy(back, dist, sizeof dist); // 备份上一轮结果 for (int j = 0; j < m; j++) { int a = e[j].a, b = e[j].b, w = e[j].w; dist[b] = min(dist[b], back[a] + w); // 用 back[a] 防止串联 } } // 因为可能存在负权边，即使不连通也可能被更新到略小于 INF，故用 INF/2 判断 if (dist[n] > 0x3f3f3f3f / 2) return-1; return dist[n]; }
intmain(){ cin >> n >> m >> k; for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; e[i] = {a, b, w}; } int res = bellman_ford(); if (res == -1) puts("impossible"); else cout << res << endl; return0; }
while (q.size()) { int t = q.front(); q.pop(); st[t] = false; // 出队后允许再次入队
for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { // 未在队列中才入队 q.push(j); st[j] = true; } } } } // SPFA 只更新与源点连通的点，不连通则保持 INF if (dist[n] == 0x3f3f3f3f) return-1; return dist[n]; }
intmain(){ cin >> n >> m; memset(h, -1, sizeof h); while (m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } int res = spfa(); if (res == -1) puts("impossible"); else cout << res << endl; return0; }
int res = 0; for (int i = 0; i < n; i++) { // 找未加入 MST 中距离最小的点 int t = -1; for (int j = 1; j <= n; j++) if (!st[j] && (t == -1 || dt[j] < dt[t])) t = j;
// 若最小距离仍为 INF，说明图不连通 if (dt[t] == INF) return INF;
st[t] = true; res += dt[t];
// 用 t 更新其他点到 MST 的距离 for (int j = 1; j <= n; j++) if (!st[j]) // 只更新未加入 MST 的点 dt[j] = min(dt[j], g[t][j]); } return res; }
intmain(){ cin >> n >> m; memset(g, 0x3f, sizeof g);
while (m--) { int a, b, w; cin >> a >> b >> w; // 无向图，保留重边中的最小值 g[a][b] = g[b][a] = min(g[a][b], w); }
int res = prim(); if (res == INF) puts("impossible"); else cout << res << endl; return0; }
Kruskal 算法
适用于：稀疏图（m≪n2），使用边集数组 + 并查集
思路
1 2 3 4
Kruskal 算法基于贪心 + 并查集： 1. 将所有边按权重从小到大排序； 2. 依次枚举每条边 (a, b, w)：若 a 和 b 不在同一连通块（find(a) != find(b)），则加入 MST且合并 a、b 所在集合，累加 w； 3. 若最终 MST 边数 = n - 1，则成功；否则图不连通。
intkruskal(){ // 初始化并查集：每个点自成一集合 for (int i = 1; i <= n; i++) p[i] = i;
sort(edges, edges + m); // 按边权排序
int res = 0, cnt = 0; // cnt: 当前 MST 边数 for (int i = 0; i < m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; if (find(a) != find(b)) { p[find(a)] = find(b); // 合并集合 res += w; cnt++; } } // 树有 n 个点需 n-1 条边 if (cnt == n - 1) return res; return INF; }
intmain(){ cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; edges[i] = {a, b, w}; }
int res = kruskal(); if (res == INF) puts("impossible"); else cout << res << endl; return0; }