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:
|
||
|
|
#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
