// 單源最短路徑Dijkstra算法

#include <stdio.h>
#define VertexNum 5	//頂點數(shù)
#define EdgeNum 7	//邊數(shù)
#define X 10000		//最大權(quán)值

// 鄰接矩陣初值(權(quán)值)
int Graph[VertexNum][VertexNum]=
{	//1   2   3   4   5
	  X, 10,  X, 30,100, //1
	  X,  X, 50,  X,  X, //2
	  X,  X,  X,  X, 10, //3
	  X,  X, 20,  X, 60, //4
	  X,  X,  X,  X,  X, //5
};

int Visited[VertexNum];		//訪問標(biāo)識(0或1)
int path[VertexNum];		//最短路徑序列
int Distance[VertexNum];	//最短路徑值

// Dijkstra算法，Begin為源點
void Dijkstra(int Begin)
{
	//輸出原始數(shù)據(jù)
	int MinEdge,i,j,Vertex;
	printf("          1   2   3   4   5\n");
	printf("----------------------------\n");
	printf("s:%d (V)",Begin);
	for(i=0; i<VertexNum; i++)
		if (Distance[i]==X) printf("  ∞");
		else printf("%4d",Distance[i]);
	printf("\n");

	//尋找n-1條最小路徑
	for(j=1; j<VertexNum; j++)
	{
		//尋找當(dāng)前最小路徑值
		MinEdge=X;
		Vertex=0;
		for(i=0; i<VertexNum; i++)
			if (Visited[i]==0 && Distance[i]<MinEdge)
			{
				Vertex=i;
				MinEdge=Distance[i];
			}
		Visited[Vertex]=1;	//Vertex頂點已訪問

		//重新計算當(dāng)前最短路徑
		printf("s:%d (%d)",j,Vertex+1);
		for(i=0; i<VertexNum; i++)
		{
			int sum=Distance[Vertex]+Graph[Vertex][i];
			if (Visited[i]==0 && sum<Distance[i])
			{
				Distance[i]=sum;
				path[i]=Vertex;
			}
			if (Distance[i]==X) printf("  ∞");
			else printf("%4d",Distance[i]);
		}
		printf("\n");
//for(i=0; i<VertexNum; i++) printf("%4d",path[i]+1);
//printf("\n");
	}
}

void main()
{
	int i,j,k=0;
	//設(shè)置初值
	for(i=0; i<VertexNum; i++) 
	{
		Visited[i]=0;
		path[i]=k;
		Distance[i]=Graph[k][i];
	}
	Visited[k]=1;	//源點已訪問

	Dijkstra(k);	//頂點1為源點

	//輸出所有最短路徑
	printf("\nAll Path:\n");
	for(i=1; i<VertexNum; i++)
	{
		j=i;
		printf("Path%d: [%d]  ",i,Distance[i]);
		do
		{
			printf("%d<--",j+1);
			j=path[j];
		} while(j!=0);
		printf("1\n");
	}
	printf("\n");
}