As we have discussed Dijkstra’s algorithm in previous articles, which helps us to find the shortest distance. But, this algorithm also has a drawback. The drawback is that this will give the wrong answer in the case of Graphs with negative weights.
So, if we get the graphs with negative weights, we will have to use Bellman Ford Algorithm. This algorithm is also simpler than Dijkstra’s algorithm and works well for distributed systems.
The only advantage that Dijkstra’s algorithm has in comparison to Bellman Ford Algorithm is that the time complexity in the case of the Bellman Ford algorithm is O(V*E) whereas in the case of Dijkstra’s algorithm it was O(V+E).
Bellman Ford Algorithm to find the shortest path
The steps for finding the shortest with Bellman Ford algorithm are –
- This step initializes distances from the source to all vertices as infinite and distance to the source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is the source vertex.
- This step calculates the shortest distances. Do the following |V|-1 times where |V| is the number of vertices in a given graph. Do the following for each edge u-v
- If dist[v] > dist[u] + weight of edge uv, then update dist[v] to
- dist[v] = dist[u] + weight of edge uv
- This step reports if there is a negative weight cycle in the graph. Again traverse every edge and do the following for each edge u-v
- ……If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”
- The idea of step 3 is, step 2 guarantees the shortest distances if the graph doesn’t contain a negative weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative weight cycle.
Bellman Ford Algorithm code in C
Now, we will see the coding implementation for Bellman Ford Algorithm in C –
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 99999
struct Edge {
int u; //start vertex of the edge
int v; //end vertex of the edge
int w; //weight of the edge (u,v)
};
struct Graph {
int V; //total number of vertices in the graph
int E; //total number of edges in the graph
struct Edge *edge; //array of edges
};
void bellmanford(struct Graph *g, int source);
void display(int arr[], int size);
int main(void) {
struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));
g->V = 4; //total vertices
g->E = 5; //total edges
g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));
g->edge[0].u = 0;
g->edge[0].v = 1;
g->edge[0].w = 5;
g->edge[1].u = 0;
g->edge[1].v = 2;
g->edge[1].w = 4;
g->edge[2].u = 1;
g->edge[2].v = 3;
g->edge[2].w = 3;
g->edge[3].u = 2;
g->edge[3].v = 1;
g->edge[3].w = 6;
g->edge[4].u = 3;
g->edge[4].v = 2;
g->edge[4].w = 2;
bellmanford(g, 0);
return 0;
}
void bellmanford(struct Graph *g, int source) {
int i, j, u, v, w;
int tV = g->V;
int tE = g->E;
int d[tV];
int p[tV];
for (i = 0; i < tV; i++) {
d[i] = INFINITY;
p[i] = 0;
}
d[source] = 0;
for (i = 1; i <= tV - 1; i++) {
for (j = 0; j < tE; j++) {
u = g->edge[j].u;
v = g->edge[j].v;
w = g->edge[j].w;
if (d[u] != INFINITY && d[v] > d[u] + w) {
d[v] = d[u] + w;
p[v] = u;
}
}
}
for (i = 0; i < tE; i++) {
u = g->edge[i].u;
v = g->edge[i].v;
w = g->edge[i].w;
if (d[u] != INFINITY && d[v] > d[u] + w) {
printf("Negative weight cycle detected!\n");
return;
}
}
printf("Distance array: ");
display(d, tV);
printf("Predecessor array: ");
display(p, tV);
}
void display(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
Attempt Free Data Structures Online Test
