Here you will learn about Bellman-Ford Algorithm in C and C++.
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.
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.
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,
d(u) > d(v) + Cost(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).
Algorithm and Time Complexity
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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)
Example Problem
This is the given directed graph.
(s,t) = 6 (y,x) = -3
(s,y)= 7 (y,z) = 9
(t,y) = 8 (x,t) = -2
(t,z) = -4 (z,x) = 7
(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 | T | X | Y | Z | |
distance | 0 | ∞ | ∞ | ∞ | ∞ |
Path | – | – | – | – | – |
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”.
Iteration 1: edge (s,t) and (z,y) relaxed and updating the distances to t and y.
S | T | X | Y | Z | |
distance | 0 | 6 | ∞ | 7 | ∞ |
Path | – | S | – | S | – |
Iteration 2 : edge (t,z) and (y,x) relaxed and x and z values are updated.
S | T | X | Y | Z | |
distance | 0 | 6 | 4 | 7 | 2 |
Path | – | S | Y | S | T |
Iteration 3: Value of t updated by relaxing (x,t)
S | T | X | Y | Z | |
distance | 0 | 2 | 4 | 7 | 2 |
Path | – | X | Y | S | T |
Iteration 4: Value of z updated by relaxing edge (t,z)
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.
Program for Bellman-Ford Algorithm in C
Code explanation
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.
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
#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
Enter edge 1 properties Source, destination, weight respectively
0 1 6
Enter edge 2 properties Source, destination, weight respectively
0 2 7
Enter edge 3 properties Source, destination, weight respectively
1 2 8
Enter edge 4 properties Source, destination, weight respectively
1 4 -4
Enter edge 5 properties Source, destination, weight respectively
1 3 5
Enter edge 6 properties Source, destination, weight respectively
3 1 -2
Enter edge 7 properties Source, destination, weight respectively
2 3 -3
Enter edge 8 properties Source, destination, weight respectively
2 4 9
Enter edge 9 properties Source, destination, weight respectively
4 0 2
Enter edge 10 properties Source, destination, weight respectively
4 3 7
Vertex Distance from Source Vertex
0 0
1 2
2 7
3 4
4 -2
Program for Bellman-Ford Algorithm in C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#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
Comment below if you have queries or found anything incorrect in above tutorial for Bellman-Ford Algorithm in C and C++.
These Algorithms are quite complex, maybe I need study and learn more to understand. Thanks for sharing the article.