上一篇文章介绍了求图上两点间最短路径的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的最短距离”等等~
网友评论