#include <iostream>
#include <limits.h>
using namespace std;

#define FOR(i, x, v) for(int i=x;i<v;i++)
#define V 9

void printPath(int points[], int i){
	if(points[i]==-1){
		return;
	}
	printPath(points, points[i]);
	cout << i << " ";
}

void printSolution(int dist[], int points[]) { 
   printf("Titik   Jarak dari titik awal\tPath\n"); 
   FOR(i, 0, V){
      printf("%d \t\t %d \t\t ", i, dist[i]);
      printPath(points, i);
      cout << endl;
	}
} 

int findMin(int dist[], bool visited[]){
	int min = INT_MAX, minIndex;
	FOR(i, 0, V){
		if(visited[i]==false && dist[i]<=min){
			minIndex = i;
			min = dist[i];
		}		
	}
	cout << "Min is " << minIndex << endl;
	return minIndex;
}

void shortestPath(int data[V][V], int fPoint){
	int dist[V];
	int points[V];
	bool visited[V] = {false};
	FOR(i, 0, V){
		dist[i] = INT_MAX;
	}
	dist[fPoint] = 0;
	points[fPoint] = -1;
	FOR(i, 0, V-1){
		int x = findMin(dist, visited);
		visited[x] = true;
		FOR(y, 0, V){
			if(!visited[y] && data[x][y] && dist[x]!=INT_MAX && dist[x]+data[x][y]<dist[y]){
				dist[y] = dist[x] + data[x][y];
				cout << "Dist y is " << dist[y] << endl;
				points[y] = x;
			}
		}
	}
	printSolution(dist, points);
}

int main(){
   int data[V][V]   = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
                      {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
                      {0, 8, 0, 7, 0, 4, 0, 0, 2}, 
                      {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
                      {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
                      {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
                      {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
                      {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
                      {0, 0, 2, 0, 0, 0, 6, 7, 0}}; 
   
    shortestPath(data, 0);
    return 0;
}