#include <stdio.h>
#include <stdlib.h>
#define Count_Vertice 6
#define Far_Distance 2000

int W[Count_Vertice][Count_Vertice] = {
	// W[i][j] represents the direct distance from i to j, where a large value indicates that direct travel is not possible
    {0, Far_Distance, 2, 3, 3, 6},
    {Far_Distance, 0, Far_Distance, 4, 2, Far_Distance},
    {10, 2, 0, 5, 1, Far_Distance},
    {Far_Distance, Far_Distance, 4, 0, Far_Distance, 2},
    {5, 9, Far_Distance, 4, 0, 3},
    {Far_Distance, Far_Distance, Far_Distance, 4, Far_Distance, 0},
};

int D[Count_Vertice][Count_Vertice]; // D[i][j] stores the minimum distance from i to j
int P[Count_Vertice][Count_Vertice]; // P[i][j] stores the highest degree vertex traversed from i to j

void Floyd(){
	int i, j, k;
	for(i=0; i < Count_Vertice; i++) // Initialize arrays
		for(j=0; j < Count_Vertice; j++){
			P[i][j] = -1;
			D[i][j] = W[i][j];
		}
	for(k=0; k < Count_Vertice; k++)
		for(i=0; i < Count_Vertice; i++)
			for(j=0; j < Count_Vertice; j++)
				if(D[i][j] > D[i][k] + D[k][j]){
				/* If D[i][j] becomes shorter by going through k */
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = k;
				}
}

void Print_Path(int a, int b){ // Note that i and j in Print_Path[i][j] are not printed
	if(P[a][b] != -1) { // P[a][b] = -1 "=" the shortest distance is from a directly to b
		Print_Path(a, P[a][b]);
		printf("%d ", P[a][b]);
		Print_Path(P[a][b], b);
	}
}

int main(int argc, char *argv[]){
	Floyd();
	int a, b;
	printf("Enter the starting point and the destination. (0 ~ %d)\n", Count_Vertice - 1);
	scanf("%d %d", &a, &b);
	printf("Shortest distance: %d\n", D[a][b]);
	printf("Shortest path: ");
	printf("%d ", a); Print_Path(a, b);
	if(D[a][b] != 0) printf("%d", b); // D[a][b] = 0

 "=" a = b
	return 0;
}