Bellman-Ford算法及SPFA算法详解

张

张建站

2026/4/23 6:43:15

10分钟阅读

Bellman–Ford 算法Bellman–Ford 算法用于解决单源最短路径问题适用于包含负权边的图。该算法通过动态规划思想逐步松弛边最终得到从源点到所有其他顶点的最短路径。算法原理Bellman–Ford 算法的核心思想是对所有边进行多次松弛操作。假设图中有 ( V ) 个顶点和 ( E ) 条边算法需要进行 ( V-1 ) 轮松弛操作。每轮松弛操作检查所有边尝试通过当前边缩短源点到目标顶点的距离。松弛操作对于边 ( (u, v) ) 和权重 ( w )如果 ( dist[v] dist[u] w )则更新 ( dist[v] dist[u] w )。负权环检测在完成 ( V-1 ) 轮松弛后再进行一次松弛操作。如果仍能更新某些顶点的距离说明图中存在负权环。伪代码实现struct Edge { int u, v, w; }; bool BellmanFord(int src, int V, vectorEdge edges, vectorint dist) { dist.assign(V, INF); dist[src] 0; for (int i 1; i V; i) { bool updated false; for (const Edge e : edges) { if (dist[e.u] ! INF dist[e.v] dist[e.u] e.w) { dist[e.v] dist[e.u] e.w; updated true; } } if (!updated) break; // 提前终止优化 } // 检查负权环 for (const Edge e : edges) { if (dist[e.u] ! INF dist[e.v] dist[e.u] e.w) { return false; // 存在负权环 } } return true; }时间复杂度分析最坏情况( O(V \times E) )需要进行 ( V-1 ) 轮松弛每轮检查所有 ( E ) 条边。优化空间若某一轮松弛未更新任何距离可提前终止算法。优缺点优点支持负权边。能检测负权环。缺点时间效率较低尤其是稠密图。SPFAShortest Path Faster AlgorithmSPFA 是 Bellman–Ford 算法的优化版本通过队列动态管理待松弛的顶点减少不必要的松弛操作。算法原理SPFA 维护一个队列存储可能需要进行松弛操作的顶点。初始时源点入队。每次从队列中取出顶点 ( u )松弛其所有邻接边 ( (u, v) )。若 ( v ) 的距离被更新且未在队列中则将其加入队列。队列优化避免重复处理无变化的顶点。负权环检测若某个顶点被松弛超过 ( V-1 ) 次说明存在负权环。伪代码实现bool SPFA(int src, int V, vectorvectorpairint, int adj, vectorint dist) { dist.assign(V, INF); dist[src] 0; queueint q; q.push(src); vectorint cnt(V, 0); vectorbool inQueue(V, false); inQueue[src] true; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; if (cnt[v] V - 1) { return false; // 存在负权环 } } } } } return true; }时间复杂度分析平均情况( O(E) )优于 Bellman–Ford 的 ( O(V \times E) )。最坏情况退化为 ( O(V \times E) )例如构造特殊数据使队列频繁更新。优化技巧队列替换为优先队列类似 Dijkstra 算法但需额外处理负权边。SLFSmall Label First优化若新顶点的距离小于队首顶点插入队首而非队尾。优缺点优点在稀疏图上效率显著优于 Bellman–Ford。保留负权边处理能力。缺点最坏时间复杂度与 Bellman–Ford 相同。对构造数据敏感可能退化成高复杂度。对比与选择适用场景Bellman–Ford需检测负权环。边数较少或无需频繁查询。SPFA稀疏图且无负权环。动态图边权可变化。性能差异SPFA 在随机数据上表现优异但竞赛中可能因特殊数据被卡时间。Bellman–Ford 稳定性高适合确定性需求。代码示例完整实现Bellman–Ford 实现#include vector #include climits using namespace std; const int INF INT_MAX; struct Edge { int u, v, w; }; bool BellmanFord(int src, int V, vectorEdge edges, vectorint dist) { dist.assign(V, INF); dist[src] 0; for (int i 1; i V; i) { bool updated false; for (const Edge e : edges) { if (dist[e.u] ! INF dist[e.v] dist[e.u] e.w) { dist[e.v] dist[e.u] e.w; updated true; } } if (!updated) break; } for (const Edge e : edges) { if (dist[e.u] ! INF dist[e.v] dist[e.u] e.w) { return false; } } return true; }SPFA 实现#include queue #include vector #include climits using namespace std; const int INF INT_MAX; bool SPFA(int src, int V, vectorvectorpairint, int adj, vectorint dist) { dist.assign(V, INF); dist[src] 0; queueint q; q.push(src); vectorint cnt(V, 0); vectorbool inQueue(V, false); inQueue[src] true; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; if (cnt[v] V - 1) { return false; } } } } } return true; }总结Bellman–Ford 和 SPFA 是处理负权边最短路径问题的经典算法。Bellman–Ford 通过全局松弛保证正确性而 SPFA 利用队列优化减少冗余计算。实际应用中需根据图特性和需求选择合适的算法。