本文最后更新于 2830 天前，其中的信息可能已经有所发展或是发生改变。
Table of Content
根据Floyd算法我们可以通过状态转移方程解决一个无向图或者有向图中两点之间最短路径的问题，其时间复杂度为O(n³),空间复杂度可以控制在O(n²)(一般情况)。但是在实际运用中如果对Floyd三重循环的ijk顺序有改动，会导致无法正确得出两点之间的最短路径的问题。
正确的做法是
[code lang=”cpp”]
for(int k=1;k<=border;k++)//i,j,k均从1开始
{
for(int i=1;i<=border;i++)
{
for(int j=1;j<=border;j++)
{
graph[i][j]=min(graph[i][k]+graph[k][j],graph[i][j]);
}
}
}
[/code]