网站开发 360百科,大连哪里有手机自适应网站建设维护,从事网站建,什么是网站的后台摘要#xff1a; 1#xff0c;Floyd算法的介绍和实现步骤 2#xff0c;Floyd算法的代码实现和优化 3#xff0c;Floyd算法最短路径打印 4#xff0c;Floyd算法为什么要先遍历中间顶点 k 1#xff0c;Floyd算法的介绍和实现步骤 在前面我们讲过迪杰斯特拉算法#xff0c… 摘要 1Floyd算法的介绍和实现步骤 2Floyd算法的代码实现和优化 3Floyd算法最短路径打印 4Floyd算法为什么要先遍历中间顶点 k 1Floyd算法的介绍和实现步骤 在前面我们讲过迪杰斯特拉算法Bellman-Ford算法以及SPFA算法这些都是求单源点最短路径也就是从计算从一个点到其他所有点的最短路径。而弗洛伊德(Floyd-Warshall)算法是求多源点最短路径的就是求任意两个顶点之间的最短距离可以有负权边都不能有负权回路。 我们来思考这样一个问题如果知道 A 到 B 的距离是 x 这个 x 可能是一个确定的值也可能是无穷大怎么才能使 x 的值变小呢 唯一的解决方式就是找一个中转点 C 判断 A 到 C 的距离加上 C 到 B 的距离是否小于 A 到 B 的距离如果小于就更新 A 到 B 的值如果不小于 A 到 B 的值就不变。 如下图所示A 到 B 的直线距离是 9 如果经过顶点 C 中转距离就会变成 7 。 只需要把所有的点都作为中转点枚举一遍即可很明显这是一道动态规划的问题我们定义 dp[k][i][j] 表示经过前 k 个顶点从 i 到 j 的最短距离。 1如果不经过第 k 个顶点中转那么 dp[k][i][j]dp[k-1][i][j]。 2如果经过第 k 个顶点中转那么 dp[k][i][j]dp[k-1][i][k]dp[k-1][k][j]。 只需要取他们的最小值即可也就是 dp[k][i][j] min(dp[k - 1][i][j], dp[k - 1][i][k] dp[k - 1][k][j]); 我们来画个图看下
