//程序實例8_6
//Dijkstra算法求最短路徑
#include<stdio.h>
#define Max 100
#define I 32767

void print_path(int dist[],int path[],int s[],int n,int v0)
{
	int i,k;
	for(i=1;i<=n;i++)
		if(s[i]==1)
		{
			k=i;
			printf("%d到%d的最短路徑為：",v0,i);
			while (k!=v0)
			{
				printf("%d<-",k);
				k=path[k];
			}
			printf("%d",k);
			printf("\n路徑長度為:  %d\n",dist[i]);
			printf("\n");
		}
		else
			printf("%d<-%d  路徑不存在!",i,v0);
}

void shortest(int cost[][7],int dist[],int path[],int n,int v0)	
//cost[][]為帶權鄰接矩陣
//dist[i]為從源點v到終點vi的最短路徑長度
//path[i]為從源點v到終點vi的最短路徑中的前一個頂點的編號
{
	int s[Max],i,j,k,min;
	for(i=1;i<=n;i++)    //初始化
	{	dist[i]=cost[v0-1][i-1];
		s[i]=0;          //0表示頂點不在S集合中，1則相反
		if(cost[v0-1][i-1]<I)	path[i]=v0;
		else		path[i]=0;
	}
	s[v0]=1;path[v0]=0;     //源點v0放入S中
	for(i=1;i<=n;i++)       //對所有的n個頂點
	{	min=I;	k=0;
		for(j=1;j<=n;j++)   //選取不在S中且具有最小距離的頂點k
			if(s[j]==0)
				if(dist[j]!=0 && dist[j]<min)
				{	min=dist[j];	k=j;	}
		s[k]=1;               //把頂點k加入S中
		for(j=1;j<=n;j++)     //修改不在S中的頂點的距離
			if(s[j]==0)
		    if(cost[k-1][j-1]<I && dist[k]+cost[k-1][j-1]<dist[j])
				{	dist[j]=dist[k]+cost[k-1][j-1];
					path[j]=k;
				}
	}
	print_path(dist,path,s,n,v0);
}

void main()
{	int cost[][7]={{0,15,I,4,I,I,I},	{I,0,I,I,2,I,8},
					{9,I,0,I,I,I,I},	{I,5,I,0,I,6,I},
					{I,I,I,I,0,I,3},	{I,I,12,I,I,0,16},
					{I,I,I,11,I,I,0}};
	int dist[Max], path[Max],n,v0;
	n=7; 	v0=1;
	shortest(cost,dist,path,n,v0);
}