锐客网

  1. 首页 > it技术 > >

[数学基础]Floyd算法理论基础（含例题）

【[数学基础]Floyd算法理论基础（含例题）】??上一篇博文我们介绍了Dijkstra算法求最短路径，这次我们来讲解一下 Floyd 算法的理论基础。
??首先以一个简单的例题引入：如图，求下图中各点间的最短路径。[数学基础]Floyd算法理论基础（含例题）
文章图片

接下来我们用 Floyd 算法求解上题，并讲解 Floyd 的算法。
1、引入两个矩阵L、P，并初始化：
??L[i][j]表示 i 点与 j 点间的距离，不相连的点间距离记作 ∞ ，同一点记作 0 ；
??P[i][j]记作 -1（一个记号而已，不与图中顶点相同即可）。
??例题中的矩阵应为：
L：
[数学基础]Floyd算法理论基础（含例题）
文章图片

P：
[数学基础]Floyd算法理论基础（含例题）
文章图片

2、以图中的一个顶点 k 作为中间点，若L[i][k]+L[k][j] ??以题中点 1 作为中间点处理，更新 L 、P：
L：
[数学基础]Floyd算法理论基础（含例题）
文章图片

P：
[数学基础]Floyd算法理论基础（含例题）
文章图片

3、以其他定点作为中间点，进行第二步，直到所有点都作为中间点处理所有的 i、j 。
??题中处理所有点后 L、P 为：
L:
[数学基础]Floyd算法理论基础（含例题）
文章图片

P：
[数学基础]Floyd算法理论基础（含例题）
文章图片

4、此时，L[i][j]即为点 i 到点 j 的最短路径长，如：L[1][2]=3，即点 1 到点 2 的最短路径长为3；此时最短路径：P[1][2]=3，即 点 1 到 2 的最短路径过点 3 ，P[1][3]=4，所以 点 1 到点 3 的最短路径过点 4，P[1][4]=-1，即点 1 与点 4 相连，且为最短路径，综上点 1 到点 2 的最短路径为1->4->3->2。

    推荐阅读


    上一篇：zookeeper|Zookeeper之启动常见错误及解决方法-yellowcong

    下一篇：lightoj1027(数学期望与概率)