Floyd算法记录路径 | Eternal_zttz

Floyd算法记录路径

关于Floyd算法记录路径的方法一般有两种:一是用path[i][j]记录i的后继节点,二是用path[i][j]记录j的前驱节点。

第一种方法:利用path[i][j]记录i的后继节点。
路径记录关键代码:
1: 初始化:

1
path[i][j] = j;

2:路径转移记录:

1
path[i][j] = path[i][k];

完整代码:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 10000001
int e[1001][1001];
int path[1001][1001];
int n,m,t1,t2,t3;
void init(){
//初始化e,path数组
memset(e,0,sizeof(e));
memset(path,0,sizeof(path));
for (int i = 1;i<=n;i++){
for (int j = 1;j<=n;j++){
if(i == j)
e[i][j] = 0;
else
e[i][j] = INF;
path[i][j] = j;
}
}
//输入边
for (int i =1;i<=m;i++){
scanf("%d %d %d",&t1,&t2,&t3);
if(e[t1][t2]>t3)
e[t1][t2] = t3;
}
}
void Floyd(){
//floyd算法
for (int k =1;k<=n;k++){
for (int i = 1;i<=n;i++){
for (int j =1;j<=n;j++){
if(e[i][j]>e[i][k]+e[k][j]){
e[i][j]=e[i][k]+e[k][j];
path[i][j] = path[i][k];
}
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
init();
Floyd();
int start,end;
//得出从start 到end 的路径
while(~scanf("%d %d",&start,&end)){
if(start == end){
printf("从%d到%d的最优路线 : %d\n",start,end,start);
printf("最短路径:%d\n",0);
}
else{
printf("从%d到%d的最短路线:%d",start,end,start);
int now= path[start][end];
while(1){
printf("-->%d",now);
if(now == end)
break;
now = path[now][end];
}
printf("\n");
printf("最短路径:%d\n",e[start][end]);
}
}
return 0;
}


第二种方法:利用path[i][j]记录j的前驱节点,这个方法需要利用stack来输出路径
路径记录关键代码:
1:初始化:

1
pre[i][j] = i;

2:路径转移记录:

1
pre[i][j] = pre[k][j];

完整代码:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define INF 10000001
using namespace std;
int e[1001][1001];
int pre[1001][1001];
int n,m,t1,t2,t3;
void init(){
memset(e,0,sizeof(e));
memset(pre, 0, sizeof(pre));
for (int i =1;i<=n;i++){
for (int j =1;j<=n;j++){
e[i][j] = i==j? 0:INF;
pre[i][j] = i;
}
}
for (int i = 1;i<=m;i++){
scanf("%d %d %d",&t1,&t2,&t3);
if(e[t1][t2]>t3)
e[t1][t2] = t3;
}
}
void Floyd(){
for (int k =1;k<=n;k++){
for (int i = 1;i<=n;i++){
for (int j =1;j<=n;j++){
if(e[i][j]>e[i][k]+e[k][j]){
e[i][j] = e[i][k]+e[k][j];
pre[i][j] = pre[k][j];
}
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
init();
Floyd();
int start,end;
while(~scanf("%d %d",&start,&end)){
if(start == end){
printf("从 %d 到 %d 的最短路线:%d\n",start,end,start);
printf("最短路径:%d\n",0);
}else{
int now = pre[start][end];
stack<int>path;
path.push(end);
while(1){
path.push(now);
if(now == start)
break;
now = pre[start][now];
}
printf("从 %d 到 %d 的最短路线:%d",start,end,start);
path.pop();
while(!path.empty()){
printf("-->%d",path.top());
path.pop();
}
printf("\n");
printf("最短路径:%d\n",e[start][end]);
}
}
return 0;
}

-------------The End-------------