#include <stdio.h>
 #define MAX 32767
 #define MAX_NODES 100
 int graph[6][6] = {
  {MAX, 2, 3, 2, 6, 5},
  {2, MAX, 4, 2, 1, 4},
  {3, 4, MAX, 5, 3, 3},
  {2, 2, 5, MAX, 4, 2},
  {6, 1, 3, 4, MAX, 7},
  {5, 4, 3, 2, 7, MAX}
 };
 void printShortestPath(int graph[6][6], int nodes, int from, int to) {
  /****** initiation **************/
  int weight[MAX_NODES], neighbour[MAX_NODES], tag[MAX_NODES];
  int i; int current;
  for(i = 0; i < nodes; i++) {
   weight[i] = MAX;
   tag[i]    = 2;    /******* the i'th node belongs to
        *   the second group
        ********************************/
  }
  weight[from] = 0;
  tag[from]    = 1;
  current      = from;
  /****** repeat until 'current' == 'to' ************/
  while(current != to) {
   int min;
   /******* find the neighbours of the current node **/
   for(i = 0; i < nodes; i++)
    if(tag[i] == 2 && graph[current][i] != MAX) {
     int add = weight[current] +
        graph[current][i];
     if(add < weight[i]) {
      weight[i] = add;
      neighbour[i] = current;
     }
    }
   /***** fine the node which weight is smallest from
    *** the 2'nd group *******/
   min = MAX; current = -1;
   for(i = 0; i < nodes; i++)
    if(tag[i] == 2 && weight[i] < min) {
     current = i;
     min = weight[i];
    }
   if(current == -1) {
    printf("no path found from %d to %d\n",
     from, to);
    return;
   }
   tag[current] = 1;
  }
  /****** print the shortest path        ************/
  while(current != from) {
   printf("%d ", current);
   current = neighbour[current];
  };
  printf("%d ", from);
 }
 void printSGT(int graph[6][6], int nodes) {
  /****** initiation **************/
  int weight[MAX_NODES], neighbour[MAX_NODES], tag[MAX_NODES];
  int i; int current;
  for(i = 0; i < nodes; i++) {
   weight[i] = MAX;
   tag[i]    = 2;    /******* the i'th node belongs to
        *   the second group
        ********************************/
  }
  weight[0] = 0;
  tag[0]    = 1;
  current   = 0;
  /****** repeat until 'current' == 'to' ************/
  while(1) {
   int min;
   /******* find the neighbours of the current node **/
   for(i = 0; i < nodes; i++)
    if(tag[i] == 2 && graph[current][i] != MAX) {
     if(graph[current][i] < weight[i]) {
      weight[i] = graph[current][i];
      neighbour[i] = current;
     }
    }
   /***** fine the node which weight is smallest from
    *** the 2'nd group *******/
   min = MAX; current = -1;
   for(i = 0; i < nodes; i++)
    if(tag[i] == 2 && weight[i] < min) {
     current = i;
     min = weight[i];
    }
   if(current == -1)
    break;
   tag[current] = 1;
  }
  /****** print the SGT        ************/
  for(i = 1; i < nodes; i++)
   printf("\t\t%d ------- %d\n", i, neighbour[i]);
 }
 main() {
  printf("\n\n\t\t");
  printShortestPath(graph, 6, 4, 5);
  printf("\n\n\n\n");
  printSGT(graph, 6);
  printf("\n\n\n\n");
 }