Showing posts with label Bellman Ford. Show all posts
Showing posts with label Bellman Ford. Show all posts

Sunday 17 July 2016

Program 1: Bellman Ford Algorithm

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to implement the Bellman-Ford algorithm and determine its performance. Give its applications.

Algorithm:

INITIALIZE_SINGLE_SOURCE (G = (V, E), Source s)
  1. for each vertex v in V[G]
  2.                       d[v] :=  +infinity   
  3.              parent[v] := NIL                    /* parent of v in the shortest path tree rooted at s */
  4. d[s] := 0

 

RELAX ( u, v, w )
1.     if  d[v] > d[u] + w(u,v)
2.                       d[v]  := d[u] + w(u,v)
3.               parent[v]  := u
 
    

         BELLMAN_FORD ( G, w, s )

  1. INITIALIZE_SINGLE_SOURCE (G = (V,E), Source s)
  2. for i = 1 to V[G] – 1
  3.             for each edge (u, v)  in E[G]
  4.                         RELAX(u, v, w)
  5. for each edge (u, v)  in E[G]
  6.              if  d[v] > d[u] + w(u,v)
  7.                         return FALSE
  8. return TRUE
 
 


































#include<stdio.h>
#include<stdlib.h>

int w[10][10], dist[10], parent[10];
int n, source;
int BellmanFord();
int Display(int);

int main()
{
            int i, j, check;
            printf("\n Enter the no. of vertices: ");
            scanf("%d", &n);
            printf("\n Enter the cost matrix: ");
            for(i = 1; i <= n; i++)
                        for(j = 1; j <= n; j++)
                        {
                                    if(i != j)
                                    {
                                                printf("\n Enter the weight/cost of the edge w[%d][%d]: ", i, j);
                                                scanf("%d", &w[i][j]);
                                    }
                        }
            printf("\n Enter the source vertex: ");
            scanf("%d", &source);
            for(i = 1; i <= n; i++)
            {
                        dist[i] = 999;
                        parent[i] = 999;
            }
            dist[source] = 0;
            parent[source] = -1;
            check = BellmanFord();
            if(check == 0)
            {
                        printf("\nNo solution exists because of -ve weight cycle in I/P G");
                        exit(0);
            }
            for(i = 1; i <= n; i++)
            {
                        if(i != source)
                        {
                                    printf("\n\n(V%d, V%d) : %d", source, i, dist[i]);
                                    printf("\nPath is: ");
                                    Display(i);
                        }
            }
            return 0;
}
int Display(int x)
{
            if(parent[x] == source)
                        printf(" %d  ==>  %d", source, x);
            else
            {
                        Display(parent[x]);
                        printf(" ==> %d ", x);
            }
            return 0;
}


int BellmanFord()
{
            int pass, i, j, k, NegativeCycle;
            for(pass = 1; pass <= n-1; pass++)
            {
                        for(i = 1; i <= n; i++)
                                    for(j = 1; j <= n; j++)
                                    {
                                                if((dist[i]+w[i][j]) < dist[j])
                                                {
                                                            parent[j] = i;
                                                            dist[j] = dist[i]+w[i][j];
                                                }
                                    }
                        printf("\n\nAt the end of Pass %d Distance vector is:\n", pass);
                        for(k = 1; k <= n; printf("%d ", dist[k]), k++);
                        printf("\nThe Parent vector is: \n");
                        for(k = 1; k <= n; printf("%d ", parent[k++]));
            }
            NegativeCycle = 0;
            for(i = 1; i <= n; i++)
                        for(j = 1; j <= n; j++)
                        {
                                    if(dist[j] > (dist[i]+w[i][j]))
                                    {
                                                NegativeCycle = 1;
                                                return 0;
                                    }
                        }
            return 1;
}


Output:

 Enter the no. of vertices: 5
 Enter the cost matrix:
 Enter the weight/cost of the edge w[1][2]: 6
 Enter the weight/cost of the edge w[1][3]: 999
 Enter the weight/cost of the edge w[1][4]: 7
 Enter the weight/cost of the edge w[1][5]: 999
 Enter the weight/cost of the edge w[2][1]: 999
 Enter the weight/cost of the edge w[2][3]: 5
 Enter the weight/cost of the edge w[2][4]: 8
 Enter the weight/cost of the edge w[2][5]: -4
 Enter the weight/cost of the edge w[3][1]: 999
 Enter the weight/cost of the edge w[3][2]: -2
 Enter the weight/cost of the edge w[3][4]: 999
 Enter the weight/cost of the edge w[3][5]: 999
 Enter the weight/cost of the edge w[4][1]: 999
 Enter the weight/cost of the edge w[4][2]: 999
 Enter the weight/cost of the edge w[4][3]: -3
 Enter the weight/cost of the edge w[4][5]: 9
 Enter the weight/cost of the edge w[5][1]: 2
 Enter the weight/cost of the edge w[5][2]: 999
 Enter the weight/cost of the edge w[5][3]: 7
 Enter the weight/cost of the edge w[5][4]: 999

Enter the source vertex: 1
At the end of Pass 1 Distance vector is:
0     6     4     7     2
The Parent vector is:
-1     1     4     1     2

At the end of Pass 2 Distance vector is:
0     2     4     7     2
The Parent vector is:
-1     3     4     1     2

At the end of Pass 3 Distance vector is:
0     2     4     7     -2
The Parent vector is:
-1     3     4     1     2

At the end of Pass 4 Distance vector is:
0     2     4     7     -2
The Parent vector is:
-1     3     4     1     2

(V1, V2): 2
Path is: 1 ==> 4 ==> 3 ==> 2

(V1, V3): 4
Path is: 1 ==> 4 ==> 3

(V1, V4): 7
Path is: 1 ==> 4

(V1, V5): -2
Path is: 1 ==> 4 ==> 3 ==> 2 ==> 5