/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define INF 9999
int flag[N + 1];
int distance[N + 1];
int result[N + 1];
int via[N + 1];
int i, j, min, position;
int data[N + 1][N + 1] = {
{0,0,0,0,0,0,0},
{0,0,2,INF,3,INF,INF},
{0,INF,0,4,1,7,INF},
{0,INF,INF,0,4,1,3},
{0,INF,2,2,0,1,INF},
{0,INF,INF,1,INF,0,6},
{0,INF,3,INF,8,INF,0}
};
int main(void)
{
//initiate
for (i = 1; i <= N; i++) {
flag[i] = 0;
distance[i] = INF;
result[i] = 0;
}
distance[1] = 0;
for (i = 1; i <= N; i++) {
min = INF;
for (j = 1; j <= N; j++) {
if (min > distance[i] && flag[j] == 0) {
min = distance[i] + data[i][j];
position = j;
}
}
flag[position] = 1;
for (j = 1; j <= N; j++) {
if (distance[j] > data[position][j] + distance[position] && data[position][j] != INF) {
distance[j] = data[position][j] + distance[position];
via[j] = position;
printf("distance[%d] : data[%d][%d] + distance[%d] : %d + %d\n", j, position, j, position, data[position][j], distance[position]);
}
}
}
printf("\n");
int path[N], path_counter = 0;
for (i = 1; i <= N; i++) {
printf("1 ~ %d : %d", i, distance[i]);
position = i;
while (1) {
path[path_counter++] = position;
if (position == 1)break;
position = via[position];
}
printf(" PATH : ");
for (int k = path_counter - 1; k >= 0; k--) {
printf("%d ", path[k]);
path_counter = 0;
if(k - 1 >= 0){
result[i] += data[path[k]][path[k-1]];
}
}
printf(" / result : %d", result[i]);
printf("\n");
}
}
