Bellman-Ford算法是一种单源最短路径算法,与Dijkstra算法不同,它能够处理带有负权边的图,还能检测负权环的存在。
Bellman-Ford算法是一种用于计算带权图中单源最短路径的算法。与Dijkstra算法不同,Bellman-Ford算法可以处理含有负权边的图,能够检测负权环(负权环会导致最短路径无限减小)。该算法由Richard Bellman和Lester Ford分别独立发现,因此以他们的名字命名。
松弛操作的定义是:对于边(u,v),如果 dist[v] > dist[u] + weight(u,v),则更新 dist[v] = dist[u] + weight(u,v)。
假设有一个包含5个顶点(A-E)的有向加权图,边的关系及权重如下:
...