1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void dijkstra(int graph[][6],int len,int start){
	int isshort[len];/*记录是否找到最短路径*/
	int dis[len];
	int path[len];/*recode pre node*/	
	for(int i=0;i<len;i++){
		dis[i]=graph[start][i];
		if(graph[start][i]!=INF)
			path[i]=start;
		else
			path[i]=-1;
		isshort[i]=0;
	}
	isshort[start]=1;
	for(int i=0;i<len;i++){
		int min=INF;
		int minindex=-1;
		for(int j=0;j<len;j++){
			if(isshort[j]!=1&&dis[j]<min){
				min=dis[j];
				minindex=j;				
			}
		}
		isshort[minindex]=1;
		/*update the dis by shortest vtx*/
		for(int j=0;j<len;j++){
			if(isshort[j]!=1&&graph[minindex][j]!=0&&min+graph[minindex][j]<dis[j]){
				dis[j]=min+graph[minindex][j];
				path[j]=minindex;
			}
		}
	}
	printf("dis path\n");
	for(int i=0;i<len;i++)
		printf("%3d %3d\n",dis[i],path[i]);
}