Convert this algortihm to C PLEASE Needed ASAP 1 function Dijkstra( Graph , sour
ID: 3904724 • Letter: C
Question
Convert this algortihm to C PLEASE Needed ASAP 1 function Dijkstra(Graph, source): 2 3 create vertex set Q 4 5 for each vertex v in Graph: // Initialization 6 dist[v] ? INFINITY // Unknown distance from source to v 7 prev[v] ? UNDEFINED // Previous node in optimal path from source 8 add v to Q // All nodes initially in Q (unvisited nodes) 9 10 dist[source] ? 0 // Distance from source to source 11 12 while Q is not empty: 13 u ? vertex in Q with min dist[u] // Node with the least distance 14 // will be selected first 15 remove u from Q 16 17 for each neighbor v of u: // where v is still in Q. 18 alt ? dist[u] + length(u, v) 19 if alt < dist[v]: // A shorter path to v has been found 20 dist[v] ? alt 21 prev[v] ? u 22 23 return dist[], prev[]
Explanation / Answer
Below is your code.Please do rate this answer positive, If i was able to help you. Let me know if you have any issues in comments
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<math.h>
#define IN 99
#define N 6
int dijkstra(int cost[][N], int source, int target);
int main()
{
int cost[N][N],i,j,w,ch,co;
int source, target,x,y;
printf(" The Shortest Path Algorithm ( DIJKSTRA'S ALGORITHM in C ");
for(i=1;i< N;i++)
for(j=1;j< N;j++)
cost[i][j] = IN;
for(x=1;x< N;x++)
{
for(y=x+1;y< N;y++)
{
printf("Enter the weight of the path between nodes %d and %d: ",x,y);
scanf("%d",&w);
cost [x][y] = cost[y][x] = w;
}
printf(" ");
}
printf(" Enter the source:");
scanf("%d", &source);
printf(" Enter the target");
scanf("%d", &target);
co = dijsktra(cost,source,target);
printf(" The Shortest Path: %d",co);
}
int dijsktra(int cost[][N],int source,int target)
{
int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
char path[N];
for(i=1;i< N;i++)
{
dist[i] = IN;
prev[i] = -1;
}
start = source;
selected[start]=1;
dist[start] = 0;
while(selected[target] ==0)
{
min = IN;
m = 0;
for(i=1;i< N;i++)
{
d = dist[start] +cost[start][i];
if(d< dist[i]&&selected[i]==0)
{
dist[i] = d;
prev[i] = start;
}
if(min>dist[i] && selected[i]==0)
{
min = dist[i];
m = i;
}
}
start = m;
selected[start] = 1;
}
start = target;
j = 0;
while(start != -1)
{
path[j++] = start+65;
start = prev[start];
}
path[j]='';
strrev(path);
printf("%s", path);
return dist[target];
}