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