Dijkstra algorithm to find shortest path C code

 

Dijkstra algorithm to find shortest path C code

Using dijkstra shortest path is 

Output

enter number of node3 enter cost matrix 0 1 3 1 0 1 3 1 0 distance of node1=1 Path=1<-0distance of node2=2 Path=2<-1<-0

#include<stdio.h>

void dijkstra(int c[10][10],int n);

int i,j,s,n;

int c[10][10];

int sourcenode=0;

int main()

{

    printf("enter number of node");

    scanf("%d",&n);

    printf("enter cost matrix");

    for(i=0;i<n;i++)

        for(j=0;j<n;j++)

            scanf("%d",&c[i][j]);

    dijkstra(c,n);

    return 0;

}

void dijkstra(int c[10][10],int n)

{

int distance[10];

int pre[10];

int visited[10];

int count,minidistance,nextnode;

for(i=0;i<n;i++)

{

    distance[i]=c[sourcenode][i];

    pre[i]=sourcenode;

    visited[i]=0;

}

distance[sourcenode]=0;

visited[sourcenode]=1;

count=1;

while(count<n-1)

{

    minidistance=99;

    for(i=0;i<n;i++)

    {

        if(distance[i]<minidistance&&!visited[i])

        {

            minidistance=distance[i];

            nextnode=i;

        }

    }

    visited[nextnode]=1;

    for(i=0;i<n;i++)

        if(!visited[i])

        if(minidistance+c[nextnode][i]<distance[i])

        {

            distance[i]=minidistance+c[nextnode][i];

            pre[i]=nextnode;

        }

        count++;

}

for(i=0;i<n;i++)

if(i!=sourcenode)

{

    printf("distance of node%d=%d",i,distance[i]);

    printf("\nPath=%d",i);

    j=i;

    do

    {

        j=pre[j];

        printf("<-%d",j);

    }

    while (j!=sourcenode);

   

    }

   

}

Output

enter number of node3 enter cost matrix 0 1 3 1 0 1 3 1 0 distance of node1=1 Path=1<-0distance of node2=2 Path=2<-1<-0