Floyd算法

算法思想

Floyd算法是一个可以处理有向图或负权重的最短路径问题的一个算法。她的算法思想很简单，就是：

如果想要让任意两个点间的距离缩短，那么必然要引入第三个点，只有通过第三个点的中转，才能实现缩短路程。

假设$D_{i,j,k}$为$i$到$j$的只以$(1,k)$集合中的节点为中间节点的最短路径的长度，那么如果最短路径经过$k$点，则：

$$D_{i,j,k} = D_{i,j,k-1} +D_{k,j,k-1}$$

如果最短路径不经过点$k$，则：

$$D_{i,j,k} = D_{i,j,k-1}$$

因此：

$$D_{i,j,k} = min(D_{i,j,k-1}, D_{i,j,k-1} +D_{k,j,k-1} )$$

距离实例解析：

请参见下面的案例：

只有5行代码的Floy算法

5行代码的实现

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(e[i][j]>e[i][k]+e[k][j])
                 e[i][j]=e[i][k]+e[k][j];

已案例中的例子分析一下这段代码：

当$k=2$时，if之前，$e[i][j]$为$i$到$j$的直达，或$i$到$j$经过点1的距离的最小值

所以$k=2$时，整个函数是$i$到$j$经过2的的距离或$i$到$j$的直达，或$i$到$j$经过1，2的距离的最小值。

Floyd是多源路径算法，能够求得任意两点之间的距离。就是效率比较差，时间复杂度为$O(N^3)$,空间复杂度为$O(N^2)$。