如何实现基于任意权值的单源最短路径算法（Bellman-Ford）？

本文共计3201个文字，预计阅读时间需要13分钟。

原文：本文实例为大家分享了C++计算任意权值单源最短路径的具体代码，供大家参考，具体内容如下：

一、有Dijkstra算法求最短路径了，为什么还要用Bellman-Ford算法？

Dijkstra算法不适用于带有负权边的图，而Bellman-Ford算法可以处理带有负权边的图。当图中存在负权边时，Dijkstra算法可能会陷入局部最优，导致无法正确计算出最短路径。而Bellman-Ford算法能够检测到负权环，并给出正确的最短路径。

本文实例为大家分享了C++计算任意权值单源最短路径的具体代码，供大家参考，具体内容如下

一、有Dijkstra算法求最短路径了，为什么还要用Bellman-Ford算法

Dijkstra算法不适合用于带有负权值的有向图。

如下图：

用Dijkstra算法求顶点0到各个顶点的最短路径：

（1）首先,把顶点0添加到已访问顶点集合S中，选取权值最小的邻边<0, 2>，权值为5

记录顶点2的最短路径为：dist[2]=5, path[2]=0,把顶点2添加到集合S中。

顶点2，没有邻边(从顶点2出发，其他顶点为终点的边)，结束；

（2）访问<0, 1>边，权值为7，把顶点7添加到顶点集合S中，dist[1]=7, path[1]=0。

虽然，顶点1有邻边<1,2>，但是因为顶点2已在集合S中，所以，不继续修改，结束程序。

所以，最终dist[1]=7,dist[2]=5。