C Program To Implement Bellman Ford Algorithm
Let us learn how to implement Bellman Ford Algorithm in C programming language. This algorithm is also famously known as Bellman – Ford – Moore Algorithm. The algorithm makes use of Queue Data Structure.
What is Bellman Ford Algorithm?
The Bellman-Ford Algorithm is an algorithm that calculates the shortest path from a source vertex to a destination vertex in a weighted graph. A weighted graph consists of the cost or lengths of all the edges in a given graph. This algorithm helps to detect cycles whose edges sum to a negative value which is also known as a
This algorithm helps to detect cycles whose edges sum to a negative value which is also known as a
A weighted graph consists of the cost or lengths of all the edges in a given graph. This algorithm helps to detect cycles whose edges sum to a negative value which is also known as a Negative Cycle.
However, this algorithm is more versatile than Dijkstra’s Algorithm but a little slower in execution. This algorithm can handle graphs with non – negative weights, unlike Dijkstra Algorithm.
This algorithm works efficiently only for Non – Negative weights.
Must Read: C Program For Sieve of Eratosthenes Algorithm
Bellman Ford Algorithm
- Initialize the predecessor of all the vertices to NIL and pathLength of all vertices to Infinity.
- Set the pathLength of the source vertex to zero and add it to the Queue.
- Delete a vertex from the Queue and set it as the current vertex.
- Check all the adjacent vertices of the current vertex. Check minimum weight condition for these vertices and do relabel if needed.
- Every vertex is relabeled is inserted into the queue if it is not present in the queue.
- Repeat Steps 3, 4 and 5 till the Queue Underflow condition is satisfied. Queue underflow occurs when the Queue becomes Empty.
There are other algorithms that can be used to find the shortest path in a weighted graph such as:
- Dijkstra’s Algorithm
- Floyd’s Algorithm
C Program To Implement Bellman Ford Algorithm using Queue
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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 | #include<stdlib.h> #include<stdio.h> #define MAX 100 #define TRUE 1 #define FALSE 0 #define infinity 9999 #define NIL -1 int vertices; int front, rear; int queue[MAX]; int pathLength[MAX]; int adjacent_matrix[MAX][MAX]; int predecessor[MAX]; int isPresent_in_queue[MAX]; int BellmanFord_Algorithm(int source); void initialize(); void insert(int u); int del(); int isEmpty(); void make_graph(); void pathFinder(int source, int vertex); void showTable(); void show_queue(); int main() { int flag, source, vertex; make_graph(); printf("Enter Source Vertex:\t"); scanf("%d", &source); flag = BellmanFord_Algorithm(source); if(flag == -1) { printf("Negative Cycle in the Graph. Cannot Proceed.\n"); exit(1); } while(1) { printf("Enter Destination Vertex(-1 to Quit):\t"); scanf("%d", &vertex); if(vertex == -1) { break; } if(vertex < 0 || vertex >= vertices) { printf("Vertex %d does not exist\n", vertex); } else if(vertex == source) { printf("Source Vertex and Destination Vertex are same\n"); } else if(pathLength[vertex] == infinity) { printf("No path from Source to Destination Vertex\n"); } else { pathFinder(source, vertex); } } return 0; } void pathFinder(int source, int vertex) { int count, u; int path[MAX]; int shortest_distance = 0; int temp = 0; while(vertex != source) { temp++; path[temp] = vertex; u = predecessor[vertex]; shortest_distance = shortest_distance + adjacent_matrix[u][vertex]; vertex = u; } temp++; path[temp] = source; printf("Shortest Path:\n"); for(count = temp; count >= 1; count--) { printf("%3d", path[count]); } printf("\nShortest Distance:\t%d\n", shortest_distance); } int BellmanFord_Algorithm(int source) { int k = 0, count, current; for(count = 0; count < vertices; count++) { predecessor[count] = NIL; pathLength[count] = infinity; isPresent_in_queue[count] = FALSE; } initialize(); printf("Make pathLength of source vertex 0\n"); pathLength[source] = 0; printf("Insert Source Vertex in the Queue\n"); insert(source); isPresent_in_queue[source] = TRUE; show_queue(); showTable(); getchar(); while(!isEmpty()) { current = del(); isPresent_in_queue[current] = FALSE; printf("Current vertex: \t%d\n", current); if(source == current) { k++; } if(k > vertices) { return -1; } for(count = 0; count < vertices; count++) { if (adjacent_matrix[current][count] != 0) { printf("Vertex [%d] is adjacent to the Current Vertex [%d]\n", count, current); if(pathLength[count] > pathLength[current] + adjacent_matrix[current][count]) { printf("pathLength(%d) + weight(%d, %d) < pathLength(%d)\t", current, current, count, count); printf("%d + %d < %d\n", pathLength[current], adjacent_matrix[current][count], pathLength[count]); pathLength[count] = pathLength[current] + adjacent_matrix[current][count]; predecessor[count] = current; printf("Relabel vertex: %d\n", count); printf("pathLength[%d] = %d , ", count, pathLength[count]); printf("predecessor[%d] = %d\n", count, current); if(!isPresent_in_queue[count]) { insert(count); isPresent_in_queue[count] = TRUE; printf("Insert %d in the queue\n\n", count); } else printf("%d is present in the queue\n\n", count); } else { if(pathLength[current] + adjacent_matrix[current][count] == pathLength[count]) { printf("pathLength(%d) + weight(%d, %d) = pathLength(%d)\t", current, current, count, count); printf("%d + %d = %d\n", pathLength[current], adjacent_matrix[current][count], pathLength[count]); } else { printf("pathLength(%d) + weight(%d, %d) > pathLength(%d)\t", current, current, count, count); printf("%d + %d > %d\n", pathLength[current], adjacent_matrix[current][count], pathLength[count]); } printf("Vertex [%d] Should Not Be Relabelled\n\n", count); } } } show_queue(); showTable(); getchar(); } return 1; } void showTable() { int count; printf("\nVertex pathLength Predecessor\n"); for(count = 0; count < vertices; count++) { printf("%d\t%d\t\t", count, pathLength[count]); if(predecessor[count] == NIL) { printf("NIL\n"); } else { printf("%d\n", predecessor[count]); } } printf("\n\n"); } void initialize() { int count; for(count = 0; count < MAX; count++) { queue[count] = 0; } rear = -1; front = -1; } int isEmpty() { if(front == -1 || front > rear) { return 1; } else { return 0; } } void insert(int element) { if (rear == MAX - 1) { printf("Queue Overflow\n"); exit(1); } else { if(front == -1) { front = 0; } rear = rear + 1; queue[rear] = element; } } int del() { int element; if (front == -1 || front > rear) { printf("Queue Underflow\n"); exit(1); } else { element = queue[front]; front = front + 1; } return element; } void show_queue() { int count; if(isEmpty()) { printf("Queue is Empty\n"); return; } printf("QUEUE\n"); for(count = front; count <= rear; count++) { printf("%4d", queue[count]); } printf("\n\n"); } void make_graph() { int count, maximum_edges, origin_vertex, destination_vertex, weight; printf("Enter total number of vertices:\t"); scanf("%d", &vertices); maximum_edges = vertices * (vertices - 1); for(count = 0; count < maximum_edges; count++) { printf("Enter Edge [%d] Co-ordinates [-1 -1] to Quit\n", count + 1); printf("Enter Origin Vertex Point:\t"); scanf("%d", &origin_vertex); printf("Enter Destination Vertex Point:\t"); scanf("%d", &destination_vertex); if((origin_vertex == -1) && (destination_vertex == -1)) { break; } printf("Enter the weight for this edge:\t"); scanf("%d", &weight); if(origin_vertex >= vertices || destination_vertex >= vertices || origin_vertex < 0 || destination_vertex < 0) { printf("Edge Co - ordinates are Invalid\n"); count--; } else { adjacent_matrix[origin_vertex][destination_vertex] = weight; } } } |
Must Read: C Program For Implement Warshall’s Algorithm
Output
In case you get any compilation errors or any doubts in this C program for Bellman Ford Algorithm solution for Finding Shortest Path in a weighted graph, let us know about it in the comment section below. Find more about this algorithm on Wikipedia.
The bellman ford algorithm is an advanced version of the Dijkstra’s algorithm.
Thank you so much. The Bellman ford is an an amazing algorithm