In our previous post, Dijkstra Algorithm, we calculated the shortest path from a single source to all destinations (vertices) on a graph with non-negative weights. In this post, we will study an algorithm for single source shortest path on a graph with negative weights but no negative cycles.

Here are some points to keep in mind regarding the different algorithms studied so far:

- Breadth First Search : For graphs where the edge-weights are either zero or all same.
- Dijkstra's Alogrithm : For graphs where the edge-weights are non-negative. Uses greedy strategy.
- Bellman-Ford Algorithm : For graphs where the edge-weights may be negative, but no negative weight cycle exists. Uses dynamic programming.

This post contains array - based implementation for simplicity. Another way is to use linked lists using dynamic allocation.

The code in C is as follows. Its time complexity is O (VE).

#include <stdio.h> #include <stdlib.h> int Bellman_Ford(int G[20][20] , int V, int E, int edge[20][2]) { int i,u,v,k,distance[20],parent[20],S,flag=1; for(i=0;i<V;i++) distance[i] = 1000 , parent[i] = -1 ; printf("Enter source: "); scanf("%d",&S); distance[S-1]=0 ; for(i=0;i<V-1;i++) { for(k=0;k<E;k++) { u = edge[k][0] , v = edge[k][1] ; if(distance[u]+G[u][v] < distance[v]) distance[v] = distance[u] + G[u][v] , parent[v]=u ; } } for(k=0;k<E;k++) { u = edge[k][0] , v = edge[k][1] ; if(distance[u]+G[u][v] < distance[v]) flag = 0 ; } if(flag) for(i=0;i<V;i++) printf("Vertex %d -> cost = %d parent = %d\n",i+1,distance[i],parent[i]+1); return flag; } int main() { int V,edge[20][2],G[20][20],i,j,k=0; printf("BELLMAN FORD\n"); printf("Enter no. of vertices: "); scanf("%d",&V); printf("Enter graph in matrix form:\n"); for(i=0;i<V;i++) for(j=0;j<V;j++) { scanf("%d",&G[i][j]); if(G[i][j]!=0) edge[k][0]=i,edge[k++][1]=j; } if(Bellman_Ford(G,V,k,edge)) printf("\nNo negative weight cycle\n"); else printf("\nNegative weight cycle exists\n"); return 0; }

This is an awesome algorithm. I also found another good and complete code for

ReplyDeleteBellman Ford Algorithm in C Programming.How you printed execution time in program?

ReplyDeleteThe execution time is not a part of the program, it is printed by default by the Codeblocks IDE. It is not required by the program, and is not indicative of the complexity as well.

Deletewhat is parent here???

ReplyDeleteWhat is graph in matrix form?

ReplyDelete