??上一篇博文我们介绍了Dijkstra算法求最短路径这次我们来讲解一下 floyd warshall算法 算法的理论基础。
??首先以一个简单的例题引入：如图求下图中各点间的最短路径。
接下来我們用 floyd warshall算法 算法求解上题并讲解 floyd warshall算法 的算法。
1、引入两个矩阵L、P并初始化：
??L[i][j]表示 i 点与 j 点间的距离，不相连的点间距离记作 ∞ 同一點记作 0 ；
??P[i][j]记作 -1（一个记号而已，不与图中顶点相同即可）
??例题中的矩阵应为：
??以题中点 1 作为中间点处理，更新 L 、P：
3、以其怹定点作为中间点进行第二步，直到所有点都作为中间点处理所有的 i、j
??题中处理所有点后 L、P 为：