标签: 最短路

1 篇文章

关于使用Floyd解决最短路问题的一些注意事项
根据Floyd算法我们可以通过状态转移方程解决一个无向图或者有向图中两点之间最短路径的问题,其时间复杂度为O(n³),空间复杂度可以控制在O(n²)(一般情况)。但是在实际运用中如果对Floyd三重循环的ijk顺序有改动,会导致无法正确得出两点之间的最短路径的问题。 正确的做法是   [code lang="cpp"] for(int k…