#include?
#include?
#define?INFINITY?99999

int?FindMinLabel（int?*?Label?int?*visit?int?num）;
int?UpdateLabel（int?*?Label?int?currentlabel?int?arr[6][6]?int?num）;
void?ShowPath（int?*?Label?int?destination?int?start?int?arr[6][6]?int?num）;

int?main（void）
{
	
	printf（“This?program?finds?the?shortest?path?for?a?graph.\n“）;
	//initialize?graph
	int?graph[6][6]={
		{INFINITY43INFINITYINFINITYINFINITY}
		{INFINITYINFINITYINFINITY32INFINITY}
		{INFINITYINFINITYINFINITYINFINITY3INFINITY}
		{INFINITYINFINITYINFINITYINFINITYINFINITY2}
		{INFINITYINFINITYINFINITYINFINITYINFINITY2}
		{INFINITYINFINITYINFINITYINFINITYINFINITYINFINITY}
	};

	//initialize?label?&?previous?node?info
	int?label[6]={INFINITYINFINITYINFINITYINFINITYINFINITYINFINITY};
	int?visited[6]={000000};
	

????//input?OD?nodes
	int?origin?destination;
	printf（“Please?enter?the?origin?node:?“）;
	scanf（“%d“?&origin）;
	printf（“Please?enter?the?destination?node:?“）;
	scanf（“%d“?&destination）;

	int?current?=?origin;
	int?temp;
	label[current-1]?=?0;

	//update?label
	while（current!=destination）{
		if（UpdateLabel（labelcurrentgraph6）?||?graph[current-1][destination-1]!=INFINITY）{
			visited[current-1]=1;
			temp=FindMinLabel（labelvisited6）;
			current=temp+1;
		}

		else
			break;
	}
		
		if（current==destination）
			ShowPath（labeldestination?origingraph6）;
		else
			printf（“These?is?no?path?from?node?%d?to?node?%d.\n“?origin?destination）;

	system（“pause“）;
	return?0;
}


int?UpdateLabel（int?*?Label?int?currentlabel?int?arr[6][6]?int?num）{
	int?i;
	int?IsUpdated=0;
	for（i=0;i		if（Label[currentlabel-1]+arr[currentlabel-1][i]		{
			Label[i]=Label[currentlabel-1]+arr[currentlabel-1][i];
			IsUpdated=1;
		}
????}
	return?IsUpdated;
}

int?FindMinLabel（int?*?Label?int?*?visit?int?num）{
	int?i;
	int?node;
	int?minlabelvalue=INFINITY;
	for（i=0;?i		if（Label[i]			minlabelvalue=Label[i];
			node=i;
		}
	}
	return?node;
}

void?ShowPath（int?*?Label?int?destinationint?start?int?arr[6][6]?int?num）{

		int?path[6]={000000};
		int?node=destination;
		int?i=0;
		int?count=0;
		int?j;
		path[0]=node;
		while?（node!=start）{
			for（i=0;i				if（arr[i][node-1]==Label[node-1]-Label[i]）{
					count++;
					path[count]=i+1;
					break;
				}
			}
			node=i+1;
		}
		printf（“The?shortest?path?from?node?%d?to?node?%d?is:?\n“start?destination）;
		for（j=count;j>=0;j--）
			printf（“%d?“path[j]）;
	}
???

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????30208??2011-03-02?21:43??ShortestPath\Debug\ShortestPath.exe

?????文件?????309256??2011-03-02?21:43??ShortestPath\Debug\ShortestPath.ilk

?????文件?????355328??2011-03-02?21:43??ShortestPath\Debug\ShortestPath.pdb

?????文件???????8614??2011-03-02?21:43??ShortestPath\ShortestPath\Debug\BuildLog.htm

?????文件??????12639??2011-03-02?21:43??ShortestPath\ShortestPath\Debug\Dijkstra.obj

?????文件?????????65??2011-03-02?21:43??ShortestPath\ShortestPath\Debug\mt.dep

?????文件????????621??2011-03-02?21:43??ShortestPath\ShortestPath\Debug\ShortestPath.exe.intermediate.manifest

?????文件??????44032??2011-03-02?21:43??ShortestPath\ShortestPath\Debug\vc90.idb

?????文件??????61440??2011-03-02?21:43??ShortestPath\ShortestPath\Debug\vc90.pdb

?????文件???????2689??2011-03-02?21:43??ShortestPath\ShortestPath\Dijkstra.cpp

?????文件???????6354??2011-03-02?15:52??ShortestPath\ShortestPath\Release\BuildLog.htm

?????文件??????11264??2011-03-02?15:52??ShortestPath\ShortestPath\Release\vc90.idb

?????文件??????36864??2011-03-02?15:52??ShortestPath\ShortestPath\Release\vc90.pdb

?????文件???????3654??2011-03-02?16:45??ShortestPath\ShortestPath\ShortestPath.vcproj

?????文件???????1415??2011-03-02?21:54??ShortestPath\ShortestPath\ShortestPath.vcproj.zywu-VAIO.zywu.user

?????文件????1084416??2011-03-02?21:54??ShortestPath\ShortestPath.ncb

?????文件????????902??2011-03-02?13:25??ShortestPath\ShortestPath.sln

????..A..H.?????11776??2011-03-02?21:54??ShortestPath\ShortestPath.suo

?????目錄??????????0??2011-03-06?10:37??ShortestPath\ShortestPath\Debug

?????目錄??????????0??2011-03-06?10:37??ShortestPath\ShortestPath\Release

?????目錄??????????0??2011-03-06?10:37??ShortestPath\Debug

?????目錄??????????0??2011-03-06?10:37??ShortestPath\ShortestPath

?????目錄??????????0??2011-03-06?10:37??ShortestPath

-----------?---------??----------?-----??----

??????????????1981537????????????????????23