text: #include <stdio.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:");
      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:");
      scanf("%d", &u);
      dijkstra(G, n, u);
  
      return 0;
  }
  
  void dijkstra(int G[MAX][MAX], int n, int startnode)
  {
  
      int cost[MAX][MAX], distance[MAX], pred[MAX];
      int visited[MAX], count, mindistance, nextnode, i, j;
  
      //pred[] stores the predecessor of each node
      //count gives the number of nodes seen so far
      //create the cost matrix
      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[],distance[] and visited[]
      for (i = 0; i < n; i++)
      {
          distance[i] = cost[startnode][i];
          pred[i] = startnode;
          visited[i] = 0;
      }
  
      distance[startnode] = 0;
      visited[startnode] = 1;
      count = 1;
  
      while (count < n - 1)
      {
          mindistance = INFINITY;
  
          //nextnode gives the node at minimum distance
          for (i = 0; i < n; i++)
              if (distance[i] < mindistance && !visited[i])
              {
                  mindistance = distance[i];
                  nextnode = i;
              }
  
          //check if a better path exists through nextnode
          visited[nextnode] = 1;
          for (i = 0; i < n; i++)
              if (!visited[i])
                  if (mindistance + cost[nextnode][i] < distance[i])
                  {
                      distance[i] = mindistance + cost[nextnode][i];
                      pred[i] = nextnode;
                  }
          count++;
      }
  
      //print the path and distance of each node
      for (i = 0; i < n; i++)
          if (i != startnode)
          {
              printf("\nDistance of node%d=%d", i, distance[i]);
              printf("\nPath=%d", i);
  
              j = i;
              do
              {
                  j = pred[j];
                  printf("<-%d", j);
              } while (j != startnode);
          }
  }