上一篇文章介绍了求图上两点间最短路径的Dijkstra算法,算法要求图上所有边的权重必须是不小于0的正数。如果不满足这个条件的话,算法可能无法找到正确的最短路径。比如在下面的例子中
使用Dijkstra算法求0点到2点间的最短路径,结果是直接从0到2,可是实际上0点到2点的最短路径是由0经过1再到2。
为什么会这样子呢?因为在Dijkstra算法中,每一次循环都会选中一个点,如果图中没有负权的边,那后面选中的点的最短路径只会增加,不会减少。可是当有负权边时,后面选中的点可能会更近,所以前面的选择就有待商榷了。可是Dijkstra算法并没有掉回头去修改前面选择的机制。
今天介绍另一个求最短路径的算法,Floyd算法,它能够克服负权边带来的问题,不要求边的权重为正数,不过依然要求图中没有负权边组成的回路(否则在这个回路中一直走下去,路径会越来越短~)。
不同于Dijkstra算法,Floyd算法的基于一个简单的观察,那就是在没有环路的由n个点组成的图中,两点间的最短路径,最多路过n个中间点。算法的基本思想是,找两点间最短路径的时候,限制允许通过的中间点数目,先找到只允许通过一个中间点的情况下,两点间的最短路径,然后找允许通过两个点情况下的最短路径,等等,直到条件放松到允许通过n个点,至此找到的就是无环路情况下的最短路径。
Floyd算法的求点i,j之间的最短距离实现如下
将图中的所有n个点依次带入下面的迭代循环:
对于点x,重新计算点i,j间的距离:如果dist[i,x]+dist[x,j]
= dist[i,x]+dist[x,j];
需要注意的是,随着循环的进行,dist[i,j]的意义一直在变化,它记录的是在允许经过那些已经被循环过的点的情况下,点i,j间的最短距离。也就是说,循环开始时,dist是i到j的直接距离,第一步之后是“允许经过点1的情况下,i,j的最短距离”,第二步之后是“允许经过点1和2的情况下,i,j的最短距离”等等~