目录引入一、经典单源最短路径1.普通BFS代码2.Dijkstra迪杰斯特拉算法代码3.Bellman-Ford代码4.SPFA代码二、多源全源最短路径1.Floyd-Warshall代码2.Johnson代码总结例题基础提高引入这是一张无向图接下来尝试给边上加上一些箭头你就得到了一张有向图在拓展一点给每条边赋予边权你就得到了一张有向带权图我们可以假设边权就是距离那么我们就得到了一张地图。接下来抛出一个问题我们该如何求任意两点或某个确定点与其他点的最短路径呢这时就要用到单/多源最短路径算法也就是本文的主题。最短路径算法有许多通常会根据不同的场景来选择不同的最短路径算法。一、经典单源最短路径单源最短路径指的是求某一个确定的点到其他所有点的最短距离。1.普通BFS常用于无权图所有边权重相等核心思想是逐层向外扩展首次访问即最短路径。代码int dist[MAXN]; int q[MAXN]; // 数组模拟队列 void bfs(int n, int src) { memset(dist, -1, sizeof(dist)); int front 0, rear 0; dist[src] 0; q[rear] src; while (front rear) { int u q[front]; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; if (dist[v] -1) { dist[v] dist[u] 1; q[rear] v; } } } }2.Dijkstra迪杰斯特拉算法常用于非负权图是一种贪心算法每次选取离起点最近且未处理的节点进行松弛。通常会使用优先队列优化适合稀疏图。代码#include queue using PII pairint, int; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int n, int src) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); priority_queuePII, vectorPII, greaterPII pq; dist[src] 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i], w weight[i]; if (!vis[v] dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }3.Bellman-Ford更适用于非负权稠密图核心思路是对每条边进行轮松弛操作。较少使用。代码struct Edge { int u, v, w; } edges[MAXM]; int dist[MAXN]; bool bellman_ford(int n, int m, int src) { memset(dist, 0x3f, sizeof(dist)); dist[src] 0; // 松弛 n-1 次 for (int i 1; i n - 1; i) { bool updated false; for (int j 1; j m; j) { int u edges[j].u, v edges[j].v, w edges[j].w; if (dist[u] ! INF dist[v] dist[u] w) { dist[v] dist[u] w; updated true; } } if (!updated) break; } // 检测负环 for (int j 1; j m; j) { int u edges[j].u, v edges[j].v, w edges[j].w; if (dist[u] ! INF dist[v] dist[u] w) { return false; // 存在负环 } } return true; }4.SPFA在所有最短路径算法中最“全面发展”的一个但在部分特殊情况不如某些其他算法。核心思路是用队列维护发生松弛的节点减少无效松弛。稀疏图极快但很有可能被出题者卡数据导致退化为。代码int dist[MAXN]; bool inQueue[MAXN]; int q[MAXN]; // 队列 int cnt[MAXN]; // 入队次数检测负环 bool spfa(int n, int src) { memset(dist, 0x3f, sizeof(dist)); memset(inQueue, false, sizeof(inQueue)); memset(cnt, 0, sizeof(cnt)); int front 0, rear 0; dist[src] 0; q[rear] src; inQueue[src] true; while (front rear) { int u q[front]; inQueue[u] false; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i], w weight[i]; if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q[rear] v; inQueue[v] true; cnt[v]; if (cnt[v] n) return false; // 存在负环 } } } } return true; }二、多源全源最短路径1.Floyd-Warshall通常用邻接矩阵实现更适合稠密图只是时间复杂度有些高核心思想为动态规划枚举中间点尝试松弛的路径。代码int g[MAXN][MAXN]; // 邻接矩阵 void floyd(int n) { // 初始化g[i][i]0, 有边g[i][j]w, 无边g[i][j]INF for (int k 1; k n; k) { for (int i 1; i n; i) { if (g[i][k] INF) continue; // 小优化 for (int j 1; j n; j) { if (g[i][j] g[i][k] g[k][j]) { g[i][j] g[i][k] g[k][j]; } } } } }2.Johnson适合稀疏图核心思想为先通过重新赋予非负权重势能法再对每个点跑。代码int h[MAXN]; // 势能 int dist_johnson[MAXN][MAXN]; // 结果矩阵 bool johnson(int n, int m) { // Step 1: 添加超级源点0到所有点边权为0 for (int i 1; i n; i) { addEdge(0, i, 0); } // Step 2: SPFA/Bellman-Ford 计算势能h[] if (!spfa(n 1, 0)) { return false; // 存在负环 } for (int i 1; i n; i) { h[i] dist[i]; } // Step 3: 移除超级源点重新建图 // 实际使用中重新初始化head重新添加原边这里省略 // 新权重 w w h[u] - h[v] (非负) // Step 4: 对每个点跑Dijkstra for (int src 1; src n; src) { // 使用上面的dijkstra函数使用重新赋权后的图 // 结果 dist_johnson[src][v] dist[v] h[v] - h[src] } return true; }总结首先是对各类最短路径算法的详细汇总算法名称时间复杂度适用场景核心思想能否处理负权图密度适用性BFS广度优先搜索O(V E)无权图所有边权重相等逐层向外扩展首次访问即最短路径。不涉及权重稀疏/稠密均可E较小更优Dijkstra优先队列优化O((VE) log V)非负权图最常用贪心策略每次选取离起点最近且未处理的节点进行松弛。不能负权会失效稀疏图更优ElogVBellman-FordO(VE)含负权边的图对每条边进行 V-1 轮松弛操作。能可检测负环稀疏图尚可稠密图极慢SPFA队列优化Bellman-Ford平均 O(E)最坏 O(VE)含负权边且需快速或判断负环用队列维护发生松弛的节点减少无效松弛。能可检测负环稀疏图极快稠密图易退化Floyd-WarshallO(V³)稠密图或需输出所有点对距离动态规划枚举中间点 k尝试松弛 i→j 的路径。能但不能有负环稠密图最优V³与E无关JohnsonO(VE V² log V)稀疏图且含负权边先通过 Bellman-Ford 重新赋予非负权重势能法再对每个点跑 Dijkstra。能但不能有负环稀疏图更优当 E V²/logV 时其次是对算法选择的决策过程1. 无权图 → BFS单源 / 多源BFS全源 2. 非负权图 ├─ 单源 │ ├─ 稀疏图E V²/logV→ Dijkstra优先队列O(ElogV) │ └─ 稠密图E ≈ V² → Dijkstra朴素O(V²) └─ 全源 ├─ 稀疏图 → 对每个点跑Dijkstra堆O(VElogV) └─ 稠密图 → Floyd-Warshall O(V³) 3. 含负权边无负环 ├─ 单源 │ ├─ 稀疏图 → SPFA平均O(E) │ └─ 稠密图 → Bellman-Ford O(VE) 或 SPFA但都会很慢 └─ 全源 ├─ 稀疏图 → Johnson O(VE V²logV) └─ 稠密图 → Floyd-Warshall O(V³)虽慢但实现简单 4. 需要检测负环 ├─ 单源 → Bellman-Ford 或 SPFA └─ 全源 → Floyd-Warshall检测 g[i][i] 0接下来是对于图的密度的判断标准图类型判断标准说明稀疏图E V log V邻接表存储优先队列Dijkstra中等图V E V² / logV两种Dijkstra都可以稠密图E ≈ V²邻接矩阵存储朴素Dijkstra或Floyd完全图E V(V-1)/2必然用朴素Dijkstra或Floyd例题基础洛谷 P2910 [USACO08OPEN] Clear And Present Danger Shttps://www.luogu.com.cn/problem/P2910洛谷 P3371 【模板】单源最短路径弱化版https://www.luogu.com.cn/problem/P3371提高P1144 最短路计数https://www.luogu.com.cn/problem/P1144P2446 [SDOI2010] 大陆争霸https://www.luogu.com.cn/problem/P2446感谢观看有问题欢迎提出 算法系列 | 图论最短路径算法
目录引入一、经典单源最短路径1.普通BFS代码2.Dijkstra迪杰斯特拉算法代码3.Bellman-Ford代码4.SPFA代码二、多源全源最短路径1.Floyd-Warshall代码2.Johnson代码总结例题基础提高引入这是一张无向图接下来尝试给边上加上一些箭头你就得到了一张有向图在拓展一点给每条边赋予边权你就得到了一张有向带权图我们可以假设边权就是距离那么我们就得到了一张地图。接下来抛出一个问题我们该如何求任意两点或某个确定点与其他点的最短路径呢这时就要用到单/多源最短路径算法也就是本文的主题。最短路径算法有许多通常会根据不同的场景来选择不同的最短路径算法。一、经典单源最短路径单源最短路径指的是求某一个确定的点到其他所有点的最短距离。1.普通BFS常用于无权图所有边权重相等核心思想是逐层向外扩展首次访问即最短路径。代码int dist[MAXN]; int q[MAXN]; // 数组模拟队列 void bfs(int n, int src) { memset(dist, -1, sizeof(dist)); int front 0, rear 0; dist[src] 0; q[rear] src; while (front rear) { int u q[front]; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; if (dist[v] -1) { dist[v] dist[u] 1; q[rear] v; } } } }2.Dijkstra迪杰斯特拉算法常用于非负权图是一种贪心算法每次选取离起点最近且未处理的节点进行松弛。通常会使用优先队列优化适合稀疏图。代码#include queue using PII pairint, int; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int n, int src) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); priority_queuePII, vectorPII, greaterPII pq; dist[src] 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i], w weight[i]; if (!vis[v] dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }3.Bellman-Ford更适用于非负权稠密图核心思路是对每条边进行轮松弛操作。较少使用。代码struct Edge { int u, v, w; } edges[MAXM]; int dist[MAXN]; bool bellman_ford(int n, int m, int src) { memset(dist, 0x3f, sizeof(dist)); dist[src] 0; // 松弛 n-1 次 for (int i 1; i n - 1; i) { bool updated false; for (int j 1; j m; j) { int u edges[j].u, v edges[j].v, w edges[j].w; if (dist[u] ! INF dist[v] dist[u] w) { dist[v] dist[u] w; updated true; } } if (!updated) break; } // 检测负环 for (int j 1; j m; j) { int u edges[j].u, v edges[j].v, w edges[j].w; if (dist[u] ! INF dist[v] dist[u] w) { return false; // 存在负环 } } return true; }4.SPFA在所有最短路径算法中最“全面发展”的一个但在部分特殊情况不如某些其他算法。核心思路是用队列维护发生松弛的节点减少无效松弛。稀疏图极快但很有可能被出题者卡数据导致退化为。代码int dist[MAXN]; bool inQueue[MAXN]; int q[MAXN]; // 队列 int cnt[MAXN]; // 入队次数检测负环 bool spfa(int n, int src) { memset(dist, 0x3f, sizeof(dist)); memset(inQueue, false, sizeof(inQueue)); memset(cnt, 0, sizeof(cnt)); int front 0, rear 0; dist[src] 0; q[rear] src; inQueue[src] true; while (front rear) { int u q[front]; inQueue[u] false; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i], w weight[i]; if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q[rear] v; inQueue[v] true; cnt[v]; if (cnt[v] n) return false; // 存在负环 } } } } return true; }二、多源全源最短路径1.Floyd-Warshall通常用邻接矩阵实现更适合稠密图只是时间复杂度有些高核心思想为动态规划枚举中间点尝试松弛的路径。代码int g[MAXN][MAXN]; // 邻接矩阵 void floyd(int n) { // 初始化g[i][i]0, 有边g[i][j]w, 无边g[i][j]INF for (int k 1; k n; k) { for (int i 1; i n; i) { if (g[i][k] INF) continue; // 小优化 for (int j 1; j n; j) { if (g[i][j] g[i][k] g[k][j]) { g[i][j] g[i][k] g[k][j]; } } } } }2.Johnson适合稀疏图核心思想为先通过重新赋予非负权重势能法再对每个点跑。代码int h[MAXN]; // 势能 int dist_johnson[MAXN][MAXN]; // 结果矩阵 bool johnson(int n, int m) { // Step 1: 添加超级源点0到所有点边权为0 for (int i 1; i n; i) { addEdge(0, i, 0); } // Step 2: SPFA/Bellman-Ford 计算势能h[] if (!spfa(n 1, 0)) { return false; // 存在负环 } for (int i 1; i n; i) { h[i] dist[i]; } // Step 3: 移除超级源点重新建图 // 实际使用中重新初始化head重新添加原边这里省略 // 新权重 w w h[u] - h[v] (非负) // Step 4: 对每个点跑Dijkstra for (int src 1; src n; src) { // 使用上面的dijkstra函数使用重新赋权后的图 // 结果 dist_johnson[src][v] dist[v] h[v] - h[src] } return true; }总结首先是对各类最短路径算法的详细汇总算法名称时间复杂度适用场景核心思想能否处理负权图密度适用性BFS广度优先搜索O(V E)无权图所有边权重相等逐层向外扩展首次访问即最短路径。不涉及权重稀疏/稠密均可E较小更优Dijkstra优先队列优化O((VE) log V)非负权图最常用贪心策略每次选取离起点最近且未处理的节点进行松弛。不能负权会失效稀疏图更优ElogVBellman-FordO(VE)含负权边的图对每条边进行 V-1 轮松弛操作。能可检测负环稀疏图尚可稠密图极慢SPFA队列优化Bellman-Ford平均 O(E)最坏 O(VE)含负权边且需快速或判断负环用队列维护发生松弛的节点减少无效松弛。能可检测负环稀疏图极快稠密图易退化Floyd-WarshallO(V³)稠密图或需输出所有点对距离动态规划枚举中间点 k尝试松弛 i→j 的路径。能但不能有负环稠密图最优V³与E无关JohnsonO(VE V² log V)稀疏图且含负权边先通过 Bellman-Ford 重新赋予非负权重势能法再对每个点跑 Dijkstra。能但不能有负环稀疏图更优当 E V²/logV 时其次是对算法选择的决策过程1. 无权图 → BFS单源 / 多源BFS全源 2. 非负权图 ├─ 单源 │ ├─ 稀疏图E V²/logV→ Dijkstra优先队列O(ElogV) │ └─ 稠密图E ≈ V² → Dijkstra朴素O(V²) └─ 全源 ├─ 稀疏图 → 对每个点跑Dijkstra堆O(VElogV) └─ 稠密图 → Floyd-Warshall O(V³) 3. 含负权边无负环 ├─ 单源 │ ├─ 稀疏图 → SPFA平均O(E) │ └─ 稠密图 → Bellman-Ford O(VE) 或 SPFA但都会很慢 └─ 全源 ├─ 稀疏图 → Johnson O(VE V²logV) └─ 稠密图 → Floyd-Warshall O(V³)虽慢但实现简单 4. 需要检测负环 ├─ 单源 → Bellman-Ford 或 SPFA └─ 全源 → Floyd-Warshall检测 g[i][i] 0接下来是对于图的密度的判断标准图类型判断标准说明稀疏图E V log V邻接表存储优先队列Dijkstra中等图V E V² / logV两种Dijkstra都可以稠密图E ≈ V²邻接矩阵存储朴素Dijkstra或Floyd完全图E V(V-1)/2必然用朴素Dijkstra或Floyd例题基础洛谷 P2910 [USACO08OPEN] Clear And Present Danger Shttps://www.luogu.com.cn/problem/P2910洛谷 P3371 【模板】单源最短路径弱化版https://www.luogu.com.cn/problem/P3371提高P1144 最短路计数https://www.luogu.com.cn/problem/P1144P2446 [SDOI2010] 大陆争霸https://www.luogu.com.cn/problem/P2446感谢观看有问题欢迎提出