Single Source Shortest Path: Bellman-Ford Algorithm

The Bellman-Ford Algorithm is a single-source shortest path algorithm used to find the shortest path from a source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, which works only for graphs with non-negative edge weights, Bellman-Ford can handle graphs with negative edge weights and can detect negative weight cycles.

Algorithm

INITIALIZE-SINGLE-SOURCE (G, s) for each vertex i = 1 to V[G] - 1 do for each edge (u, v) in E[G] do RELAX (u, v, w) For each edge (u, v) in E[G] do if d[u] + w(u, v) < d[v] then return FALSE return TRUE

---

Analysis

The initialization in line 1 takes (v) time. For loop of lines, 2-4 takes O(E) time and for For-loop of lines, 5-7 takes O(E) time. Thus, the Bellman-Ford algorithm runs in O(E) time.

---

Implementation in C Language 

---

maxVertices represents the maximum number of vertices that can be present in the graph. 

Input Format: Graph is directed and weighted. 

 

The first two integers must be the number of vertices and edges which must be followed by pairs of vertices that have an edge between them. vertices represent the number of vertices and edges represent the number of edges in the graph.

 

Source Code

#include<stdio.h> #include<stdlib.h> #include<limits.h> struct edge { int src; int dest; int weight; }; struct Graph { int vertex; int e; struct edge * edge_list; }; void bellman_ford(struct Graph *graph, int * dist, int source) { int i = 0, j = 0; for (i = 0; i < graph->vertex; i++) { dist[i] = INT_MAX; } dist[source] = 0; for (j = 0; j <= graph->vertex - 1; j++) { for (i = 0; i < graph->e; i++) { if (dist[graph->edge_list[i].dest] > (dist[graph->edge_list[i].src] + graph->edge_list[i].weight)) { dist[graph->edge_list[i].dest] = dist[graph->edge_list[i].src] + graph->edge_list[i].weight; } } } } int main() { int no_of_vertex, no_of_edges, *dist, i = 0, start_vertex = 0; struct Graph *graph = (struct Graph *) malloc(sizeof(struct Graph)); printf("Enter number of vertex:"); scanf("%d", &no_of_vertex); printf("Enter number of edges:"); scanf("%d", &no_of_edges); printf("Enter the start vertex:"); scanf("%d", &start_vertex); graph->e = no_of_edges; graph->vertex = no_of_vertex; graph->edge_list = (struct edge *) malloc(no_of_edges * sizeof(struct edge)); printf("Enter source destination and weight of the edges:"); for (i = 0; i < no_of_edges; i++) { scanf("%d%d%d", &graph->edge_list[i].src, &graph->edge_list[i].dest, &graph->edge_list[i].weight); } dist = (int * ) malloc(no_of_vertex * sizeof(int)); bellman_ford(graph, dist, start_vertex); for (i = 0; i < graph->vertex; i++) { printf("%d %d\n", i, dist[i]); } return 0; }

---

Happy Exploring!