Algorithm:
dj(int n,int v,int cost[][],int dist[])
{
for( i <- 1 to n )
flag[i]<-0;
dist[i]<-cost[v][i];
count<-2;
while(count<=n)
{
min<-99;
for( w <- 1 to n )
if(dist[w]<min && !a[w])
min <- dist[w];
u<-w;
a[u] <- 1;
count <- count+1;
for( w <- 1 to n )
if((dist[u]+cost[u][w])<dist[w] && !a[w])
dist[w] <- dist[u]+cost[u][w];
}
}
Program:
#include<stdio.h>
#include<conio.h>
#define inf 999
void dj(int n,int v,int cost[10][10],int dist[])
{
int i,u,count,w,a[10],min;
for(i=1;i<=n;i++)
a[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !a[w])
min=dist[w],u=w;
a[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w])<dist[w] && !a[w])
dist[w]=dist[u]+cost[u][w];
}
}
int main()
{
int n,v,i,j,cost[10][10],dist[10],infi=224;
clrscr();
printf("\n Enter the no.of nodes: ");
scanf("%d",&n);
printf("\n Enter the cost matrix:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0 && i!=j )
cost[i][j]=inf;
}
printf("\n");
}
printf("The Matrix for the given graph is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]!=inf)
printf("%d\t",cost[i][j]);
else
printf("%c\t",infi);
}
printf("\n");
}
printf("\n Enter the source: ");
scanf("%d",&v);
dj(n,v,cost,dist);
printf("\n Shortest path:\n");
for(i=1;i<=n;i++)
{
if(i!=v)
printf("%c->%c Cost=%d\n",64+v,64+i,dist[i]);
}
getch();
return 0;
}
Output:
Enter the no.of nodes: 9
Enter the cost matrix:
0 5 2 0 0 0 0 0 0
5 0 0 3 0 3 0 0 0
2 0 0 6 5 8 0 0 0
0 3 6 0 0 0 1 4 0
0 0 5 0 0 0 6 2 0
0 3 8 0 0 0 6 2 0
0 0 0 1 6 6 0 0 7
0 0 0 4 2 2 0 0 3
0 0 0 0 0 0 7 3 0
The Matrix for the given graph is:
0 5 2 α α α α α α
5 0 α 3 α 3 α α α
2 α 0 6 5 8 α α α
α 3 6 0 α α 1 4 α
α α 5 α 0 α 6 2 α
α 3 8 α α 0 6 2 α
α α α 1 6 6 0 α 7
α α α 4 2 2 α 0 3
α α α α α α 7 3 0
Enter the source: 1
Shortest path:
A->B Cost=5
A->C Cost=2
A->D Cost=8
A->E Cost=7
A->F Cost=8
A->G Cost=9
A->H Cost=9
A->I Cost=12
0 Comments