2008年9月10日星期三

Floyd-Warshall 算法及其优化

今天是教师节,因而下午放假,有了些复习时间。上午挺强的,几个老师被我们用彩带一顿狂喷,有几个还被迫唱歌了。因为前方黑板被占(几个大字),有两个老师是站在后面上课的(后面有空黑板),这下我这类最后一排的有福了。不过后黑板平时无人使用,没放板擦、粉笔,两节课都是我主动到前面去拿来的。第一节是灵感突发,第二节我看没人接班,无奈,只得又去一趟。算是RP++吧。

好了,言归正传。Floyd-Warshall 算法解决了有向图中每对定点间最短路径的问题,时间O(V3),空间O(V2)。适用条件是,换句话说限制是,不能有负权值环,当然还有,最多只能有一条从一个点到另一个点的弧(基本都是这样。不然,长的那个可以直接去掉,没用)。对于无向图,把一条边变成两条弧。尽管有负权值环时它不可用,但可以判断是否有负权值环,方法是再运行一次(不过代价不小)。

这是个动态规划算法,基本思想如下。如果顶点k在顶点i到顶点j的一条路径上,则称k为该路径的一个中间顶点。如果路径p是从i到j的最短路径且k是其中间顶点之一,则以k为界将该路径分成两段,每段都是最短路径。(不然的话会出来一个更短的。)相反,如果路径a, b分别是i->k, k->j的最短路径,将a和b合并起来的路径不一定是最短路径。为了得到最短路径,我们必须考察图中的所有顶点,以他们为中间顶点,合并起来才能是最短的。基于此,我们可以得到算法。用邻接矩阵表示图,算法如下(C++)。

for (int k=1;k<=n;++k)
for (int i=1;i<=n;++i)
if (ans[i][k] != _infty) //the one line optimization
for (int j=1;j<=n;++j)
ans[i][j]=min(ans[i][j], ans[i][k] + ans[k][j]);

那个仅一行的优化是我后加的,可以去掉。预处理时[i][i]为0,有弧的是权值,没有的是无穷大。_infty是预处理时当作无穷大的量。优化后的具体时间复杂度我一直没有做出来,总之松弛的界是Ω(VE)和O(V3)。这个算法极其简洁,我认为是最优美的算法。(其次是堆。)上述代码整合到程序中后,通过编译且运行正确。

2 条评论:

leokan 说...

复杂度我可以告诉你还是O(n^3)
这个优化是只要写floyd都会加上去的...
还有...堆,spfa,bellmanford,群蚁,甚至是启发式搜索都能比这个来的快吧

水墨青花 说...

floyd是全點對最短路徑算法,bellmanford只是單源最短路算法,其複雜度為O(VE)稠密圖是O(n^3),目前已知最快的單源最短路算法是Dijkstra加FibonacciHeap複雜度為O(E+VlogV),E在稠密圖相當於V^2,可以知道你所謂堆的算法在全點隊上的表現仍然不及Floyd,至於spfa,他只不過是bellmanford的優化而已,最糟的複雜度還是O(VE),接下來是群蟻(蟻群)其實也是啟發式搜索的一種(或稱超啟發式搜索),啟發式搜索並不能保證得到正確的最短路,亦即犧牲正確性來獲得時間,也無法證明他至少能近似到一定程度,一般用在工程中,並不做數學上的討論。