Bellman-Ford 单源最短路径算法

时间:2022-04-23 02:10:05

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(V2),若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 O(E + VlogV)。

Bellman-Ford 算法描述:

  1. 创建源顶点 v 到图中所有顶点的距离的集合 distSet,为图中的所有顶点指定一个距离值,初始均为 Infinite,源顶点距离为 0;
  2. 计算最短路径,执行 V - 1 次遍历;
    • 对于图中的每条边:如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d,则更新终点 v 的距离值 d;
  3. 检测图中是否有负权边形成了环,遍历图中的所有边,计算 u 至 v 的距离,如果对于 v 存在更小的距离,则说明存在环;

伪码实现如下:

 BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i to |V[G]| -
do for each edge (u, v) E[G]
do RELAX(u, v, w)
for each edge (u, v) E[G]
do if d[v] > d[u] + w(u, v)
then return FALSE
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。

Bellman-Ford 单源最短路径算法

由于图中有 5 个顶点,按照步骤 1 需要遍历 4 次,第一次遍历的结果如下。

Bellman-Ford 单源最短路径算法

第二次遍历的结果如下。

Bellman-Ford 单源最短路径算法

以此类推可以得出完全遍历的结果。

C# 代码实现:

 using System;
using System.Collections.Generic;
using System.Linq; namespace GraphAlgorithmTesting
{
class Program
{
static void Main(string[] args)
{
int[,] graph = new int[, ]
{
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , }
}; Graph g = new Graph(graph.GetLength());
for (int i = ; i < graph.GetLength(); i++)
{
for (int j = ; j < graph.GetLength(); j++)
{
if (graph[i, j] > )
g.AddEdge(i, j, graph[i, j]);
}
} Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
Console.WriteLine(); int[] distSet = g.BellmanFord();
Console.WriteLine("Vertex\t\tDistance from Source");
for (int i = ; i < distSet.Length; i++)
{
Console.WriteLine("{0}\t\t{1}", i, distSet[i]);
} // build a directed and negative weighted graph
Graph directedGraph = new Graph();
directedGraph.AddEdge(, , -);
directedGraph.AddEdge(, , );
directedGraph.AddEdge(, , );
directedGraph.AddEdge(, , );
directedGraph.AddEdge(, , );
directedGraph.AddEdge(, , );
directedGraph.AddEdge(, , );
directedGraph.AddEdge(, , -); Console.WriteLine();
Console.WriteLine("Graph Vertex Count : {0}", directedGraph.VertexCount);
Console.WriteLine("Graph Edge Count : {0}", directedGraph.EdgeCount);
Console.WriteLine(); int[] distSet1 = directedGraph.BellmanFord();
Console.WriteLine("Vertex\t\tDistance from Source");
for (int i = ; i < distSet1.Length; i++)
{
Console.WriteLine("{0}\t\t{1}", i, distSet1[i]);
} Console.ReadKey();
} class Edge
{
public Edge(int begin, int end, int weight)
{
this.Begin = begin;
this.End = end;
this.Weight = weight;
} public int Begin { get; private set; }
public int End { get; private set; }
public int Weight { get; private set; } public override string ToString()
{
return string.Format(
"Begin[{0}], End[{1}], Weight[{2}]",
Begin, End, Weight);
}
} class Graph
{
private Dictionary<int, List<Edge>> _adjacentEdges
= new Dictionary<int, List<Edge>>(); public Graph(int vertexCount)
{
this.VertexCount = vertexCount;
} public int VertexCount { get; private set; } public int EdgeCount
{
get
{
return _adjacentEdges.Values.SelectMany(e => e).Count();
}
} public void AddEdge(int begin, int end, int weight)
{
if (!_adjacentEdges.ContainsKey(begin))
{
var edges = new List<Edge>();
_adjacentEdges.Add(begin, edges);
} _adjacentEdges[begin].Add(new Edge(begin, end, weight));
} public int[] BellmanFord(int source)
{
// distSet[i] will hold the shortest distance from source to i
int[] distSet = new int[VertexCount]; // Step 1: Initialize distances from source to all other vertices as INFINITE
for (int i = ; i < VertexCount; i++)
{
distSet[i] = int.MaxValue;
}
distSet[source] = ; // Step 2: Relax all edges |V| - 1 times. A simple shortest path from source
// to any other vertex can have at-most |V| - 1 edges
for (int i = ; i <= VertexCount - ; i++)
{
foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))
{
int u = edge.Begin;
int v = edge.End;
int weight = edge.Weight; if (distSet[u] != int.MaxValue
&& distSet[u] + weight < distSet[v])
{
distSet[v] = distSet[u] + weight;
}
}
} // Step 3: check for negative-weight cycles. The above step guarantees
// shortest distances if graph doesn't contain negative weight cycle.
// If we get a shorter path, then there is a cycle.
foreach (var edge in _adjacentEdges.Values.SelectMany(e => e))
{
int u = edge.Begin;
int v = edge.End;
int weight = edge.Weight; if (distSet[u] != int.MaxValue
&& distSet[u] + weight < distSet[v])
{
Console.WriteLine("Graph contains negative weight cycle.");
}
} return distSet;
}
}
}
}

运行结果如下:

Bellman-Ford 单源最短路径算法

参考资料

本篇文章《Bellman-Ford 单源最短路径算法》由 Dennis Gao 发表自博客园,未经作者本人同意禁止任何形式的转载,任何自动或人为的爬虫转载行为均为耍流氓。