基于最短增廣鏈的最大流改進(jìn)算法

趙禮峰，紀(jì)亞勁

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

基于最短增廣鏈的最大流改進(jìn)算法

趙禮峰，紀(jì)亞勁

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

網(wǎng)絡(luò)最大流是經(jīng)典的組合優(yōu)化問題，它的經(jīng)典算法主要有三種，分別是Ford-Fulkerson算法、最短增廣鏈算法(Dinic算法)和預(yù)流推進(jìn)算法。Ford-Fulkerson算法中由于增廣鏈的選取任意性而有時無法得到理想的最大流。最短增廣鏈算法在分層剩余網(wǎng)絡(luò)中尋找最短增廣鏈，從而避免了增廣鏈選取的任意性。但最短增廣鏈算法在求解最大流過程中每次增廣都需要重新尋找最短增廣鏈，利用率不高。針對這一問題，提出了一種修復(fù)最短增廣鏈的新算法。該算法在沿最短增廣鏈調(diào)整流量之后，刪除最短增廣鏈流量為零的弧，且尋找合適的路徑修復(fù)最短增廣鏈，從而提高了最短增廣鏈的使用效率，減少了最短增廣鏈的搜索次數(shù)。應(yīng)用新算法進(jìn)行了BA無標(biāo)度網(wǎng)絡(luò)建模仿真。實(shí)驗(yàn)結(jié)果表明，該算法運(yùn)行效率要高于最短增廣鏈算法。

最大流；分層剩余網(wǎng)絡(luò)；最短增廣鏈；BA無標(biāo)度網(wǎng)絡(luò)

0 引 言

網(wǎng)絡(luò)最大流問題是圖論中極其重要的分支，是經(jīng)典的組合優(yōu)化問題，也可以看成特殊的線性規(guī)劃問題[1]。它在運(yùn)籌學(xué)、計算機(jī)、工程等眾多科學(xué)領(lǐng)域中有著廣泛的應(yīng)用[2-3]，例如，運(yùn)輸問題、分派問題、通信問題等都可以轉(zhuǎn)化為網(wǎng)絡(luò)最大流模型來解決。因此，研究網(wǎng)絡(luò)最大流算法具有很重要的意義。

至今為止，網(wǎng)絡(luò)最大流問題的研究已經(jīng)有50多年的歷史，現(xiàn)已建立了較為完善的理論并且提出了一系列經(jīng)典算法。……