C和C ++中的Bellman-Ford算法

太过爱你忘了你带给我的痛 2022-12-07 13:56 106阅读 0赞

Here you will learn about Bellman-Ford Algorithm in C and C++.

在这里，您将了解C和C ++中的Bellman-Ford算法。

Dijkstra and Bellman-Ford Algorithms used to find out single source shortest paths. i.e. there is a source node, from that node we have to find shortest distance to every other node. Dijkstra algorithm fails when graph has negative weight cycle. But Bellman-Ford Algorithm won’t fail even, the graph has negative edge cycle. If there any negative edge cycle it will detect and say there is negative edge cycle. If not it will give answer to given problem.

Dijkstra和Bellman-Ford算法用于找出单源最短路径。 也就是说，有一个源节点，我们必须从该节点找到到其他每个节点的最短距离。 当图具有负权重循环时，Dijkstra算法失败。 但是Bellman-Ford算法甚至不会失败，因为图形具有负边沿周期。 如果有任何负边缘周期，它将检测并说有负边缘周期。 如果没有，它将给定问题的答案。

Bellman-Ford Algorithm will work on logic that, **if graph has n nodes, then shortest path never contain more than n-1 edges**. This is exactly what Bellman-Ford do. It is enough to relax each edge (v-1) times to find shortest path. But to find whether there is negative cycle or not we again do one more relaxation. If we get less distance in nth relaxation we can say that there is negative edge cycle. Reason for this is negative value added and distance get reduced.

Bellman-Ford算法将适用于以下逻辑： **如果图具有n个节点，则最短路径永远不会包含n-1个以上的边** 。 这正是贝尔曼·福特所做的。 放松每个边缘(v-1)次以找到最短路径就足够了。 但是要发现是否存在负周期，我们再次放松一遍。 如果我们在第n次弛豫中得到的距离较小，则可以说存在负边缘周期。 原因是增加了负值，距离减小了。

**Relaxing edge**

**松弛的边缘**

In algorithm and code below we use this term Relaxing edge.

在下面的算法和代码中，我们使用此术语松弛边。

Relaxing edge is an operation performed on an edge (u, v) . when,

松弛边缘是在边缘(u，v)上执行的操作。 什么时候，

d(u) > d(v) + Cost(u,v)

d(u)> d(v)+成本(u，v)

Here d(u) means distance of u. If already known distance to “u” is greater than the path from “s” to “v” and “v” to “u” we update that d(u) value with d(v) + cost(u,v).

在此，d(u)表示u的距离。 如果已知的到“ u”的距离大于从“ s”到“ v”以及从“ v”到“ u”的距离，我们用d(v)+ cost(u，v)更新该d(u)值。

### 算法和时间复杂度 **(**Algorithm and Time Complexity**)** ###

Bellman-Ford (G,w,S){   //G is graph given, W is weight matrix, S is source vertex (starting vertex)
        Initialize single source (G,S)  //means initially distance to every node is infinity except to source. Source is 0 (zero). This will take O(v) time
     
        For i=1 to |G.V| -1     //Runs (v-1) times
            For each edge (G,V)€ G.E    // E times
                Relax(u,v,w)    //O(1) time
     
        For each edge (G,V) € G.E
            If (v.d > u.d + w(u,v))     //The idea behind this is we are relaxing edges nth time if we found more shortest path than (n-1)th level, we can say that graph is having negative edge cycle and detected.
                Return False
     
        return true
    }

Finally time complexity is (v-1) (E) O(1) = O(VE)

最后时间复杂度为(v-1)(E)O(1)= O(VE)

### 示例问题 **(**Example Problem**)** ###

![Bellman-Ford Algorithm 1][]

This is the given directed graph.

这是给定的有向图。

(s,t) = 6  (y,x) = -3

(s，t)= 6(y，x)= -3

(s,y)= 7  (y,z) = 9

(s，y)= 7(y，z)= 9

(t,y) = 8  (x,t) = -2

(t，y)= 8(x，t)= -2

(t,z) = -4  (z,x) = 7

(t，z)= -4(z，x)= 7

(t,x) = 5  (z,s) = 2

(t，x)= 5(z，s)= 2

Above we can see using vertex “S” as source (Setting distance as 0), we initialize all other distance as infinity.

在上方我们可以看到使用顶点“ S”作为源(将距离设置为0)，我们将所有其他距离初始化为无穷大。

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td><strong>S</strong></td> 
   <td><strong>T</strong></td> 
   <td><strong>X</strong></td> 
   <td><strong>Y</strong></td> 
   <td><strong>Z</strong></td> 
  </tr> 
  <tr> 
   <td><strong>distance</strong></td> 
   <td>0</td> 
   <td>∞</td> 
   <td>∞</td> 
   <td>∞</td> 
   <td>∞</td> 
  </tr> 
  <tr> 
   <td><strong>Path</strong></td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

**Table and Image explanation:** This table, 2nd row shows distance from source to that particular node ad 3rd row shows to reach that node what is the node we visited recently. This path we can see in the image also.

**表和图像说明：**该表第二行显示了从源到特定节点的距离，第三行显示了到达该节点的位置，这是我们最近访问的节点。 我们也可以在图像中看到此路径。

**Note:** In each iteration, iteration “n” means it contains the path at most “n” edges. And while we are doing iteration “n” we must follow the graph which we obtained in iteration “n-1”.

**注意：**在每次迭代中，迭代“ n”表示它最多包含“ n”个边缘的路径。 在进行迭代“ n”时，我们必须遵循在迭代“ n-1”中获得的图。

**Iteration 1:** edge (s,t) and (z,y) relaxed and updating the distances to t and y.

**迭代1：**放松(s，t)和(z，y)边，并将距离更新为t和y。

![Bellman-Ford Algorithm][]

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td><strong>S</strong></td> 
   <td><strong>T</strong></td> 
   <td><strong>X</strong></td> 
   <td><strong>Y</strong></td> 
   <td><strong>Z</strong></td> 
  </tr> 
  <tr> 
   <td><strong>distance</strong></td> 
   <td>0</td> 
   <td>6</td> 
   <td>∞</td> 
   <td>7</td> 
   <td>∞</td> 
  </tr> 
  <tr> 
   <td><strong>Path</strong></td> 
   <td>–</td> 
   <td>S</td> 
   <td>–</td> 
   <td>S</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

**Iteration 2 :** edge (t,z) and (y,x) relaxed and x and z values are updated.

**迭代2：**放松(t，z)和(y，x)的边，并更新x和z值。

![Bellman-Ford Algorithm 3][]

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td><strong>S</strong></td> 
   <td><strong>T</strong></td> 
   <td><strong>X</strong></td> 
   <td><strong>Y</strong></td> 
   <td><strong>Z</strong></td> 
  </tr> 
  <tr> 
   <td><strong>distance</strong></td> 
   <td>0</td> 
   <td>6</td> 
   <td>4</td> 
   <td>7</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td><strong>Path</strong></td> 
   <td>–</td> 
   <td>S</td> 
   <td>Y</td> 
   <td>S</td> 
   <td>T</td> 
  </tr> 
 </tbody> 
</table>

**Iteration 3:** Value of t updated by relaxing (x,t)

**迭代3：**通过放宽(x，t)更新t的值

![Bellman-Ford Algorithm 4][]

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td><strong>S</strong></td> 
   <td><strong>T</strong></td> 
   <td><strong>X</strong></td> 
   <td><strong>Y</strong></td> 
   <td><strong>Z</strong></td> 
  </tr> 
  <tr> 
   <td><strong>distance</strong></td> 
   <td>0</td> 
   <td>2</td> 
   <td>4</td> 
   <td>7</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td><strong>Path</strong></td> 
   <td>–</td> 
   <td>X</td> 
   <td>Y</td> 
   <td>S</td> 
   <td>T</td> 
  </tr> 
 </tbody> 
</table>

**Iteration 4:** Value of z updated by relaxing edge (t,z)

**迭代4：** z的值通过松弛边(t，z)更新

![Bellman-Ford Algorithm 5][]

Until now 4 iterations completed and shortest path found to every node form source node. Now we have to do one more iteration to find whether there exists negative edge cycle or not. When we do this nth (5th here) relaxation if we found less distance to any vertex from any other path we can say that there is negative edge cycle. Here we can relax any edge to graph which obtained in iteration 4and we can observe that there is no chance to change those values. So we can confirm that there is no negative edge cycle in this graph.

到目前为止，已完成4次迭代，并找到了从源节点到每个节点的最短路径。 现在，我们必须再进行一次迭代以查找是否存在负边沿周期。 当我们进行第n次(此处为第5次)松弛时，如果发现从任何其他路径到任何顶点的距离较小，则可以说存在负边沿循环。 在这里，我们可以放宽在迭代4中获得的任何边缘到图形，并且可以观察到没有机会更改这些值。 因此，我们可以确认该图中没有负边缘周期。

## C语言中的Bellman-Ford算法程序 **(**Program for Bellman-Ford Algorithm in C**)** ##

### 代码说明 **(**Code explanation**)** ###

![Bellman-Ford Algorithm 6][]

This picture shows the Structure of our input graph.

此图显示了输入图的结构。

We create a structure called “Graph” which contains two integers int v (represent number of vertices) and int E (represents number of edges) and also another structure inside this structure which represents edge. That structure contains 3 integers source, destination, weight of that edge. So we create “E” number of structures inside the structure Graph.

我们创建一个名为“ Graph”的结构，其中包含两个整数int v(表示顶点数)和int E(表示边数)，以及该结构内部的另一个表示边数的结构。 该结构包含3个整数，即该边的源，目标和权重。 因此，我们在结构图内创建“ E”个结构。

After creating Graph, choose a source node and send to BellmanFord function. In this function we relax each edge “v-1” times. After this we can store the result of shortest paths in an array. And we do one more relaxation to find whether there exists negative edge cycle or not. If we got less distance at any node in Vth relaxation of edges, then we can say that the graph have negative edge cycle.

创建图后，选择一个源节点并发送给BellmanFord函数。 在此功能中，我们放松每个边缘“ v-1”次。 之后，我们可以将最短路径的结果存储在数组中。 我们再做一次松弛，以发现是否存在负边沿周期。 如果我们在边缘的Vth弛豫中的任何节点上获得的距离较小，则可以说该图具有负边缘周期。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <limits.h>
     
    struct Edge
    {
        // This structure is equal to an edge. Edge contains two end points. These edges are directed edges so they
    	//contain source and destination and some weight. These 3 are elements in this structure
        int source, destination, weight;
    };
     
    // a structure to represent a connected, directed and weighted graph
    struct Graph
    {
        int V, E;
    	// V is number of vertices and E is number of edges
     
        struct Edge* edge;
    	// This structure contain another structure which we already created edge.
    };
     
    struct Graph* createGraph(int V, int E)
    {
        struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));
    	//Allocating space to structure graph
     
        graph->V = V;   //assigning values to structure elements that taken form user.
     
        graph->E = E;
     
        graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
    	//Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges
     
        return graph;
    }
     
    void FinalSolution(int dist[], int n)
    {
    	// This function prints the final solution
        printf("\nVertex\tDistance from Source Vertex\n");
        int i;
     
        for (i = 0; i < n; ++i){
    		printf("%d \t\t %d\n", i, dist[i]);
    	}
    }
     
    void BellmanFord(struct Graph* graph, int source)
    {
        int V = graph->V;
     
        int E = graph->E;
     
        int StoreDistance[V];
     
        int i,j;
     
        // This is initial step that we know , we initialize all distance to infinity except source.
    	// We assign source distance as 0(zero)
     
        for (i = 0; i < V; i++)
            StoreDistance[i] = INT_MAX;
     
        StoreDistance[source] = 0;
     
        //The shortest path of graph that contain V vertices, never contain "V-1" edges. So we do here "V-1" relaxations
        for (i = 1; i <= V-1; i++)
        {
            for (j = 0; j < E; j++)
            {
                int u = graph->edge[j].source;
     
                int v = graph->edge[j].destination;
     
                int weight = graph->edge[j].weight;
     
                if (StoreDistance[u] + weight < StoreDistance[v])
                    StoreDistance[v] = StoreDistance[u] + weight;
            }
        }
     
        // Actually upto now shortest path found. But BellmanFord checks for negative edge cycle. In this step we check for that
        // shortest distances if graph doesn't contain negative weight cycle.
     
        // If we get a shorter path, then there is a negative edge cycle.
        for (i = 0; i < E; i++)
        {
            int u = graph->edge[i].source;
     
            int v = graph->edge[i].destination;
     
            int weight = graph->edge[i].weight;
     
            if (StoreDistance[u] + weight < StoreDistance[v])
                printf("This graph contains negative edge cycle\n");
        }
     
        FinalSolution(StoreDistance, V);
     
        return;
    }
     
    int main()
    {
        int V,E,S;  //V = no.of Vertices, E = no.of Edges, S is source vertex
     
    	printf("Enter number of vertices in graph\n");
        scanf("%d",&V);
     
    	printf("Enter number of edges in graph\n");
        scanf("%d",&E);
     
    	printf("Enter your source vertex number\n");
    	scanf("%d",&S);
     
        struct Graph* graph = createGraph(V, E);    //calling the function to allocate space to these many vertices and edges
     
        int i;
        for(i=0;i<E;i++){
            printf("\nEnter edge %d properties Source, destination, weight respectively\n",i+1);
            scanf("%d",&graph->edge[i].source);
            scanf("%d",&graph->edge[i].destination);
            scanf("%d",&graph->edge[i].weight);
        }
     
        BellmanFord(graph, S);
    	//passing created graph and source vertex to BellmanFord Algorithm function
     
        return 0;
    }

**Output**

**输出量**

*Enter number of vertices in graph* *5* *Enter number of edges in graph* *10* *Enter your source vertex number* *0*

*在图形* *5中* *输入* *顶点数在图形* *10中* *输入边数* *10* *输入源顶点数* *0*

*Enter edge 1 properties Source, destination, weight respectively* *0 1 6*

*输入边1属性分别为源，目标，权重* *0 1 6*

*Enter edge 2 properties Source, destination, weight respectively* *0 2 7*

*输入边2个属性分别为源，目标，权重* *0 2 7*

*Enter edge 3 properties Source, destination, weight respectively* *1 2 8*

*输入边3个属性分别为源，目标，权重* *1 2 8*

*Enter edge 4 properties Source, destination, weight respectively* *1 4 -4*

*输入边4个属性分别为源，目标，权重* *1 4 -4*

*Enter edge 5 properties Source, destination, weight respectively* *1 3 5*

*输入边5个属性分别是源，目标，权重* *1 3 5*

*Enter edge 6 properties Source, destination, weight respectively* *3 1 -2*

*输入边6个属性分别是源，目标，权重* *3 1 -2*

*Enter edge 7 properties Source, destination, weight respectively* *2 3 -3*

*输入边7个属性分别是源，目标，权重* *2 3 -3*

*Enter edge 8 properties Source, destination, weight respectively* *2 4 9*

*输入边8个属性分别是源，目标，权重* *2 4 9*

*Enter edge 9 properties Source, destination, weight respectively* *4 0 2*

*输入边9个属性分别是源，目标，权重* *4 0 2*

*Enter edge 10 properties Source, destination, weight respectively* *4 3 7*

*输入边10个属性分别为源，目标，权重* *4 3 7*

*Vertex  Distance from Source Vertex* *0  0* *1  2* *2  7* *3  4* *4  -2*

*顶点到源顶点的距离* *0 0* *1 2* *2 7* *3 4* *4 -2*

## C ++中的Bellman-Ford算法程序 **(**Program for Bellman-Ford Algorithm in C++**)** ##

#include <iostream>
    #include <stdlib.h>
    #include <string.h>
    #include <limits.h>
     
    using namespace std;
     
    struct Edge
    {
        // This structure is equal to an edge. Edge contains two end points. These edges are directed edges so they
    	//contain source and destination and some weight. These 3 are elements in this structure
        int source, destination, weight;
    };
     
    // a structure to represent a connected, directed and weighted graph
    struct Graph
    {
        int V, E;
    	// V is number of vertices and E is number of edges
     
        struct Edge* edge;
    	// This structure contain another structure which we already created edge.
    };
     
    struct Graph* createGraph(int V, int E)
    {
        struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));
    	//Allocating space to structure graph
     
        graph->V = V;   //assigning values to structure elements that taken form user.
     
        graph->E = E;
     
        graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
    	//Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges
     
        return graph;
    }
     
    void FinalSolution(int dist[], int n)
    {
    	// This function prints the final solution
        cout<<"\nVertex\tDistance from Source Vertex\n";
        int i;
     
        for (i = 0; i < n; ++i){
    		cout<<i<<"\t\t"<<dist[i]<<"\n";
    	}
    }
     
    void BellmanFord(struct Graph* graph, int source)
    {
        int V = graph->V;
     
        int E = graph->E;
     
        int StoreDistance[V];
     
        int i,j;
     
        // This is initial step that we know , we initialize all distance to infinity except source.
    	// We assign source distance as 0(zero)
     
        for (i = 0; i < V; i++)
            StoreDistance[i] = INT_MAX;
     
        StoreDistance[source] = 0;
     
        //The shortest path of graph that contain V vertices, never contain "V-1" edges. So we do here "V-1" relaxations
        for (i = 1; i <= V-1; i++)
        {
            for (j = 0; j < E; j++)
            {
                int u = graph->edge[j].source;
     
                int v = graph->edge[j].destination;
     
                int weight = graph->edge[j].weight;
     
                if (StoreDistance[u] + weight < StoreDistance[v])
                    StoreDistance[v] = StoreDistance[u] + weight;
            }
        }
     
        // Actually upto now shortest path found. But BellmanFord checks for negative edge cycle. In this step we check for that
        // shortest distances if graph doesn't contain negative weight cycle.
     
        // If we get a shorter path, then there is a negative edge cycle.
        for (i = 0; i < E; i++)
        {
            int u = graph->edge[i].source;
     
            int v = graph->edge[i].destination;
     
            int weight = graph->edge[i].weight;
     
            if (StoreDistance[u] + weight < StoreDistance[v])
                cout<<"\nThis graph contains negative edge cycle\n";
        }
     
        FinalSolution(StoreDistance, V);
     
        return;
    }
     
    int main()
    {
        int V,E,S;  //V = no.of Vertices, E = no.of Edges, S is source vertex
     
    	cout<<"Enter number of vertices in graph\n";
        cin>>V;
     
    	cout<<"Enter number of edges in graph\n";
        cin>>E;
     
    	cout<<"Enter your source vertex number\n";
    	cin>>S;
     
        struct Graph* graph = createGraph(V, E);    //calling the function to allocate space to these many vertices and edges
     
        int i;
        for(i=0;i<E;i++){
            cout<<"\nEnter edge "<<i+1<<" properties Source, destination, weight respectively\n";
            cin>>graph->edge[i].source;
            cin>>graph->edge[i].destination;
            cin>>graph->edge[i].weight;
        }
     
        BellmanFord(graph, S);
    	//passing created graph and source vertex to BellmanFord Algorithm function
     
        return 0;
    }

**Reference:** Introduction to Algorithms by Thomas H. Cormen

**参考：** Thomas H. Cormen的算法简介

Comment below if you have queries or found anything incorrect in above tutorial for Bellman-Ford Algorithm in C and C++.

如果您对以上使用C和C ++的Bellman-Ford算法的教程有疑问或发现任何不正确之处，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/06/bellman-ford-algorithm-in-c-and-c.html][https_www.thecrazyprogrammer.com_2017_06_bellman-ford-algorithm-in-c-and-c.html]

[Bellman-Ford Algorithm 1]: /images/20221123/a9457014f78d4073b11e55f82f097dc0.png
[Bellman-Ford Algorithm]: /images/20221123/2aefaaa8ef334582b8002e225073eee6.png
[Bellman-Ford Algorithm 3]: /images/20221123/4a6305c0c1694f46b52493e09f170e71.png
[Bellman-Ford Algorithm 4]: /images/20221123/432c2198d7154e7aa1630eb3bc31e021.png
[Bellman-Ford Algorithm 5]: /images/20221123/ba6f9e53188e4e0281a7d70c0f992e7b.png
[Bellman-Ford Algorithm 6]: /images/20221123/e481beea7a714dd590b222b30ef2c23e.png
[https_www.thecrazyprogrammer.com_2017_06_bellman-ford-algorithm-in-c-and-c.html]: https://www.thecrazyprogrammer.com/2017/06/bellman-ford-algorithm-in-c-and-c.html