迪杰斯特拉算法C实现

利用C实现经典的迪杰斯特拉算法，用于最短路问题的实现。

#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[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