Translate the Pseudocode to C Some Pseudocode Down below is the Dijkstra\'s Algo

Question

Translate the Pseudocode to C

Some Pseudocode

Down below is the Dijkstra's Algorithm for reference

/* Dijkstra's Algorithm in C */
#include
#include
#include
#include
#include
#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];
}

This is the url from the Dijkstra's code if it helps   http://www.codewithc.com/dijkstras-algorithm-in-c/

Explanation / Answer

Djikstra.c

#include <stdio.h>
#include <limits.h>
  
#define Vertices 9

int minDist(int dt[], bool setSP[])
{
int minimum = INT_MAX, minimumIndex;
  
for (int a = 0; a < Vertices; a++)
if (setSP[a] == false && dt[a] <= minimum)
minimum = dt[a], minimumIndex = a;
  
return minimumIndex;
}
  
int dispSoln(int dt[], int n)
{
printf("Vertex Distance from Sourcen");
for (int uu = 0; uu < Vertices; uu++)
printf("%d tt %dn", uu, dt[uu]);
}
  

void djikstrasAlgo(int grp[Vertices][Vertices], int source)
{
int dt[Vertices];   
bool setSP[Vertices];
for (int uu = 0; uu < Vertices; uu++)
dt[uu] = INT_MAX, setSP[uu] = false;
dt[source] = 0;
for (int cnt = 0; cnt < Vertices-1; cnt++)
{
int qq = minDist(dt, setSP);
setSP[qq] = true;
for (int a = 0; a < Vertices; a++)
if (!setSP[a] && grp[qq][a] && dt[qq] != INT_MAX&& dt[qq]+grp[qq][a] < dt[a])
dt[a] = dt[qq] + grp[qq][a];
}
dispSoln(dt, Vertices);
}
int main()
{
int grp[Vertices][Vertices] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
  
djikstrasAlgo(grp, 0);
  
return 0;
}

Hope this helps......

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.