#include <stdio.h>
#define MAXVEX 100
#define INF 32767
void Dijkstra(int cost[][MAXVEX],int n,int v)
{
	int dist[MAXVEX],path[MAXVEX];
	int s[MAXVEX];
	int mindis,i,j,u,pre;
	for (i=0;i<n;i++) 
	{	
		dist[i]=cost[v][i];   		/*距離初始化*/
		s[i]=0;                		/*s[]置空*/
		if (cost[v][i]<INF)			/*路徑初始化*/
			path[i]=v;
		else
		    path[i]=-1;
	}
	s[v]=1;path[v]=0;        		/*源點編號v放入s中*/
	for (i=0;i<n;i++)     			/*循環直到所有頂點的最短路徑都求出*/
	{	
		mindis=INF;
		u=-1;
		for (j=0;j<n;j++)     		/*選取不在s中且具有最小距離的頂點u*/
			if (s[j]==0 && dist[j]<mindis) 
			{ 	
				u=j;
				mindis=dist[j];	
			}
		if (u!=-1)						/*找到最小距離的頂點u*/
		{	s[u]=1; 					/*頂點u加入s中*/
			for (j=0;j<n;j++)      		/*修改不在s中的頂點的距離*/
				if (s[j]==0) 
					if (cost[u][j]<INF && dist[u]+cost[u][j]<dist[j]) 
					{	
						dist[j]=dist[u]+cost[u][j];
						path[j]=u;
					} 
		}
	}
	printf("\n Dijkstra算法求解如下:\n"); 
	for (i=0;i<n;i++)				/*輸出最短路徑長度,路徑逆序輸出*/
	{
		if (i!=v)
		{	
			printf("  %d->%d:",v,i);
			if (s[i]==1)  
			{	
				printf("路徑長度為%2d ",dist[i]);
				pre=i;
				printf("路徑逆序為");
				while (pre!=v)		/*一直求解到初始頂點*/
				{	
					printf("%d,",pre);
					pre=path[pre];
				}
				printf("%d\n",pre);
			}
			else
				printf("不存在路徑\n");
		}
	}
}
void main()
{
	int cost[6][MAXVEX]={		/*圖6.9的代價矩陣*/
		{0,50,10,INF,INF,INF},
		{INF,0,15,50,10,INF},
		{20,INF,0,15,INF,INF},
		{INF,20,INF,0,35,INF},
		{INF,INF,INF,30,0,INF},
		{INF,INF,INF,3,INF,0}};
	Dijkstra(cost,6,1);
	printf("\n");
}