Sunday, July 9, 2017

6. form a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm.

#include<stdio.h>
main ()
{
int n, cost[15][15], i, j, s[15], v,dist[15],num,min;
clrscr();
printf ("Enter the vertices please\n");
scanf ("%d", &n);
printf ("Enter the cost of the edges please\n");
printf ("Enter 999 if the edge is not present or for the self loop\n");
for (i = 1; i<= n; i++)
for (j = 1; j <= n; j++)
scanf ("%d", &cost[i][j]);
printf ("Enter the Source vertex please\n");
scanf ("%d", &v);
for (i = 1; i<= n; i++)
{
s[i] = 0;
dist[i] = cost[v][i];
}
s[v] = 1;
dist[v] = 0;
for (num = 2; num <= n - 1; num++)
{
min = 999;
for (i = 1; i<= n; i++)
if (s[i] == 0 &&dist[i] < min)
{
min = dist[i];
j = i;
}
s[j] = 1;
for (i = 1; i<= n; i++)
{
if (s[i] == 0)
{
if (dist[i] > (dist[j] + cost[j][i]))
dist[i] = (dist[j] + cost[j][i]);
}
}
}
printf ("VERTEX\tDESTINATION\tCOST\n");
for (i = 1; i<= n; i++)
printf (" %d\t %d\t\t %d\n", v, i, dist[i]);
getch();
}

No comments:

Post a Comment