好资源导航 » 文章资讯 » 最短路径的 Bellman-Ford 算法

最短路径的 Bellman-Ford 算法

2023-06-21 06:23:05 81

Bellman-Ford算法用于找到从源顶点到任何其他顶点的最小距离。该算法与Dijkstra算法的主要区别在于，在Dijkstra算法中我们无法处理负权重，但在这里我们可以轻松处理。

Bellman-Ford算法以自下而上的方式找到距离。首先，它找到路径中只有一条边的那些距离。之后增加路径长度以找到所有可能的解决方案。

输入和输出

Input:
The cost matrix of the graph:
0  6  ∞ 7  ∞
∞  0  5 8 -4
∞ -2  0 ∞  ∞
∞  ∞ -3 0  9
2  ∞  7 ∞  0

Output:
源顶点： 2
Vert:   0   1   2   3   4
Dist:  -4  -2   0   3  -6
Pred:   4   2  -1   0   1
The graph has no negative edge cycle

算法

bellmanFord(dist, pred, source)

输入-距离列表、前驱列表和源顶点。
输出-当发现负循环时为真。

Begin
   iCount := 1
   maxEdge := n * (n - 1) / 2     //n是顶点数

   for all vertices v of the graph, do
      dist[v] := ∞
      pred[v] := ϕ
   done

   dist[source] := 0
   eCount := number of edges present in the graph
   create edge list named edgeList

   while iCount < n, do
      for i := 0 to eCount, do
         if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i) dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i) pred[edgeList[i].v] := edgeList[i].u
      done
   done

   iCount := iCount + 1
   for all vertices i in the graph, do
      if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i),
         then return true
   done

   return false
End

示例

#include
#include
#define V 5
#define INF 999
using namespace std;
//图（有向）顶点5的成本矩阵

int costMat[V][V] = {
   {0, 6, INF, 7, INF},
   {INF, 0, 5, 8, -4},
   {INF, -2, 0, INF, INF},
   {INF, INF, -3, 0, 9},
   {2, INF, 7, INF, 0}
};

typedef struct {
   int u, v, cost;
}edge;

int isDiagraph() {

   //检查图是否为有向图

   int i, j;
   for(i = 0; i dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) {      //放松边缘并设置前任
            dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v];
            pred[edgeList[i].v] = edgeList[i].u;
         }
      }
      icount++;
   }

   //负循环测试
   for(int i = 0; i dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) {
         return 1;    //表示图形有负循环
      }
   }

   return 0;     //无负循环
}

void display(int *dist, int *pred) {
   cout << "Vert: ";
   for(int i = 0; i输出结果源顶点： 2
Vert:   0   1   2   3   4
Dist:  -4  -2   0   3  -6
Pred:   4   2  -1   0   1
The graph has no negative edge cycle

返回顶部
514930285
czq8825@qq.com

最短路径的 Bellman-Ford 算法

输入和输出

算法

示例

热门推荐

随机推荐