Bellman-Ford最短路径算法

图算法

Bellman-Ford算法是一种单源最短路径算法,与Dijkstra算法不同,它能够处理带有负权边的图,还能检测负权环的存在。

时间复杂度:最佳 O(E) | 平均 O(V × E) | 最差 O(V × E)
空间复杂度:O(V)
图类型:加权图

应用场景/前提条件

  • 可以处理负权边的图
  • 能够检测负权环

算法讲解

Bellman-Ford最短路径算法

介绍

Bellman-Ford算法是一种用于计算带权图中单源最短路径的算法。与Dijkstra算法不同,Bellman-Ford算法可以处理含有负权边的图,能够检测负权环(负权环会导致最短路径无限减小)。该算法由Richard Bellman和Lester Ford分别独立发现,因此以他们的名字命名。

算法步骤

  1. 初始化:将起始顶点的距离设为0,其他所有顶点的距离设为无穷大
  2. 松弛操作:对图中的所有边进行V-1次松弛操作(V为顶点数)
  3. 负环检测:再对所有边进行一次松弛操作,如果仍有距离更新,则说明图中存在负权环

松弛操作的定义是:对于边(u,v),如果 dist[v] > dist[u] + weight(u,v),则更新 dist[v] = dist[u] + weight(u,v)。

算法详解

假设有一个包含5个顶点(A-E)的有向加权图,边的关系及权重如下:

  • A到B,权重为6
  • A到C,权重为4
  • A到D,权重为5
  • B到E,权重为-1
  • C到B,权重为-2
  • C到E,权重为3

...