floyd最短路算法 | Eternal_zttz

floyd最短路算法

Floyd算法是一种动态规划算法,适用于多源最短路径,相对于Dijkstra算法和SPFA算法,其算法复杂度较高,时间复杂度为O(n^3),但其理解较为容易,且代码简单。
其基本思想便是对点松弛,在任意 i,j 顶点中,看是否存在顶底k,使得i -> k -> j 的距离小于i -> j的距离,如果存在,则对该两点进行松弛操作。

核心代码:

1
2
3
4
5
6
7
8
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];
}
}
}

完整代码:

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
#include <stdio.h>
int e[1000][1000];
int main(){
int n,m,t1,t2,t3;
int inf = 9999999;
scanf("%d %d",&n,&m);
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;
}
for (int i =1 ;i<=m;i++){
scanf("%d %d %d",&t1,&t2,&t3);
//这里if主要是为了在存在多条从t1到t2的路径时,记录最短的一条
if(e[t1][t2]>t3)
e[t1][t2] = t3;
}

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];
}
}
}
for (int i =1 ;i<=n;i++){
for (int j = 1;j<=n;j++)
printf("%d ",e[i][j]);
printf("\n");
}
return 0;
}


测试数据:

1
2
3
4
5
6
7
8
9
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12

输出:

1
2
3
4
0 2 5 4 
9 0 3 4
6 8 0 1
5 7 10 0


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