最短路径算法：Bellman-Ford算法 Bellman-Ford算法是一种用于在带权图中计算单源最短路径的算法。它能够处理图中包含负权边的情况，并且可以检测是否存在从源点可达的负权环。该算法适用于有向图和无向图（无向图的边可视为两条方向相反的有向边），但在无向图中，负权边会直接形成负权环。 算法描述 设图G有V个顶点和E条边，源点为s。算法通过松弛（Relaxation）操作逐步逼近最短路径。核心思想是：最短路径最多包含V-1条边（因为简单路径不可能有环，否则路径会更长或陷入负环），因此进行V-1轮松弛操作，每轮尝试对所有的边进行松弛。如果在V-1轮后还能继续松弛，则说明图中存在从源点可达的负权环。 解题过程循序渐进讲解 初始化 创建一个距离数组 dist ，长度为V（顶点数）。 dist[v] 表示从源点s到顶点v的当前最短距离估计值。 初始化 dist[s] = 0 ，表示源点到自身的距离为0。 对于所有其他顶点v（v ≠ s），初始化 dist[v] = ∞ （一个很大的数，表示无穷大，即尚未找到路径）。 松弛操作（Relaxation） 松弛是算法的核心操作。对于一条有向边(u, v)，其权重为w，松弛操作检查是否可以通过u来缩短s到v的路径。 具体过程：如果 dist[u] + w < dist[v] ，则更新 dist[v] = dist[u] + w 。这表示“如果从s到u，再经过边(u, v)到v的路径比当前已知的s到v的路径更短，则采用这条更短的路径”。 松弛操作是动态规划思想的体现，它不断地优化（缩短）到达每个顶点的路径估计值。 主循环：进行V-1轮松弛 对图中的所有边，进行V-1轮松弛操作。 为什么是V-1轮？因为任意两点之间的最短路径最多包含V-1条边（假设图中没有负权环）。进行V-1轮松弛足以保证所有可能的最短路径都被考虑到。 每一轮松弛，算法都会尝试将最短路径的边数扩展一条。例如，第一轮松弛后，我们找到了所有从s出发、经过最多1条边可到达的顶点的最短路径；第二轮后，找到了经过最多2条边的最短路径，以此类推。 检测负权环 完成V-1轮松弛后，再进行一轮额外的松弛操作（即第V轮松弛）。 如果在这一轮中，任何一条边(u, v)仍然满足 dist[u] + w < dist[v] ，则说明图中存在从源点s可达的负权环。 原因：在V-1轮后，最短路径应该已经确定。如果还能被松弛，意味着存在一条路径，它可以通过绕行一个负权环来无限地减小路径的总权重。 算法复杂度 时间复杂度：O(V* E)。需要进行V-1轮松弛，每轮需要遍历所有的E条边。 空间复杂度：O(V)。主要用于存储距离数组 dist 。 举例说明 考虑一个有向图，顶点集为{0, 1, 2, 3}，源点为0。边集为：0->1（权重4），0->2（权重5），1->2（权重-2），2->1（权重1），1->3（权重6），2->3（权重3）。 初始化 ： dist = [0, ∞, ∞, ∞] 第一轮松弛 （遍历所有边）： 边0->1： dist[0]+4=4 < ∞ ，更新 dist[1]=4 边0->2： dist[0]+5=5 < ∞ ，更新 dist[2]=5 边1->2： dist[1]+(-2)=2 < 5 ，更新 dist[2]=2 边2->1： dist[2]+1=3 < 4 ，更新 dist[1]=3 边1->3： dist[1]+6=9 < ∞ ，更新 dist[3]=9 边2->3： dist[2]+3=5 < 9 ，更新 dist[3]=5 第一轮后 dist = [0, 3, 2, 5] 第二轮松弛 ： 边0->1： 0+4=4 > 3 ，不更新 边0->2： 0+5=5 > 2 ，不更新 边1->2： 3+(-2)=1 < 2 ，更新 dist[2]=1 边2->1： 1+1=2 < 3 ，更新 dist[1]=2 边1->3： 2+6=8 > 5 ，不更新 边2->3： 1+3=4 < 5 ，更新 dist[3]=4 第二轮后 dist = [0, 2, 1, 4] 第三轮松弛 （V=4，所以进行V-1=3轮）： 边0->1： 0+4=4 > 2 ，不更新 边0->2： 0+5=5 > 1 ，不更新 边1->2： 2+(-2)=0 < 1 ，更新 dist[2]=0 边2->1： 0+1=1 < 2 ，更新 dist[1]=1 边1->3： 1+6=7 > 4 ，不更新 边2->3： 0+3=3 < 4 ，更新 dist[3]=3 第三轮后 dist = [0, 1, 0, 3] 检测负权环 （第四轮松弛）： 检查所有边，看是否还能松弛。 边1->2： 1+(-2) = -1 < 0 ，可以松弛！说明图中存在从源点0可达的负权环（例如路径1->2->1，权重为-2+1=-1，是一个负环）。 通过这个例子，你可以看到算法如何逐步优化距离估计，并在最后检测出负权环。如果图中没有负权环，那么V-1轮后的 dist 数组就是最终的最短路径结果。