Floyed-Warshall 算来自法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 注意单独一条边的路径也不一定是最佳路径。
来自 从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比星重足己知的路径更短。如果是更新它。
Pas360百科cal程序:
时间复杂度O(n^3),只要有存下邻接矩阵的空间，时间一般没问题，并且不必担心负权边的问题。
弗洛耶德算法(Floyed算法):
来自 基本思想:求解所有点间的路径需要进行n次试探。对于顶点i到顶点j的路径长度，首先考虑让路径经过顶点1，比较路径(i，j)和(i，1，j)的长度取其短者为当前求得的最短路径长度。对每一对顶点的路径都做这样的试探，则可360百科求得一个矩阵设为A(1)，求n次即得每对顶点间的最短路径A(n)。A(0)=A:邻接矩阵。如下图:
程序如下:
注律侵伟而绍控无乎意:弗洛耶德算法(Floyed算法)思想可用与判断有向图中任意两点是否连通?算法如下:
关注微信