Uncategorized

BelmonFord

 

 

#include<stdio.h>

int main()
{
int V, edge[20][2], G[20][20],i, j, k=0;
printf(“\nBELLMAN FORD”);
printf(“\nEnter the no of vertices: “);
scanf(“%d”, &V);
printf(“\nEnter 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; //add edge

}

}
if(bellman_ford(G, V, k, edge))
printf(“\n No negative weight cycle “);
else
printf(“\n negative weight cycle is exist “);
return 0;
}

 

int bellman_ford(int G[20][20], int V, int E, int edge[20][2])
{
int i, u,v,k,dist[20], parent[20], s, flag=1;
for(i=0;i<V;i++)
{
dist[i]=1000,parent[i]=-1;

}
printf(“\nEnter source: “);
scanf(“%d”,&s);
dist[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(dist[u]+G[u][v]<dist[v])
dist[v]=dist[u]+G[u][v], parent[v]=u;

}
}
for(k=0;k<E;k++)
{
u=edge[k][0],v=edge[k][1];
if(dist[u]+G[u][v]<dist[v])
flag=0;
}

if(flag)
{
for(i=0;i<V;i++)
{
printf(“\n vertex:%d->cost=%d parent=%d\n”,i+1,dist[i],parent[i]+1);

}
}
return flag;
}

 

”””””””””””””””””””””””””””””””””””””” output ””””””””””””””””””””””””””

student@sdl17:~$ gcc ford.c
student@sdl17:~$ ./a.out

BELLMAN FORD
Enter the no of vertices: 4

Enter graph in matrix form:
0 6 3 0
0 0 3 2
0 0 0 5
7 0 0 0

Enter source: 1

vertex:1->cost=0 parent=0

vertex:2->cost=6 parent=1

vertex:3->cost=3 parent=1

vertex:4->cost=8 parent=2

No negative weight cycle student@sdl17:~$

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s