图-弗洛伊德(Floyd)算法

弗洛伊德(Floyd)算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的的一种，可以正确处理或负权的最短路径问题。

Floyd-Warshall算法的为O(N³)，为O(N²)。

原理

Floyd-Warshall算法的原理是。

设D_i,j,k为从i到j的只以(1..k)集合中的节点为中间结点的最短路径的长度。

1. 若最短路径经过点k，则D_i,j,k = D_{i,k,k − 1} + D_{k,j,k − 1}；
2. 若最短路径不经过点k，则D_i,j,k = D_{i,j,k − 1}。

因此，D_i,j,k = min(D_{i,k,k − 1} + D_{k,j,k − 1},D_{i,j,k − 1})。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。（见下面的算法描述）

算法描述

Floyd-Warshall算法的描述如下：

for k ← 1 to n do
  for i ← 1 to n do
    for j ← 1 to n do
      if (Di,k + Dk,j < Di,j) then
        Di,j ← Di,k + Dk,j;

其中D_i,j表示由点i到点j的代价，当D_i,j为 ∞ 表示两点之间没有任何连接。

弗洛伊德（Floyd）算法过程：
１、用D[v][w]记录每一对顶点的最短距离。
２、依次扫描每一个点，并以其为基点再遍历所有每一对顶点D[][]的值，看看是否可用过该基点让这对顶点间的距离更小。
算法理解：
最短距离有三种情况：
１、两点的直达距离最短。（如下图）
２、两点间只通过一个中间点而距离最短。（图）
３、两点间用通过两各以上的顶点而距离最短。（图）

对于第一种情况：在初始化的时候就已经找出来了且以后也不会更改到。
对于第二种情况：弗洛伊德算法的基本操作就是对于每一对顶点，遍历所有其它顶点，看看可否通过这一个顶点让这对顶点距离更短，也就是遍历了图中所有的三角形（算法中对同一个三角形扫描了九次，原则上只用扫描三次即可，但要加入判断，效率更低）。
对 于第三种情况：如下图的五边形，可先找一点（比如x，使=2），就变成了四边形问题，再找一点（比如y,使

原文参考：