基于有權(quán)圖的網(wǎng)絡(luò)最大流標(biāo)號(hào)算法的研究與實(shí)現(xiàn)

周青 楊劍蘭

（昆明醫(yī)科大學(xué)海源學(xué)院 云南省昆明市 650001）

計(jì)算機(jī)學(xué)科是一門應(yīng)用性和實(shí)用性很強(qiáng)的學(xué)科。為了更好地實(shí)踐“計(jì)算思維”的模式，利用計(jì)算機(jī)學(xué)科的基本概念、理論來求解、系統(tǒng)設(shè)計(jì)解決實(shí)際問題。也為了更好地踐行“二十大關(guān)于新工科建設(shè)學(xué)科融合”的問題，本文將針對(duì)求解網(wǎng)絡(luò)最大流問題的經(jīng)典算法標(biāo)號(hào)法，在算法思想和原理的基礎(chǔ)上，結(jié)合計(jì)算機(jī)語(yǔ)言程序設(shè)計(jì)的一般步驟，給出了程序設(shè)計(jì)的具體流程和部分代碼。這一過程，將在程序設(shè)計(jì)的基本概念和理論，落到實(shí)地，真正解決實(shí)際問題。

1 有權(quán)圖的介紹

有權(quán)圖是圖論里一個(gè)重要概念，即圖的每條邊都有一個(gè)表示一定實(shí)際含義的權(quán)數(shù)，稱為賦權(quán)圖或者有權(quán)圖。記作D=(V,A,C)。在具有實(shí)際意義的網(wǎng)絡(luò)中，邊上的權(quán)值可能表示的是路程，也可能表示的是運(yùn)輸費(fèi)用。

而網(wǎng)絡(luò)最大流的問題正是基于有向圖的，且與一般的有向圖有所不同，任何一個(gè)流都從某個(gè)點(diǎn)單向流入另一個(gè)點(diǎn)，并且追根溯源地來自同一個(gè)始點(diǎn)，又去往同一個(gè)終點(diǎn)。所有流源頭的那個(gè)點(diǎn)被稱為發(fā)點(diǎn)，記作Vs，而流向的那個(gè)終點(diǎn)被稱為收點(diǎn)，記作Vt，其余各點(diǎn)稱為中間點(diǎn)。對(duì)于網(wǎng)絡(luò)中的每一條弧，都存在一個(gè)容量，這規(guī)定了單條弧中的最大流量。而實(shí)際上流過這條弧的流量，不一定會(huì)達(dá)到容量。因此，在網(wǎng)絡(luò)最大流問題中，有向圖的權(quán)值一般用容量和流量來標(biāo)識(shí)。

2 網(wǎng)絡(luò)最大流標(biāo)號(hào)算法

2.1 網(wǎng)絡(luò)最大流的概念和模型

最大流問題，是網(wǎng)絡(luò)流理論研究的一個(gè)基本問題：在有若干節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)中，求一個(gè)可行流f，使其流量v(f)在不超過容量上限的前提下，達(dá)到最大值，這樣的可行流f 稱為最大流。網(wǎng)絡(luò)最大流的問題，屬于有特殊限制的線性規(guī)劃問題，可以建立如下數(shù)學(xué)模型：

在該數(shù)學(xué)模型中，其中cij為弧(vi,vj)上的容量，fij為弧(vi,vj)上的流量。i 表示任一中間結(jié)點(diǎn)，s 表示開始結(jié)點(diǎn)，t 表示終止結(jié)點(diǎn)。

2.2 標(biāo)號(hào)算法的介紹

求解網(wǎng)絡(luò)最大流的問題，可以劃歸為最優(yōu)化問題：如何調(diào)整網(wǎng)絡(luò)節(jié)點(diǎn)的實(shí)際流量，實(shí)現(xiàn)在流量守恒和容量約束的前提下流量最大？求解此類問題有很多方法，其中最為著名算法是由Ford 和Fulkerson 提出的標(biāo)號(hào)法。

標(biāo)號(hào)算法的流程圖：根據(jù)標(biāo)號(hào)算法的迭代過程，畫出該算法的流程圖如圖1。

圖1：標(biāo)號(hào)算法流程圖

該算法的核心思想是，對(duì)于網(wǎng)絡(luò)上的任何一條由起點(diǎn)到終點(diǎn)的可行流，如果存在一條增廣鏈，那么說明該網(wǎng)絡(luò)上的流量還沒有達(dá)到最大，可以繼續(xù)增加流量。直到找不到增廣鏈為止，最終的網(wǎng)絡(luò)流量即為最大流。具體分為兩個(gè)步驟：

（1）標(biāo)號(hào)過程（通過為頂點(diǎn)標(biāo)號(hào)，尋找可能存在的增廣鏈）。

標(biāo)號(hào)信息包括兩部分：前置節(jié)點(diǎn)和該弧尚可增加的流量值。以節(jié)點(diǎn)j 為例，若前置節(jié)點(diǎn)為i，標(biāo)號(hào)信息可表示為[vi,θj]。其中θj為調(diào)整量，vi 為前一節(jié)點(diǎn)，θj為該弧尚可增加的流量值。

可標(biāo)號(hào)原則為：正向弧非飽和，即容量Cij>流量fij，反向弧為非零流弧，即流量fij>0，滿足其一方可標(biāo)號(hào)。

具體標(biāo)號(hào)步驟如下：

a．自起始頂點(diǎn)s 開始標(biāo)號(hào)：[VS,∞]

b．選擇與頂點(diǎn)關(guān)聯(lián)的各類弧：

c．把頂點(diǎn)集分為兩部分：已標(biāo)號(hào)點(diǎn)集和未標(biāo)號(hào)點(diǎn)集。此時(shí)的已標(biāo)號(hào)點(diǎn)集可以看作是納入了已標(biāo)號(hào)頂點(diǎn)的新的更大的“開始節(jié)點(diǎn)”。

d．繼續(xù)重復(fù)b 和c 步驟，直到標(biāo)到終止節(jié)點(diǎn)t 為止。此時(shí)出現(xiàn)兩種可能的結(jié)果：

（2）調(diào)整過程（調(diào)整增廣鏈上的流量）。

調(diào)整的流量值取θ=min{θj}

調(diào)整完繼續(xù)重復(fù)前面的標(biāo)號(hào)過程，直到?jīng)]有增廣鏈出現(xiàn)為止，結(jié)束算法，當(dāng)前網(wǎng)絡(luò)流量即為最大流。

3 JAVA程序設(shè)計(jì)流程

3.1 算法數(shù)據(jù)結(jié)構(gòu)選擇

為了更好地將有權(quán)圖在計(jì)算機(jī)中存儲(chǔ)，該算法中引入二維數(shù)組（鄰接矩陣）的數(shù)據(jù)結(jié)構(gòu)。

鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，在有向圖中，常用鄰接矩陣來表示。其數(shù)據(jù)結(jié)構(gòu)常表示為二維數(shù)組的形式：

鄰接矩陣的引入，更加直觀、簡(jiǎn)單，同時(shí)，在做標(biāo)號(hào)算法的迭代時(shí)，便于找尋任一頂點(diǎn)的所有“鄰接點(diǎn)”（有邊直接相連的頂點(diǎn)），提高了程序執(zhí)行效率。

有如下網(wǎng)絡(luò)流問題實(shí)例：“如何安排fij，可使網(wǎng)絡(luò)D 上的總流量v 最大？”

以圖2 為例，有權(quán)圖采用鄰接矩陣具體表示如圖3、圖4。

圖2：網(wǎng)絡(luò)流問題實(shí)例

圖3：基于網(wǎng)絡(luò)容量的矩陣表示

圖4：基于網(wǎng)絡(luò)流量的矩陣表示

注意：在實(shí)際的計(jì)算機(jī)存儲(chǔ)中，為了便于計(jì)算，將∞替換為0。

3.2 算法的代碼實(shí)現(xiàn)

本文根據(jù)算法的思想和原理，進(jìn)而將算法轉(zhuǎn)換為代碼，采用Java 語(yǔ)言編輯算法過程，其中運(yùn)用到的主要數(shù)據(jù)結(jié)構(gòu)為二維數(shù)組，以存儲(chǔ)示例鄰接矩陣，部分代碼如下：

尋找增廣鏈，調(diào)整增廣鏈上的流量是該算法的核心，在實(shí)際編程中，采用鍵-值對(duì)（key-value）集合Map 存儲(chǔ)增廣路徑的編號(hào)，通過編號(hào)查找增廣路徑，利用不會(huì)存儲(chǔ)重復(fù)的元素Set 集合存儲(chǔ)當(dāng)前的增廣路徑編號(hào)的組合順序，使用for 循環(huán)結(jié)構(gòu)以迭代思想求解示例網(wǎng)絡(luò)流圖的最大流流量，核心代碼片段如下：

3.3 代碼的可行性驗(yàn)證與評(píng)價(jià)

為了驗(yàn)證程序代碼的可行性，本文依然以上文中出現(xiàn)的網(wǎng)絡(luò)流實(shí)例問題（圖2）為具體例子，按具體步驟進(jìn)行標(biāo)號(hào)，將程序運(yùn)行結(jié)果與手動(dòng)標(biāo)號(hào)結(jié)果進(jìn)行對(duì)照。

（1）具體標(biāo)號(hào)過程。

從頂點(diǎn)Vs 開始首次標(biāo)號(hào)，然后，觀察與Vs 關(guān)聯(lián)的所有弧，發(fā)現(xiàn)只有流出弧，在流出的未飽和弧中，有V1 和V2 兩個(gè)頂點(diǎn)符合標(biāo)號(hào)規(guī)則，選擇其一如V1 進(jìn)行標(biāo)號(hào)，前一節(jié)點(diǎn)為Vs，調(diào)整量為1；此時(shí)，將頂點(diǎn)集劃分為已標(biāo)號(hào)和未標(biāo)號(hào)兩部分，觀察所有從已標(biāo)號(hào)頂點(diǎn)流入未標(biāo)號(hào)頂點(diǎn)的弧，再次判斷是否符合標(biāo)號(hào)規(guī)則，重復(fù)操作，直到標(biāo)號(hào)頂點(diǎn)到達(dá)終點(diǎn)Vt 節(jié)點(diǎn)位置。

經(jīng)過第一輪標(biāo)號(hào)，已標(biāo)號(hào)頂點(diǎn)為Vs,V1,V5,V4,Vt具體標(biāo)號(hào)信息如圖5所示。

圖5

逆向搜索，找到一條增廣鏈。如圖6所示。

圖6

調(diào)整增廣鏈，調(diào)整量為增廣鏈上弧流量的最小值，調(diào)整后結(jié)果如圖7。

圖7

標(biāo)號(hào)算法二次迭代，自頂點(diǎn)Vs 開始，重復(fù)第一次的標(biāo)號(hào)過程，可標(biāo)號(hào)頂點(diǎn)為Vs 和V2，標(biāo)號(hào)過程無法繼續(xù)進(jìn)行，算法終止。當(dāng)前該網(wǎng)絡(luò)實(shí)際流量為最大流量，即4+3+7=14。紅色圓圈表示的部分即為最小截的頂點(diǎn)集。如圖8所示。

圖8

（2）完整JAVA 程序在IDEA 中的運(yùn)行結(jié)果截圖如圖9。

圖9

將算法步驟的具體迭代和程序代碼的運(yùn)行結(jié)果二者對(duì)照，結(jié)果一致，最大流均為14.說明將算法轉(zhuǎn)化后的Java 程序代碼是可行的。在解決節(jié)點(diǎn)數(shù)更多的有權(quán)圖時(shí)，程序代碼的執(zhí)行效率具有明顯的優(yōu)勢(shì)。

4 總結(jié)

本文首先介紹了網(wǎng)絡(luò)最大流問題的數(shù)學(xué)模型，然后結(jié)合現(xiàn)有的優(yōu)秀的算法對(duì)算法原理進(jìn)行了流程圖轉(zhuǎn)換。并以此為基礎(chǔ)，依照程序設(shè)計(jì)的流程，將該經(jīng)典算法轉(zhuǎn)化為具體的程序代碼，文中展示了部分核心代碼。最后，為了更好地驗(yàn)證JAVA 程序的可行性，利用網(wǎng)絡(luò)最大流問題進(jìn)行了實(shí)例比對(duì)，通過比較，發(fā)現(xiàn)程序的運(yùn)行結(jié)果和算法步驟求解出的結(jié)果保持一致。說明該過程是可行的，該程序在解決此類問題中可以較高效地求解出最優(yōu)化的路徑和最大流量。