如何使用連續(xù)最短增廣鏈的解決網(wǎng)絡(luò)最大流分析

　　本文主要是分析連續(xù)最短增廣鏈算法計(jì)算網(wǎng)絡(luò)最大流的問(wèn)題。先綜述殘留網(wǎng)絡(luò)和層次網(wǎng)絡(luò)的基本概念，然后分析連續(xù)最短增廣鏈算法計(jì)算網(wǎng)絡(luò)最大流的具體過(guò)程，再通過(guò)與Ford-Fulkerson （福特-富爾克森算法）和Edmonds-Karp （埃德蒙茲-卡普算法）算法進(jìn)行比較來(lái)體現(xiàn)出連續(xù)最短增廣鏈算法的突出點(diǎn)。通過(guò)相關(guān)性的比較，結(jié)論是連續(xù)最短增廣鏈算法運(yùn)行效果明顯比Ford-Fulkerson好，且優(yōu)于Edmonds-Karp。

　　網(wǎng)絡(luò)流中最大流問(wèn)題是一個(gè)經(jīng)典的問(wèn)題，在最初的Ford-Fulkerson 算法提出到現(xiàn)在已有60 多年的歷史了，一直是個(gè)值得研究的問(wèn)題。在此過(guò)程中，也提出了許多與之相關(guān)的算法。相比于初期的算法，現(xiàn)在對(duì)于網(wǎng)絡(luò)最大流的算法得到了很大的改進(jìn)，算法時(shí)間和空間復(fù)雜度都有所下降。常用的算法為Ford-Fulkerson 算法、Edmonds-Karp 算法和Dinic 算法等。

　　Ford-Fulkerson 算法是利用深度優(yōu)先搜索的思想來(lái)尋找增廣鏈，而這樣尋找會(huì)使得復(fù)雜度依賴于最大傳輸量。Edmonds-Karp 算法則在Ford-Fulkerson 算法的基礎(chǔ)上進(jìn)行了修改，使得每次按最短路徑尋找增廣鏈，但每次找完一個(gè)最短增廣鏈后需要重新尋找，利用率不高。而Dinic 算法則是效率更高，使用更頻繁。

　　為此，本文對(duì)連續(xù)最短增廣鏈算法在網(wǎng)絡(luò)最大流問(wèn)題上做一個(gè)詳細(xì)的分析。該算法雖然也是按最短路徑來(lái)尋找增廣鏈的，不過(guò)增加了一個(gè)層次網(wǎng)絡(luò)。相比于每次重新尋找最短增廣鏈來(lái)說(shuō)，利用層次網(wǎng)絡(luò)將避免了重新尋找最短的增廣鏈所帶來(lái)的多余的步驟。

?