图的最短路径

写于 | 归档 | | 翻阅:
| 共计: 549 字 | 时长 ≈ 2 min

Dijkstra : 从点v0开始，不断把距V0距离最小的点拉进超点（权重值一定要是正的）
Floyd : 如果i->k->j的距离比直接i->j要短的话，更新一下dist的距离和path的路径

Dijkstra

从点v0开始，不断把距V0距离最小的点拉进超点（注意：权重值一定要是正的）

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
​
void dijkstra(int G[N][N],int v0,int path[],int s[]){
	int dist[N];
	for(int i=0;i<N;i++){
		dist[i]=G[v0][i];
		if(dist[i]<INT_MAX) path[i]=v0;//记录前驱，即“0”
		else path[i] = -1; 
	}dist[v0]=-1;
	for(int a=0;a<N;a++){
		int idx=-1,min=INT_MAX;
		for(int i=0;i<N;i++){
			if(dist[i]>0&&dist[i]<min){
				idx = i;min = dist[i];
			}
		}
		if(idx<0) break;s[idx]=min;
		dist[idx] = -1;
		for(int i=0;i<N;i++){
			if(dist[i]>0&&G[idx][i]!=INT_MAX&&min+G[idx][i]<dist[i]){
				dist[i]=min+G[idx][i];
				path[i] = idx;
			}
		}
	}
}
void print(int path[N],int s[N]){
	for(int i=0;i<N;i++) if(path[i]>=0) printf("node :%2d(pre:%2d) s:%d \n",i,path[i],s[i]);
}
​

Floyd

如果i->k->j的距离比直接i->j要短的话，更新一下dist的距离和path的路径。

（特别注意：关于循环的顺序，k一定在最外层循环，不然程序会出现差错，以下给出解释：k在最外层保证了每次k变动后会遍历图上所有的点以达成完备的更新。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
​
void dist_init(int dist[N][N]){
	freopen("SP_edge.txt","r",stdin);
	for(int i=0;i<N;i++) for(int j=0;j<N;j++) dist[i][j]=INT_MAX;
	int va,vb,cost;
	while(scanf("%d %d %d\n",&va,&vb,&cost)==3) dist[va][vb] = cost;
	for(int i=0;i<N;i++) dist[i][i] = 0;
}
void path_init(int path[N][N]){
	for(int i=0;i<N;i++) for(int j=0;j<N;j++) path[i][j]=i;
}
void floyd(int dist[N][N],int path[N][N]){
	for(int k=0;j<N;j++){
		for(int i=0;i<N;i++){
			for(int j=0;k<N;k++){
				if(dist[i][k]+dist[k][j]<dist[i][j]&&dist[i][k]!=INT_MAX&&dist[k][j]!=INT_MAX){
					dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;
				}
			}
		}
	}
}
​