最小費用最大流 修改的dijkstra + Ford-Fulksonff算法
修改的dijkstra其實和Johnson算法的思想是一致的。
一個求最小費用最大流的樸素算法是這樣的：
1 求最小費用增廣路
2 判斷是否存在增廣路，否的話算法終止。
3 增加增廣路上邊的流量
4 在增廣路上添加必要的逆向負權邊
5 goto 1
因為負權邊的存在，求最小費用增廣路就不可以用dijkstra算法。當然，我們可以用bellman-ford算法，可是這樣的話求一次最短路的時間代價就是O(e*n)，e是邊數，n是頂點數。代價大了點，如果能用dijkstra算法就好了。利用Johnson算法的思想，這是可以做到的。
第一次求最短路可以用dijkstra算法（如果一開始就有負權邊，那就用bellman-ford算法，這沒關系），求出源點到所有點的距離，嗯，我說的距離是指路徑上邊的費用之和的最小值。注意，要求出到所有點的距離，而不是求出到匯點的距離就完事了。
假設有一條邊u->v，源點到u的距離是d[u]，到v的距離是d[v]，邊的費用（權值）是w(u，v)。很顯然，d[u]+w(u,v)>=d[v]，不然的話，你會發現一條更好的路徑從源點到v。問題是，什么時候取等呢？當u->v在v的最優路徑上，范圍說小一點，當u->v在從源點到匯點的最優路徑，即最小費用增廣路上。
好的，如果u->v被你增載了，你要開始添負權邊v->u了，權值取負，就是-w(u,v)。負權就是討厭，是正的就好了，dijkstra算法就可以再用了。怎么辦呢，把負權邊加個權值，讓它非負。要加多少呢，d[v]-d[u]。當然不能只加一條邊，對所有邊，無論原有的還是新添的，按這個規則加，構造一個新的圖：
對邊a->b，新的邊權w'(a,b)=w(a,b)+d[a]-d[b]
現在來看看你的杰作：
對原來的邊u->v, w'(u,v)=w(u,v)+d[u]-d[v]: 記得么d[u]+w(u,v)>=d[v], 所以 w'(u,v) >= 0
對新加的負權邊v->u, w'(v,u)=w(v,u)+d[v]-d[u]=-w(u,v)+d[v]-d[u]: 記得么d[u]+w(u,v)==d[v]，這里可是取等號的，所以w'(v,u) == 0
哈哈，這下所有邊又是非負的了。
可是，問題是，為啥不每個邊加個足夠大的正數，這樣不是所有邊也都是正的了么。仔細想想，邊權為啥要為正，不就是為了求源點到匯點的最短路方便么，可是，都加大正數的話，你求出的最短路和原來圖的最短路能一致么，不能，為啥，畫個三角形，自己想想?？墒牵业姆椒ň湍芤恢旅矗?。我證明給你看。
假設從源點s到匯點t有一條路徑s->a->b->c->d
.->t,在原圖中的路徑長度為
w(s,a)+w(a,b)+w(b,c)++w(x,t)
在新圖中的路徑為
w'(s,a)+w'(a,b)+w'(b,c)+w'(x,t)
展開來就是
w(s,a)+d[a]-d[s]+w(a,b)+d[b]-d[a]+w(c,d)+d[d]-d[b]+.+w(x,t)+d[t]-d[x]
消阿消，d[a]和-d[a]，d[b]和-d[b]d[x]和-d[x]，剩下什么呢：
w(s,a)+w(a,b)+w(b,c)++w(x,t)+d[t]-d[s]
噢，不就比原圖中多d[t]-d[s]么（其實d[s]==0）。這可是對所有s到t的路徑都成立的，既然所有路徑，在新圖中的權值都比在原圖中的權值多了d[t]，那么，新圖的最短路，也就對應原圖的最短路，只不過路徑長度多了d[t]，這不僅對t成立，對所有節點u都成立，只不過新圖中到u的最短路長度比原圖多了d[u]。
好，用dijkstra算法，第二次求出最短路。然后求出新的d’[u]，然后添加新的邊，然后準備第三次的dijkstra算法。。。為什么第二次可以這樣做，第三次還可以這樣做，第三次的原圖可能有很多負權邊??？我可沒說過w(u,v)>=0這樣的限制，所以，即使原圖有負權邊還是可以這樣做的。
好了，第一次dijkstra算法（或者bellman-ford算法，如果有負權邊的話，只用一次，不會成為瓶頸的），然后每次求最小增廣路用一次修改的dijkstra算法。這個算法求最小費用最大流復雜度是O(m*n*n), m是最大流量，或者是求增廣路次數的上界。最后，如果用這個算法來求最優匹配問題，復雜度是O(n^3)的。
posted on 2008-08-03 20:49
小果子 閱讀(5150)
評論(9) 編輯 收藏 引用