/*
 * Code example for CP264 Data Structures II
 * adopted from source: https://www.thecrazyprogrammer.com/2014/03/dijkstra-algorithm-for-finding-shortest-path-of-a-graph.html
 * this program is not an efficient implementation of Dijkstra algorithm. 
 * HBF
*/

#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
 
void dijkstra_spt(int *g, int n, int start, int spt[]);
void display_spt(int spt[], int n);
int shortest_path(int *g, int t[], int n, int source, int destination);
 
int main(){
  int n = 5;
  int source = 0;
  
  // adjacency matrix of undirected weighted graph
  int g[] = {
       0, 10,  0, 30, 100,
      10,  0, 50,  0,   0,
       0, 50,  0, 20,  10,  
      30, 20,  0,  0,  60,      
     100,  0, 10, 60,   0
  };
  
  // array to represent a tree with edge (i, t[i]) when i != t[i], root i if i = t[i]  
  int t[n]; 
  
  // compute the shortest path tree, and output to t[n]
  dijkstra_spt(g, n, source, t); 
  
  // display edge list of tree t[]
  display_spt(t, n);  

  int i;
  for (i=0; i<n; i++) {  
    shortest_path(g, t, n, source, i); 
  }
  return 0;
}
 
void dijkstra_spt(int *g, int n, int source, int spt[]) {
  int cost[n][n],distance[n],visited[n];
  int count,min_distance,next_node,i,j;
  
  // use cost matrix instead of the original weight matrix.  
  for(i=0;i<n;i++) {
    for(j=0;j<n;j++) {
      if(*(g+i*n+j)==0)
        cost[i][j]=INFINITY;
      else
        cost[i][j]=*(g + i*n +j);
	}
  }

  for(i=0;i<n;i++) {
    distance[i]=cost[source][i];
    spt[i]=source;
    visited[i]=0;
  }
  
  distance[source]=0;
  visited[source]=1;
  count=1;
  
  // Dijkstra algorithm
  while(count < n-1) {
    min_distance = INFINITY;
	
    // find the next node in V(G) - V(T) with the minimum distance
    for(i=0;i<n;i++) {   
      if(distance[i]<min_distance && !visited[i])
      {
        min_distance=distance[i];
        next_node = i;
      }
	}
    
    // update the distance for nodes in V(G) - V(T)     
    visited[next_node]=1;
    for(i=0;i<n;i++) {
      if(!visited[i]) { 
        if(min_distance+cost[next_node][i] < distance[i])
        {
          distance[i]=min_distance+cost[next_node][i];
          spt[i]=next_node;         
		}
	  }
	}
	
	count++;
  }
}

void display_spt(int spt[], int n) {
  int i, j, source;
  for (i=0; i<n; i++) {
	if (spt[i] == i) {
		source = i;
		break;
	}
  }
  printf("Shortest path tree: root: %d, edge-list: ", source);
  
  for(i=0; i<n; i++) {
    if(i != source) {
       printf("{%d, %d}", spt[i], i);
	   if(i <n-1) printf(",");
    }
  }
}

int shortest_path(int *g, int t[], int n, int source, int destination) {
  int temp[n], i = 0, j = destination, sum = 0;
  while (j != t[j]) { 
	sum += *(g + j*n + t[j]); 
	temp[i] = j;  
	i++;
	j = t[j];
  }
  temp[i] = source;
  
  printf("\nshortest-path(%d, %d): length: %d, edge-list: ", source, destination, sum);
  for (j = i; j>0; j--) {
    printf("{%d, %d}", temp[j], temp[j-1]);
	if (j>1) printf(", ");
  }
}

/*
Shortest path tree: root: 0, edge-list: {0, 1},{1, 2},{0, 3},{2, 4}
shortest-path(0, 0): length: 0, edge-list:
shortest-path(0, 1): length: 10, edge-list: {0, 1}
shortest-path(0, 2): length: 60, edge-list: {0, 1}, {1, 2}
shortest-path(0, 3): length: 30, edge-list: {0, 3}
shortest-path(0, 4): length: 70, edge-list: {0, 1}, {1, 2}, {2, 4}
*/