Single source shortest path Algorithm 1. Implement the algorithm 2. Write comments 3. Screenshot of output /// Single source shortest path #include
Single source shortest path
1. Implement the algorithm
2. Write comments
3. Screenshot of output
/// Single source shortest path
#include <stdio.h>
#define INFINITY 9999
void SingleSource(int graph[50][50], int qv, int start_ver);
void main()
{
int graph[50][50],qv, start_ver;
int i,j;
printf("\nEnter the quantity of vertexes:");
scanf("%d", &qv);
printf("\nEnter the values for path costs matrix:\n");
for(i=0; i< qv; i++)
for(j=0; j<qv; j++)
scanf("%d", &graph[i][j]);
printf("\nEnter the starting vertex:");
scanf("%d",&start_ver);
SingleSource(graph, qv, start_ver);
printf("\n\n\n");
return 0;
}
void SingleSource(int graph[50][50], int qv, int start_ver)
{
int eadgecost[50][50];
int distance[20];
int gen[50];
int visited[50];
int i,j;
for(i=0; i<qv; i++)
for(j=0; j<qv; j++)
if (graph[i][j]==0) /// inserted single "=" instead of "=="
///==================================
eadgecost[i][j]= INFINITY;
else
eadgecost[i][j] = graph[i][j];
for(i=0; i<qv;i++)
{
distance[i]= eadgecost[start_ver][i];
gen[i] = start_ver;
visited[i]= 0;
}
distance[start_ver]=0;
visited[start_ver] = 1;
int count_round = 1;
int minimum_dist;
int ahead_ver;
while(count_round < qv-1)
{
minimum_dist = INFINITY;
for(i=0; i<qv; i++)
if(distance[i] < minimum_dist&&!visited[i])
{
minimum_dist = distance[i];
ahead_ver = i;
}
visited[ahead_ver] = 1;
for (i=0; i<qv;i++)
if(!visited[i])
if(minimum_dist+eadgecost[ahead_ver][i] < distance[i])
{
distance[i] = minimum_dist + eadgecost[ahead_ver][i];
gen[i] = ahead_ver;
}
count_round++;
}
for(i=0; i<qv; i++)
if(i != start_ver)
{
printf("\nDistance of %d = %d", i, distance[i]);
printf("\nShow Path = %d",i);
j = i; /// inserted 'i=j' instead of 'j=i'
/// =========================================
do
{
j= gen[j];/// a->c->f
printf("<<< %d",j);
}while (j != start_ver);
printf("\n");
///=========================
}
}
Step by step
Solved in 2 steps with 1 images
