#include<stdio.h>
#include<conio.h>
#define infinity 32767
int cost[20][20],n,dist[20],s[20],a[20][20];
void setdata();
void getdata();
void path(int);
void setdata()
{
int i,j,k;
printf("\nEnter number of nodes: ");
scanf("%d",&n);
printf("Enter Adjacency Matrix: ");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j)
cost[i][i]=0;
else if (a[i][j]!=0)
{
}
}
void getdata()
{
}
else
printf("\nEnter cost from %d to %d: ",i,j);
scanf("%d",&cost[i][j]);
cost[i][j]=infinity;
int i;
for(i=1;i<=n;i++)
if(dist[i]==32767)
printf("not reachable");
else
}
printf(" %d",dist[i]);
void path(int v)
{
int i,j,min,u;
for(i=1;i<=n;i++)
{
}
s[v]=1;
s[i]=0;
dist[i]=cost[v][i];
dist[v]=0;
for(i=2;i<=n;i++)
{
min=32767;
for(j=1;j<=n;j++)
if(s[j]==0 && dist[j]<min)
u=j;
s[u]=1;
for(j=1;j<=n;j++)
if(s[j]==0 && a[u][j]==1)
if(dist[j]>dist[u]+cost[u][j])
dist[j]=dist[u]+cost[u][j];
}
}
void main()
{
int v;
clrscr();
setdata();
printf("\nEnter the source vertex: ");
scanf("%d",&v);
path(v);
printf("\nShortest paths " );
getdata();
getch();
}
Output:
Enter number of nodes: 6
Enter Adjacency Matrix: 0 1 1 1 0 0
0 0 1 1 0 0
0 0 0 0 1 0
1 0 0 0 1 0
0 1 1 0 0 0
0 0 0 0 1 0
Enter cost from 1 to 2: 50
Enter cost from 1 to 3: 45
Enter cost from 1 to 4: 10
Enter cost from 2 to 3: 10
Enter cost from 2 to 4: 15
Enter cost from 3 to 5: 30
Enter cost from 4 to 1: 20
Enter cost from 4 to 5: 15
Enter cost from 5 to 2: 20
Enter cost from 5 to 3: 35
Enter cost from 6 to 5: 3
Enter the source vertex: 1
Shortest paths 0 45 45 10 25not reachable
