#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define VERTICES 6
#define INF 1000
int cost[VERTICES][VERTICES] ={
{0, 50, 45, 10, INF, INF},
{INF, 0, 10, 15, INF, INF},
{INF, INF, 0, INF, 30, INF},
{20, INF, INF, 0, 15, INF},
{INF, 20, 35, INF, 0, INF},
{INF, INF, INF, INF, 3, 0}
};
int found[VERTICES];
int distance[VERTICES];
int parent[VERTICES];
void shortestPath(int v, int cost[][VERTICES], int distance[], int n, int found[])
{
int i,u,w;
int cv;
for(i=0; i<n; i++){
found[i] = FALSE;
distance[i] = cost[v][i];
if ( distance[i] > 0 && distance[i] < INF) parent[i] = v;
else parent[i] = -1;
}
found[v] = TRUE;
distance[v] =0;
for(i=0; i<n-2; i++){
u= choose(distance,n,found);
found[u] = TRUE;
cv=u;
printf("length=%d\t path\t[%d]", distance[u], cv);
while (parent[cv] >= 0) {
printf("<-[%d]", parent[cv]);
cv = parent[cv];
}
printf("\n");
for(w=0; w<n; w++)
if(!found[w] &&distance[u] + cost[u][w] <distance[w])
{
distance[w] = distance[u] + cost[u][w];
parent[w]=u;
}
}
}
int choose(int distance[] , int n, int found[])
{
int i, min, minpos;
min=INF;
minpos=-1;
for(i=0; i<n; i++)
if(distance[i]< min && !found[i]){
min = distance[i];
minpos =i;
}
return minpos;
}
void print(int distance[])
{
int i=0;
for(i=0; i<VERTICES; i++)
{
printf("%d\t", parent[i]);
}
printf("\n");
for(i=0; i<VERTICES; i++)
{
printf("%d\t", distance[i]);
}
printf("\n");
}
void print_path(int* parent, int n) {
int i;
int cv; // current vertex
for (i=0; i<n; ++i) {
cv = i;
printf("shortest path to %d :[%d]", cv, cv);
while (parent[cv] >= 0) {
printf("<-[%d]", parent[cv]);
cv = parent[cv];
}
printf("\n");
}
}
void main(){
shortestPath(0, cost, distance, VERTICES ,found);
print(distance);
}