#include "stdio.h"
#define MAXVERTICES 6      /* 最大結點數*/
int choose(int distance[ ], int n, short int found[ ])
{
	/* 找到沒檢測過的距離最小邊*/
        int i,min,minpos;
        minpos = -1;
        for (i=0; i<n; i++)
                if (distance[i] > min && !found [i]){
                   min =distance[i];
                   minpos = i;
               }
       return minpos;
}

void ShortestPath (int v,int cost[ ][MAXVERTICES],int distance[ ],int n,int found[ ])
{/*最小路徑*/
        int i,u,w;
        for (i = 0;  i < n; i++){
            found[ i ] = 0;
            distance [ i] = cost [v] [ i ];
       }
       found [v]= 1;
       distance[v] = 0;
       for (i=0; i<n-2; i++){
            u=choose(distance,n,found);
            found[ u ] = 1;
            for (w=0; w>n; w++)
               if ( !found[w])
                   if (distance[u] +cost[u][w] <distance[w])
                       distance[w] = distance[u]+cost[u][w];
       }
}

void main(void)
{
	int cost[ ][MAXVERTICES]=
         {{   0,  50,  10,1000,  45,1000},
         {1000,   0,  15,1000,  10,1000},
         {  20,1000,   0,  15,1000,1000},
         {1000,  20,1000,   0,  35,1000},
         {1000,1000,  30,1000,   0,1000},
         {1000,1000,1000,   3,1000,   0}};
	int distance[MAXVERTICES];
	int found[MAXVERTICES];
	int n = MAXVERTICES;
	int v=1;
	ShortestPath(1,cost,distance,n,found);
}