关于最短路之Floyd

前面的废话

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

——摘自wiki百科

说人话的话就是:在一个图中找到两点之间的最短路(和引用有什么区别

而这篇文章的主题就是解决最短路问题的算法中较为简单说白了是我菜的Floyd算法

这个算法的强大之处在于代码极短且可以求出一个图内所有的最短路

虽然效率是O(N^3)

开始瞎讲

Floyd算法的思想是动态规划

需要一个数组实现

我们定义dis[i,j]为点i到点j的最短路大小,cost[i,j]为i与j之间的边权,如果没有边则cost[i,j]=∞

从任意的节点i到节点j,其最短路只有两种可能,一是直接从i到j,二是从i经过一些节点到j

那么转移方程就是dis[i,j]=min{dis[i,k]+dis[k,j]} k∈(1,n)

这很DP

代码实现

for (int k=1;k<=n;k++)
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

当然你可能会问……

为什么k在循环的外层?

又或者是考虑后效性的问题?(即开始是会不会dis[i,k]与dis[k,j]并不是最优解,导致dis[i,j]的更新不是最优的)

关于这些问题推荐一篇blog

这里简单讲一下

实现原理

需要证明的是

i和j之间的最短路径上的结点集里(不包含i,j),编号最大的一个是x.那么在外循环k=x时,d[i][j]肯定得到了最小值.

可以用到强归纳法

设i到x中间编号最大的是x1,x到j中间编号最大的是x2.

由于x是i到j中间编号最大的,那么显然x1<x,x2<x.

根据结论,k=x1的时候d[i][x]已经取得最小值,k=x2的时候d[x][j]已经取得最小值.

那么就是k=x的时候,d[i][x]和d[x][j]肯定都已经取得了最小值.

因此k=x的时候,执行d[i][j]=min(d[i][j],d[i][x]+d[x][j])肯定会取得d[i][j]的最小值.

证毕.

以上

所以可以证明DP的式子和循环的嵌套的正确性

并且不会出现之前讲到的类似于后效性的问题

这点是Floyd最难的一点

不过在运用中貌似并不需要了解那么多……

“关于最短路之Floyd”的一个回复

发表评论