#include <stdio.h>

#define MAXNODES 15
#define MAXCOST 99 /* Maximum total cost */
#define FILENAME "one.net"
#define NODES 7  /*number of nodes in network*/


/*Globals --used for complexity--*/
int Count = 0;

void traverse_node(int s, int d, int c_node, int path[], int c_path_num, int cost,
		   int network[MAXNODES][MAXNODES], int lcost[MAXNODES], int spath[MAXNODES]);


void main(void)
{
  	int a, b, x, y, cost, next_node;
	int s, d;
	int c_path_num = 1; /*current path number*/

	int M[MAXNODES];    /*shortest path array*/
	int network[MAXNODES][MAXNODES];
	int lcost[MAXNODES];
	int spath[MAXNODES]; /*final shortest path*/

	FILE *input_file;
	
	
	/*initialize arrays*/
	for (x=0; x<=MAXNODES-1; x++)
	  {
	    lcost[x] = -1;
	    spath[x] = -1;
	    M[x] = -1;
 
	    for (y=0; y<=MAXNODES-1; y++)
	      network[x][y] = -1;
	  }

	/*open file for node information*/
	input_file = fopen (FILENAME, "r");
	
	/*initialize network array*/
	while (!feof(input_file))
	{
		fscanf(input_file, "%d %d %d", &x, &y, &cost);
		network[x][y] = cost;
		network[y][x] = network[x][y];
		network[x][x] = -1;
		network[y][y] = -1;
		/*network[x][x] = 0;
		  network[y][y] = 0;*/
	}
	/* for (x=0; x<=MAXNODES-1; x++)  */
/* 	  { */
/* 	    printf ("\n"); */
/* 	    for (y=0; y<=MAXNODES-1; y++) */
/* 	      printf("%d ", network[x][y]);	  */
/* 	  }  */
/* 	printf("\n\n"); */ 

	fclose(input_file);

       for (a=1; a<=NODES; a++)
	 {
	   for (b=1; b<=NODES; b++)
	     {	   
		   s = a;
		   d = b;

		/*if the starting node is not connected to the destination node
		  check for other connecting nodes*/
		M[c_path_num] = s;
		c_path_num++;
		if (network[s][d] == -1)
		  {
		    for (y=1; y<=MAXNODES-1; y++)
		      if (network[s][y] != -1)
			traverse_node(s, d, y, M, c_path_num, 0, network, lcost, spath);
		  }
		else /*check for other connecting nodes*/
		  {
		    /*set the least cost and shortest path, then 
		      check to see if a shorter path exists*/
		    lcost[d] = network[s][d];
		    M[c_path_num] = d;
		    for (x=0; x<=MAXNODES; x++)
		      spath[x] = M[x];
		    
		    for (y=1; y<=MAXNODES-1; y++)
		      {
			if (network[s][y] != -1 && d != y)
			  traverse_node(s, d, y, M, c_path_num, 0, network, lcost, spath);
		      }
		  }    
		
		if (b == 1)
		  printf("ROUTE TABLE FOR NODE %d\n\n", s);
		  
		printf("Dest-%d  Goto-%d\n", d, spath[2]);
		
		printf("Least cost from %d to %d: %d\n", s, d, lcost[d]);
		
		printf("Shortest path: ");
		x=0;
		while(spath[++x] != d)
		  {
		    next_node = spath[2];
		    printf("%d ", spath[x]);
		  }
		printf("%d", spath[x]);
       
		
		
		printf("\n\n");

		/*reinitialize globals*/
		for (x=0; x<=MAXNODES-1; x++)
		  {
		    lcost[x] = -1;
		    spath[x] = -1;
		    M[x] = -1;
		  }
		c_path_num = 1;
	       
	     }
	   
	   printf("\n\n");
	 }
	 

	printf("Recursive calls: %d\n", Count);
	exit(0);
      
}

/* traverse_node is a recursive solution to finding out the shortest path of
   a graph.  It is called on when a particular node has either no connection 
   to the destination node, or if there is a connection to the destination node, but
   there is connections to one or more other nodes that might lead to a shorter path.
   The main components are:

   s = source node
   d = destination node
   c_node = current node (the node in between)
   path = M in Dijkstra's algorithm (represents the shortest path)
   cost = keeps track of the cost of traversing 1 to n nodes in a particular path
   network = the actual network
   lcost = least cost of shortest path
   spath = the final shortest path
*/

void traverse_node(int s, int d, int c_node, int path[], int c_path_num, int cost,
		   int network[MAXNODES][MAXNODES], int lcost[MAXNODES], int spath[MAXNODES])
    {
      int x, y;

	Count++;
      /*printf("%d, %d, %d, %d\n", s, d, c_node, cost);*/

      /*if s and d are the same cost is 0, otherwise algorithm will 
	go to the least cost connected node and back*/
      if (s == d)
	{
	  cost = 0;
	  lcost[d] = cost;
	  path[c_path_num] = d;
	  for (x=0; x<=MAXNODES; x++)
	    spath[x] = path[x];
	  return;
	}

      /*set least-cost and local-shortest-path*/
      if (lcost[c_node] == -1 || lcost[c_node] > network[s][c_node] + cost)
	{
	  lcost[c_node] = network[s][c_node] + cost;
	  cost += network[s][c_node];
	  path[c_path_num] = c_node;
	  c_path_num++;
	}
      else 
	return;
	
  
      
      /*if the this node is not connected to the final destination
	recursively call traverse_node...*/
      if (network[c_node][d] == -1)
	  {
	    /*find connected nodes and call traverse_node for each*/
	    for (y=1; y<=MAXNODES-1; y++)
	      {
		if (network[c_node][y] != -1 && y != s)
		  {
		    /*printf("traverse node: %d\n", y);*/
		    traverse_node(c_node, d, y, path, c_path_num, cost, network, lcost, spath);
		  }
		  
	      }
	  }
      
      /*...otherwise set least-cost and final-shortest-path*/ 
      else if (lcost[d] == -1 || lcost[d] > network[c_node][d] + cost)
	{
	  /*printf("%d\n", network[c_node][d] + cost);*/
	  lcost[d] = network[c_node][d] + cost;
	  path[c_path_num] = d;
	  for (x=0; x<=MAXNODES; x++)
	    spath[x] = path[x];
	  
	  /*make sure there are no shorter paths from connected nodes*/
	  for (y=0; y<=MAXNODES-1; y++)
	    {
	      if (network[c_node][y] != -1)
		traverse_node(c_node, d, y, path, c_path_num, cost, network, lcost, spath);
	    }
	}
      
      return;
    }