Floyd算法:把每个点作为起点,求解n次单源最短路问题。
该算法分为三个阶段:
for(int k
=1;k
<=n
;k
++)
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
第一维K是中间点,第二维i是起点,第三维j是终点。
那么内部该怎么操作呢:
for(int k
=1;k
<=n
;k
++)
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
dist
[i
][j
]=min(dist
[i
][j
],dist
[i
][k
]+dist
[k
][j
]);
其中,dist二维数组储存i与j的最短距离,可以通过枚举所有的中间点(即最外层for循环)可以实现。