C program to find shortest path in Graph | With simple code

Shortest Path:-
The shortest path problem is about finding a path between vertices in a graph such that the total sum of the edges weights is minimum.

 #include <stdio.h>
 #include <conio.h>
 #define INFINITY 9999
 #define MAX 10
 void dijkstra(int G[MAX][MAX], int n, int startnode);

 int main()
 {
    int G[MAX][MAX], i, j, n, u;
    printf("Enter no. of vertices:\n");
    scanf("%d", &n);
    printf("\nEnter the adjacency matrix:\n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &G[i][j]);
    printf("\nEnter the starting node:\n");
    scanf("%d", &u);
    dijkstra(G, n, u);
    return 0;
 }
 void dijkstra(int G[MAX][MAX], int n, int startnode)
 {
    int cost[MAX][MAX], dis[MAX], pred[MAX];
    int visited[MAX], arr, mindis, nextnode, i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (G[i][j] == 0)
                cost[i][j] = INFINITY;
            else
                cost[i][j] = G[i][j];
    //initialize pred[],dis[] and visited[]
    for (i = 0; i < n; i++)
    {
        dis[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }
    dis[startnode] = 0;
    visited[startnode] = 1;
    arr = 1;
    while (arr < n - 1)
    {
        mindis = INFINITY;
        //nextnode gives the node at minimum dis
        for (i = 0; i < n; i++)
            if (dis[i] < mindis && !visited[i])
            {
                mindis = dis[i];
                nextnode = i;
            }
        //check if a better path exists through nextnode
        visited[nextnode] = 1;
        for (i = 0; i < n; i++)
            if (!visited[i])
                if (mindis + cost[nextnode][i] < dis[i])
                {
                    dis[i] = mindis + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        arr++;
     }
     //print the path and dis of each node
     for (i = 0; i < n; i++)
        if (i != startnode)
        {
            printf("\nDistance of node%d=%d", i, dis[i]);
            printf("\nPath=%d", i);
            j = i;
            do
            {
                j = pred[j];
                printf("<-%d", j);
            } while (j != startnode);
        }
  }

When the above program is executed, it produces following results --<\b>

   Enter no. of vertices:
   5
   
   Enter the adjacency matrix:
   0  10  0  30  100
   10 0  50  0   0
   0  50  0  20  10
   30 0  20  0  60
   100 0  10 60  0
   
   Enter the starting node:0
   
   Distance of node1=10
   Path=1<-0
   Distance of node2=50
   Path=2<-3<-0
   Distance of node3=30
   Path=3<-0
   Distance of node4=60
   Path=4<-2<-3<-0