Bellman-Ford 單源最短路徑算法 - gaochundong－IT工程師數位筆記本

文章出處

Bellman-Ford 算法是一種用于計算帶權有向圖中單源最短路徑（SSSP：Single-Source Shortest Path）的算法。該算法由 Richard Bellman 和 Lester Ford 分別發表于 1958 年和 1956 年，而實際上 Edward F. Moore 也在 1957 年發布了相同的算法，因此，此算法也常被稱為 Bellman-Ford-Moore 算法。

Bellman-Ford 算法和 Dijkstra 算法同為解決單源最短路徑的算法。對于帶權有向圖 G = (V, E)，Dijkstra 算法要求圖 G 中邊的權值均為非負，而 Bellman-Ford 算法能適應一般的情況（即存在負權邊的情況）。一個實現的很好的 Dijkstra 算法比 Bellman-Ford 算法的運行時間要低。

Bellman-Ford 算法采用動態規劃（Dynamic Programming）進行設計，實現的時間復雜度為 O(V*E)，其中 V 為頂點數量，E 為邊的數量。Dijkstra 算法采用貪心算法（Greedy Algorithm）范式進行設計，普通實現的時間復雜度為 O(V²)，若基于 Fibonacci heap 的最小優先隊列實現版本則時間復雜度為 O(E + VlogV)。

Bellman-Ford 算法描述：

創建源頂點 v 到圖中所有頂點的距離的集合 distSet，為圖中的所有頂點指定一個距離值，初始均為 Infinite，源頂點距離為 0；
計算最短路徑，執行 V - 1 次遍歷；
- 對于圖中的每條邊：如果起點 u 的距離 d 加上邊的權值 w 小于終點 v 的距離 d，則更新終點 v 的距離值 d；
檢測圖中是否有負權邊形成了環，遍歷圖中的所有邊，計算 u 至 v 的距離，如果對于 v 存在更小的距離，則說明存在環；

偽碼實現如下：

1 BELLMAN-FORD(G, w, s)
2   INITIALIZE-SINGLE-SOURCE(G, s)
3   for i  1 to |V[G]| - 1
4        do for each edge (u, v)  E[G]
5             do RELAX(u, v, w)
6   for each edge (u, v)  E[G]
7        do if d[v] > d[u] + w(u, v)
8             then return FALSE
9   return TRUE

Bellman-Ford 算法的運行時間為 O(V*E)，因為第 2 行的初始化占用了 Θ(V)，第 3-4 行對邊進行了 V - 1 趟操作，每趟操作的運行時間為 Θ(E)。第 6-7 行的 for 循環運行時間為 O(E)。

例如，下面的有向圖 G 中包含 5 個頂點和 8 條邊。假設源點為 A。初始化 distSet 所有距離為 INFI，源點 A 為 0。

由于圖中有 5 個頂點，按照步驟 1 需要遍歷 4 次，第一次遍歷的結果如下。

第二次遍歷的結果如下。

以此類推可以得出完全遍歷的結果。

C# 代碼實現：

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 
  5 namespace GraphAlgorithmTesting
  6 {
  7   class Program
  8   {
  9     static void Main(string[] args)
 10     {
 11       int[,] graph = new int[9, 9]
 12       {
 13         {0, 4, 0, 0, 0, 0, 0, 8, 0},
 14         {4, 0, 8, 0, 0, 0, 0, 11, 0},
 15         {0, 8, 0, 7, 0, 4, 0, 0, 2},
 16         {0, 0, 7, 0, 9, 14, 0, 0, 0},
 17         {0, 0, 0, 9, 0, 10, 0, 0, 0},
 18         {0, 0, 4, 0, 10, 0, 2, 0, 0},
 19         {0, 0, 0, 14, 0, 2, 0, 1, 6},
 20         {8, 11, 0, 0, 0, 0, 1, 0, 7},
 21         {0, 0, 2, 0, 0, 0, 6, 7, 0}
 22       };
 23 
 24       Graph g = new Graph(graph.GetLength(0));
 25       for (int i = 0; i < graph.GetLength(0); i++)
 26       {
 27         for (int j = 0; j < graph.GetLength(1); j++)
 28         {
 29           if (graph[i, j] > 0)
 30             g.AddEdge(i, j, graph[i, j]);
 31         }
 32       }
 33 
 34       Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
 35       Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
 36       Console.WriteLine();
 37 
 38       int[] distSet = g.BellmanFord(0);
 39       Console.WriteLine("Vertex\t\tDistance from Source");
 40       for (int i = 0; i < distSet.Length; i++)
 41       {
 42         Console.WriteLine("{0}\t\t{1}", i, distSet[i]);
 43       }
 44 
 45       // build a directed and negative weighted graph
 46       Graph directedGraph = new Graph(5);
 47       directedGraph.AddEdge(0, 1, -1);
 48       directedGraph.AddEdge(0, 2, 4);
 49       directedGraph.AddEdge(1, 2, 3);
 50       directedGraph.AddEdge(1, 3, 2);
 51       directedGraph.AddEdge(1, 4, 2);
 52       directedGraph.AddEdge(3, 2, 5);
 53       directedGraph.AddEdge(3, 1, 1);
 54       directedGraph.AddEdge(4, 3, -3);
 55 
 56       Console.WriteLine();
 57       Console.WriteLine("Graph Vertex Count : {0}", directedGraph.VertexCount);
 58       Console.WriteLine("Graph Edge Count : {0}", directedGraph.EdgeCount);
 59       Console.WriteLine();
 60 
 61       int[] distSet1 = directedGraph.BellmanFord(0);
 62       Console.WriteLine("Vertex\t\tDistance from Source");
 63       for (int i = 0; i < distSet1.Length; i++)
 64       {
 65         Console.WriteLine("{0}\t\t{1}", i, distSet1[i]);
 66       }
 67 
 68       Console.ReadKey();
 69     }
 70 
 71     class Edge
 72     {
 73       public Edge(int begin, int end, int weight)
 74       {
 75         this.Begin = begin;
 76         this.End = end;
 77         this.Weight = weight;
 78       }
 79 
 80       public int Begin { get; private set; }
 81       public int End { get; private set; }
 82       public int Weight { get; private set; }
 83 
 84       public override string ToString()
 85       {
 86         return string.Format(
 87           "Begin[{0}], End[{1}], Weight[{2}]",
 88           Begin, End, Weight);
 89       }
 90     }
 91 
 92     class Graph
 93     {
 94       private Dictionary<int, List<Edge>> _adjacentEdges
 95         = new Dictionary<int, List<Edge>>();
 96 
 97       public Graph(int vertexCount)
 98       {
 99         this.VertexCount = vertexCount;
100       }
101 
102       public int VertexCount { get; private set; }
103 
104       public int EdgeCount
105       {
106         get
107         {
108           return _adjacentEdges.Values.SelectMany(e => e).Count();
109         }
110       }
111 
112       public void AddEdge(int begin, int end, int weight)
113       {
114         if (!_adjacentEdges.ContainsKey(begin))
115         {
116           var edges = new List<Edge>();
117           _adjacentEdges.Add(begin, edges);
118         }
119 
120         _adjacentEdges[begin].Add(new Edge(begin, end, weight));
121       }
122 
123       public int[] BellmanFord(int source)
124       {
125         // distSet[i] will hold the shortest distance from source to i
126         int[] distSet = new int[VertexCount];
127 
128         // Step 1: Initialize distances from source to all other vertices as INFINITE
129         for (int i = 0; i < VertexCount; i++)
130         {
131           distSet[i] = int.MaxValue;
132         }
133         distSet[source] = 0;
134 
135         // Step 2: Relax all edges |V| - 1 times. A simple shortest path from source
136         // to any other vertex can have at-most |V| - 1 edges
137         for (int i = 1; i <= VertexCount - 1; i++)
138         {
139           foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))
140           {
141             int u = edge.Begin;
142             int v = edge.End;
143             int weight = edge.Weight;
144 
145             if (distSet[u] != int.MaxValue
146               && distSet[u] + weight < distSet[v])
147             {
148               distSet[v] = distSet[u] + weight;
149             }
150           }
151         }
152 
153         // Step 3: check for negative-weight cycles.  The above step guarantees
154         // shortest distances if graph doesn't contain negative weight cycle.
155         // If we get a shorter path, then there is a cycle.
156         foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))
157         {
158           int u = edge.Begin;
159           int v = edge.End;
160           int weight = edge.Weight;
161 
162           if (distSet[u] != int.MaxValue
163             && distSet[u] + weight < distSet[v])
164           {
165             Console.WriteLine("Graph contains negative weight cycle.");
166           }
167         }
168 
169         return distSet;
170       }
171     }
172   }
173 }