Bellman-Ford算法求单源最短路径问题

题目描述
给定一个带权有向图，其中边的权重可以是负数，以及一个源顶点s。要求找出从源顶点s到图中所有其他顶点的最短路径。如果图中存在从s可达的负权环，则算法应能检测到这一情况。

解题过程

1. 问题分析
   在带权图中，若存在负权边，Dijkstra算法可能失效，因为它基于贪心策略，假设路径权重非负。Bellman-Ford算法通过动态规划思想，允许边权为负，并能检测负权环。

2. 算法核心思想
   对图中所有边进行V-1轮松弛操作（V为顶点数），确保最短路径最多包含V-1条边的假设下找到最优解。再额外进行一轮松弛，若仍能更新距离，则说明存在负权环。

3. 步骤详解

   • 初始化：将源顶点s的距离设为0，其他顶点距离设为无穷大。
   • 松弛操作：对每条边(u, v)，检查是否可通过u缩短v的距离：
     若 dist[u] + w(u, v) < dist[v]，则更新 dist[v] = dist[u] + w(u, v)。
   • 多轮松弛：重复上述松弛操作V-1轮，确保所有可能的最短路径被覆盖。
   • 负权环检测：再进行第V轮松弛，若任何距离仍可被更新，则存在从s可达的负权环。

4. 示例演示
   假设图有顶点{A, B, C, D}，边及权重：A→B(4), A→C(5), B→C(-2), C→D(3), D→B(-1)。源点为A。

   • 初始化：dist[A]=0, 其他为∞。
   • 第1轮松弛：更新B=4, C=5；通过B→C更新C=2。
   • 第2轮松弛：通过C→D更新D=5；通过D→B更新B=4（无变化）。
   • 第3轮松弛：无更新。最终距离：A=0, B=4, C=2, D=5。
   • 第4轮检测：无更新，故无负权环。

5. 复杂度与注意事项

   • 时间复杂度：O(V·E)，适合稀疏图。
   • 关键点：V-1轮松弛保证最短路径存在时的正确性；第V轮用于负环检测。

通过以上步骤，Bellman-Ford算法能有效处理含负权边的最短路径问题，并识别负权环。