Floyd

mac2026-03-19  3

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循环)可以实现。

最新回复(0)