最小費(fèi)用最大流問(wèn)題的SPFA算法實(shí)踐一、SPFA算法概述

SPFA（ShortestPathFasterAlgorithm）算法是基于Bellman-Ford算法的改進(jìn)版本，用于解決最小費(fèi)用最大流問(wèn)題。其核心思想是通過(guò)隊(duì)列優(yōu)化松弛操作，提高算法效率，特別適用于稀疏圖。SPFA算法在最小費(fèi)用最大流問(wèn)題中具有以下特點(diǎn)：

（一）算法原理

1.基本概念

-費(fèi)用網(wǎng)絡(luò)：包含容量和單位流費(fèi)用兩個(gè)屬性的網(wǎng)絡(luò)。

-可行流：滿足容量約束和流量守恒的流。

-最小費(fèi)用最大流：在所有可行流中，總費(fèi)用最小的最大流。

2.核心步驟

-構(gòu)建費(fèi)用網(wǎng)絡(luò)，確定源點(diǎn)、匯點(diǎn)及各邊屬性。

-通過(guò)多次迭代，不斷尋找最短費(fèi)用路徑，增加流量。

-更新路徑費(fèi)用，直至無(wú)法繼續(xù)增加流量為止。

（二）算法優(yōu)勢(shì)

1.效率提升：通過(guò)隊(duì)列緩存已松弛的節(jié)點(diǎn)，減少重復(fù)計(jì)算。

2.適用性廣：適用于大規(guī)模稀疏圖，收斂速度優(yōu)于Bellman-Ford。

3.穩(wěn)定性高：在負(fù)權(quán)邊存在時(shí)仍能正確運(yùn)行（需結(jié)合可行性判斷）。

二、SPFA算法實(shí)現(xiàn)步驟

SPFA算法的實(shí)現(xiàn)分為初始化、松弛操作和結(jié)果輸出三個(gè)階段，具體流程如下：

（一）初始化

1.設(shè)置初始流量與費(fèi)用

-源點(diǎn)流量設(shè)為0，匯點(diǎn)流量為目標(biāo)流量（如需最大流）。

-各邊初始費(fèi)用為網(wǎng)絡(luò)給定值，容量為邊上限。

2.構(gòu)建隊(duì)列與標(biāo)記

-創(chuàng)建空隊(duì)列用于緩存待松弛節(jié)點(diǎn)。

-使用標(biāo)記數(shù)組記錄節(jié)點(diǎn)是否被更新，避免重復(fù)處理。

（二）松弛操作

1.隊(duì)列處理流程

-(1)出隊(duì)節(jié)點(diǎn)，檢查相鄰邊是否可松弛。

-(2)若相鄰邊滿足容量和費(fèi)用條件，更新其費(fèi)用和流量。

-(3)若相鄰邊費(fèi)用降低，將其重新入隊(duì)。

2.費(fèi)用更新規(guī)則

-每次松弛操作需計(jì)算新的費(fèi)用值：

\[\text{新費(fèi)用}=\text{當(dāng)前費(fèi)用}+\text{邊費(fèi)用}\]

-若新費(fèi)用低于記錄值，則更新并標(biāo)記為待處理。

（三）終止條件

1.最大流判斷

-隊(duì)列為空且無(wú)可松弛邊時(shí)，當(dāng)前流量為最大流。

-若檢測(cè)到負(fù)權(quán)環(huán)（費(fèi)用持續(xù)降低），需調(diào)整網(wǎng)絡(luò)參數(shù)（如增加ε懲罰）。

2.結(jié)果輸出

-輸出總流量、最小費(fèi)用及各邊流量分布。

三、算法實(shí)踐示例

（一）網(wǎng)絡(luò)構(gòu)建

1.節(jié)點(diǎn)與邊

-源點(diǎn)S，匯點(diǎn)T，中間節(jié)點(diǎn)A、B。

-邊：S-A（容量5，費(fèi)用4），A-B（容量3，費(fèi)用2），B-T（容量2，費(fèi)用1）。

2.目標(biāo)

-最大流量為4，最小費(fèi)用需計(jì)算。

（二）迭代過(guò)程

1.初始狀態(tài)

-S流量0，T流量4，邊流量均0。

2.第一次迭代

-(1)隊(duì)列入S，松弛S-A：費(fèi)用4，流量1。

-(2)松弛A-B：費(fèi)用6，流量1。

-(3)松弛B-T：費(fèi)用7，流量1。

3.第二次迭代

-(1)隊(duì)列入A，松弛A-S（反向邊）：費(fèi)用-4，無(wú)效。

-(2)松弛A-B：無(wú)更新。

-(3)終止條件觸發(fā)，總費(fèi)用7。

（三）結(jié)果分析

-最大流量4，最小費(fèi)用7，流量分布：S-A=1，A-B=1，B-T=2。

四、注意事項(xiàng)

1.負(fù)權(quán)邊處理

-若存在負(fù)權(quán)環(huán)，需檢測(cè)算法是否發(fā)散（通過(guò)計(jì)數(shù)器限制迭代次數(shù)）。

2.性能優(yōu)化

-使用鏈?zhǔn)角跋蛐谴鎯?chǔ)鄰接表，減少查找時(shí)間。

-隊(duì)列改為雙端隊(duì)列可提升入隊(duì)效率。

3.實(shí)際應(yīng)用

-適用于物流調(diào)度、資源分配等費(fèi)用優(yōu)化場(chǎng)景。

-結(jié)合堆優(yōu)化（如Dijkstra變體）可進(jìn)一步提升效率。

一、SPFA算法概述

SPFA（ShortestPathFasterAlgorithm）算法是基于Bellman-Ford算法的改進(jìn)版本，用于解決最小費(fèi)用最大流問(wèn)題。其核心思想是通過(guò)隊(duì)列優(yōu)化松弛操作，提高算法效率，特別適用于稀疏圖。SPFA算法在最小費(fèi)用最大流問(wèn)題中具有以下特點(diǎn)：

（一）算法原理

1.基本概念

-費(fèi)用網(wǎng)絡(luò)：包含容量（Capacity）和單位流費(fèi)用（UnitCost）兩個(gè)屬性的網(wǎng)絡(luò)。容量表示邊上允許通過(guò)的最大流量，單位流費(fèi)用表示每單位流量通過(guò)該邊所需的成本。

-可行流：滿足容量約束（即每條邊的流量不超過(guò)其容量）和流量守恒（即除源點(diǎn)S和匯點(diǎn)T外，任意中間節(jié)點(diǎn)的凈流量為0）的流。

-最小費(fèi)用最大流：在所有可行流中，總費(fèi)用最小的最大流?？傎M(fèi)用是網(wǎng)絡(luò)中所有邊上的流量與其單位流費(fèi)用乘積的總和。

2.核心步驟

-構(gòu)建費(fèi)用網(wǎng)絡(luò)，明確源點(diǎn)、匯點(diǎn)以及各邊屬性（容量和單位流費(fèi)用）。

-初始化流量為0，費(fèi)用為0。

-通過(guò)迭代尋找從源點(diǎn)S到匯點(diǎn)T的最短費(fèi)用路徑，沿著該路徑增加流量。

-在每次迭代中，使用松弛操作更新路徑費(fèi)用和流量。松弛操作檢查是否存在通過(guò)當(dāng)前路徑可以以更低費(fèi)用到達(dá)某節(jié)點(diǎn)的路徑，如果存在，則更新該節(jié)點(diǎn)的最短路徑估計(jì)和前驅(qū)節(jié)點(diǎn)。

-當(dāng)無(wú)法找到從源點(diǎn)到匯點(diǎn)的增廣路徑時(shí)，算法終止，此時(shí)的流量即為最大流，累計(jì)費(fèi)用為最小費(fèi)用。

（二）算法優(yōu)勢(shì)

1.效率提升：通過(guò)隊(duì)列緩存已松弛的節(jié)點(diǎn)，減少重復(fù)計(jì)算。相比于原始的Bellman-Ford算法，SPFA在稀疏圖上具有更快的收斂速度，因?yàn)樗惶幚肀粚?shí)際松弛過(guò)的節(jié)點(diǎn)。

-具體來(lái)說(shuō)，當(dāng)節(jié)點(diǎn)i被加入隊(duì)列時(shí)，會(huì)檢查其所有出邊（i->j）。如果通過(guò)邊(i,j)松弛了節(jié)點(diǎn)j（即找到了一條從源點(diǎn)S到j(luò)的最短路徑，且路徑上的費(fèi)用總和比之前記錄的更小），則將節(jié)點(diǎn)j重新入隊(duì)。這樣，每個(gè)節(jié)點(diǎn)最多被加入隊(duì)列一次，大大減少了不必要的松弛操作。

2.適用性廣：適用于大規(guī)模稀疏圖，收斂速度優(yōu)于Bellman-Ford。因?yàn)橄∈鑸D意味著大多數(shù)邊的流量為0或接近0，因此大部分邊的松弛操作都不會(huì)被觸發(fā)，隊(duì)列的使用可以避免對(duì)大量無(wú)關(guān)節(jié)點(diǎn)的重復(fù)處理。

3.穩(wěn)定性高：在負(fù)權(quán)邊存在時(shí)仍能正確運(yùn)行（需結(jié)合可行性判斷）。雖然最小費(fèi)用最大流問(wèn)題通常假設(shè)單位流費(fèi)用為非負(fù)，但在某些實(shí)際應(yīng)用中可能存在負(fù)費(fèi)用邊。SPFA算法能夠正確處理這種情況，前提是網(wǎng)絡(luò)中不存在負(fù)權(quán)環(huán)導(dǎo)致費(fèi)用無(wú)限降低。

二、SPFA算法實(shí)現(xiàn)步驟

SPFA算法的實(shí)現(xiàn)分為初始化、松弛操作和結(jié)果輸出三個(gè)階段，具體流程如下：

（一）初始化

1.設(shè)置初始流量與費(fèi)用

-將源點(diǎn)S的流量初始化為0，匯點(diǎn)T的流量也初始化為0（流量將在后續(xù)迭代中累加）。

-將匯點(diǎn)T的流量設(shè)為目標(biāo)流量（如果問(wèn)題要求求最大流，則目標(biāo)流量通常是一個(gè)預(yù)設(shè)值或所有出邊容量的總和；如果問(wèn)題要求求特定流量，則目標(biāo)流量就是該特定值）。但在SPFA的標(biāo)準(zhǔn)實(shí)現(xiàn)中，我們通常是在每次迭代中增加流量，直到無(wú)法再增廣為止，此時(shí)得到的流量即為最大流。

-初始化各邊的流量為0。

-設(shè)置各邊的初始單位流費(fèi)用，通常存儲(chǔ)在一個(gè)二維數(shù)組或鄰接表中，例如`cost[u][v]`表示從節(jié)點(diǎn)u到節(jié)點(diǎn)v的邊的單位流費(fèi)用。

2.構(gòu)建隊(duì)列與標(biāo)記

-創(chuàng)建一個(gè)空隊(duì)列`queue`，用于緩存待處理（即可能被松弛）的節(jié)點(diǎn)。

-創(chuàng)建一個(gè)標(biāo)記數(shù)組`inqueue`，大小與節(jié)點(diǎn)總數(shù)相同，用于記錄節(jié)點(diǎn)是否當(dāng)前在隊(duì)列中。`inqueue[i]=false`表示節(jié)點(diǎn)i不在隊(duì)列中，`inqueue[i]=true`表示節(jié)點(diǎn)i在隊(duì)列中。這有助于避免重復(fù)將同一個(gè)節(jié)點(diǎn)加入隊(duì)列，從而提高效率。

（二）松弛操作

1.隊(duì)列處理流程

-(1)入隊(duì)源點(diǎn)：將源點(diǎn)S加入隊(duì)列`queue`，并設(shè)置`inqueue[S]=true`。

-(2)出隊(duì)并處理：當(dāng)隊(duì)列`queue`非空時(shí)，執(zhí)行以下操作：

-出隊(duì)一個(gè)節(jié)點(diǎn)`u`，即`u=queue.front();queue.pop();`，并設(shè)置`inqueue[u]=false`。

-對(duì)于節(jié)點(diǎn)`u`的每一個(gè)出邊`(u,v)`：

-檢查是否可以沿著邊`(u,v)`松弛節(jié)點(diǎn)`v`。松弛的條件通常是：

-`u`的流量`flow[u]`大于0（即邊`(u,v)`有剩余容量）。

-通過(guò)邊`(u,v)`到達(dá)`v`的當(dāng)前路徑費(fèi)用`dist[v]`大于通過(guò)邊`(u,v)`到達(dá)`v`的路徑費(fèi)用加上邊`(u,v)`的單位流費(fèi)用`cost[u][v]`。即`dist[v]>dist[u]+cost[u][v]`。

-如果滿足上述松弛條件，則進(jìn)行松弛操作：

-更新`v`的最短路徑估計(jì)：`dist[v]=dist[u]+cost[u][v]`。

-更新`v`的前驅(qū)節(jié)點(diǎn)：`pre[v]=u`。

-增加通過(guò)邊`(u,v)`的流量：`flow[u]-=1`，`flow[v]+=1`。

-如果`inqueue[v]`為`false`（即節(jié)點(diǎn)`v`當(dāng)前不在隊(duì)列中），則將節(jié)點(diǎn)`v`加入隊(duì)列`queue`，并設(shè)置`inqueue[v]=true`。

-(3)循環(huán)檢查：重復(fù)步驟(2)直到隊(duì)列為空。

2.費(fèi)用更新規(guī)則

-每次松弛操作的核心是更新目標(biāo)節(jié)點(diǎn)的最短路徑估計(jì)和前驅(qū)節(jié)點(diǎn)。具體來(lái)說(shuō)：

-計(jì)算通過(guò)邊`(u,v)`到達(dá)`v`的新路徑費(fèi)用：`new_dist[v]=dist[u]+cost[u][v]`。

-如果`new_dist[v]<dist[v]`，則說(shuō)明找到了一條更短的路徑到達(dá)`v`，因此更新`dist[v]=new_dist[v]`，并記錄這條路徑的新前驅(qū)節(jié)點(diǎn)`pre[v]=u`。

-松弛操作完成后，通過(guò)前驅(qū)節(jié)點(diǎn)數(shù)組`pre`可以回溯出從源點(diǎn)S到匯點(diǎn)T的最短費(fèi)用路徑。這條路徑上的流量可以增加（具體增加多少取決于路徑上各邊的剩余容量）。

（三）結(jié)果輸出

1.最大流判斷

-當(dāng)隊(duì)列為空且無(wú)法再找到從源點(diǎn)S到匯點(diǎn)T的增廣路徑時(shí)，算法終止。此時(shí)，當(dāng)前網(wǎng)絡(luò)中的流即為最大流。

-可以通過(guò)計(jì)算源點(diǎn)S的總出流量或匯點(diǎn)T的總?cè)肓髁縼?lái)確定最大流的流量值。這兩個(gè)值應(yīng)該相等，且等于最大流的總流量。

-如果在算法執(zhí)行過(guò)程中發(fā)現(xiàn)`dist[T]`仍然為無(wú)窮大（或某個(gè)預(yù)設(shè)的極大值），說(shuō)明網(wǎng)絡(luò)中存在負(fù)權(quán)環(huán)（即負(fù)費(fèi)用循環(huán)），此時(shí)算法無(wú)法找到最小費(fèi)用最大流。但在最小費(fèi)用最大流的標(biāo)準(zhǔn)問(wèn)題設(shè)定中，通常假設(shè)網(wǎng)絡(luò)是無(wú)負(fù)權(quán)環(huán)的。

2.結(jié)果輸出

-輸出最大流量值。

-輸出最小費(fèi)用值。最小費(fèi)用可以通過(guò)將最大流路徑上的流量乘以其單位流費(fèi)用并求和得到。

-輸出各邊的最終流量分布?？梢酝ㄟ^(guò)前驅(qū)節(jié)點(diǎn)數(shù)組`pre`回溯出每條邊是否在最大流路徑上，并根據(jù)路徑上的流量分配確定每條邊的具體流量。

三、算法實(shí)踐示例

（一）網(wǎng)絡(luò)構(gòu)建

1.節(jié)點(diǎn)與邊

-節(jié)點(diǎn)集合：{S,A,B,T}。

-邊集合及屬性：

-(S,A)：容量`capacity[S][A]=5`，單位流費(fèi)用`cost[S][A]=4`。

-(S,B)：容量`capacity[S][B]=2`，單位流費(fèi)用`cost[S][B]=1`。

-(A,B)：容量`capacity[A][B]=3`，單位流費(fèi)用`cost[A][B]=2`。

-(A,T)：容量`capacity[A][T]=4`，單位流費(fèi)用`cost[A][T]=3`。

-(B,T)：容量`capacity[B][T]=2`，單位流費(fèi)用`cost[B][T]=5`。

-注意：在實(shí)際的費(fèi)用網(wǎng)絡(luò)表示中，通常需要存儲(chǔ)所有可能的邊（包括方向性），即使某些邊的容量為0。可以使用鄰接矩陣或鄰接表來(lái)存儲(chǔ)這些信息。

2.目標(biāo)

-求該網(wǎng)絡(luò)的最小費(fèi)用最大流。即找到一種流配置，使得從源點(diǎn)S到匯點(diǎn)T的總流量最大，同時(shí)滿足所有邊的容量約束和流量守恒，并且使得該流的總費(fèi)用（所有邊上的流量乘以其單位流費(fèi)用的總和）最小。

（二）迭代過(guò)程

1.初始狀態(tài)

-所有邊的流量`flow`初始化為0。

-源點(diǎn)S的流量為0，匯點(diǎn)T的流量為0（或目標(biāo)流量，如果指定）。

-最短路徑估計(jì)`dist`初始化：`dist[S]=0`，`dist[A]=∞`，`dist[B]=∞`，`dist[T]=∞`。

-前驅(qū)節(jié)點(diǎn)數(shù)組`pre`初始化：`pre[S]=-1`，`pre[A]=-1`，`pre[B]=-1`，`pre[T]=-1`。

-總費(fèi)用`total_cost`初始化為0。

2.第一次迭代

-(1)將源點(diǎn)S加入隊(duì)列`queue`，`inqueue[S]=true`。

-(2)隊(duì)列非空，出隊(duì)S。檢查S的出邊：

-邊(S,A)：松弛條件檢查：`flow[S]=0`（不滿足，不能松弛）。

-邊(S,B)：松弛條件檢查：`flow[S]=0`（不滿足，不能松弛）。

-(3)隊(duì)列為空，本次迭代結(jié)束，沒有進(jìn)行松弛操作。流量未增加。

3.第二次迭代

-(1)需要找到一條從S到T的增廣路徑。嘗試從S出發(fā)擴(kuò)展：

-從S出發(fā)，可以到達(dá)A和B。選擇一條路徑，例如S->A->T。

-檢查路徑S->A->T是否可行：

-邊(S,A)：剩余容量`capacity[S][A]-flow[S][A]=5-0=5`，滿足。

-邊(A,T)：剩余容量`capacity[A][T]-flow[A][T]=4-0=4`，滿足。

-計(jì)算路徑費(fèi)用：`cost[S][A]+cost[A][T]=4+3=7`。

-計(jì)算路徑上的最小剩余容量（即增廣流量的上限）：`min(5,4)=4`。

-(2)沿路徑S->A->T增廣流量4單位：

-更新流量：`flow[S][A]+=4`->4，`flow[A][T]+=4`->4。

-更新剩余容量：`capacity[S][A]-=4`->1，`capacity[A][T]-=4`->0。

-更新總費(fèi)用：`total_cost+=47=28`。

-(3)更新最短路徑估計(jì)和前驅(qū)節(jié)點(diǎn)（用于后續(xù)迭代）：

-對(duì)于路徑上的節(jié)點(diǎn)A和T：

-`dist[A]=min(dist[A],dist[S]+cost[S][A])=min(∞,0+4)=4`。

-`dist[T]=min(dist[T],dist[S]+cost[S][A]+cost[A][T])=min(∞,0+4+3)=7`。

-`pre[A]=S`，`pre[T]=A`。

-(4)將被更新的節(jié)點(diǎn)（或根據(jù)SPFA邏輯，將路徑終點(diǎn)T加入隊(duì)列）`queue`，`inqueue[T]=true`。

4.第三次迭代

-(1)隊(duì)列非空，出隊(duì)T。檢查T的出邊：

-邊(B,T)：松弛條件檢查：`flow[B]=0`，`flow[T]=4`，`dist[B]=∞`，`dist[T]=7`，`cost[B][T]=5`。`dist[B]>dist[T]+cost[B][T]`即`∞>7+5`成立?？梢运沙凇?/p>

-更新`dist[B]=12`，`pre[B]=T`。

-更新流量：`flow[B]+=4`->4，`flow[T]-=4`->0。

-更新剩余容量：`capacity[B][T]-=4`->-2（表示邊已滿，邏輯上不應(yīng)再松弛）。這里可能需要調(diào)整松弛邏輯或處理邊滿的情況。

-更新總費(fèi)用：`total_cost+=45=20`。

-將B加入隊(duì)列`queue`，`inqueue[B]=true`。

-(2)隊(duì)列非空，出隊(duì)B。檢查B的出邊：

-邊(B,T)：已經(jīng)處理過(guò)，流量為0，剩余容量為0，無(wú)法松弛。

-邊(B,A)：松弛條件檢查：`flow[B]=4`，`flow[A]=4`，`dist[A]=4`，`dist[B]=12`，`cost[B][A]`（假設(shè)存在，反向邊）需要定義。如果定義反向邊(B,A)的容量為0（即不允許反向流），則無(wú)法松弛。如果定義反向邊用于殘差網(wǎng)絡(luò)，則需要根據(jù)殘差網(wǎng)絡(luò)規(guī)則判斷。

-假設(shè)反向邊(B,A)容量為1，單位流費(fèi)用為-2（常見于殘差網(wǎng)絡(luò)表示最小費(fèi)用流問(wèn)題，但這里直接在原始網(wǎng)絡(luò)中反向松弛可能不直觀，且與最小費(fèi)用流的標(biāo)準(zhǔn)定義可能略有偏差）。如果反向松弛(B,A)：

-檢查：`flow[B]>0`，`dist[A]>dist[B]-cost[B][A]`即`4>12-(-2)`即`4>14`不成立，不能松弛。

-假設(shè)邊(B,A)不存在或容量為0，無(wú)法松弛。

-(3)隊(duì)列為空，本次迭代結(jié)束，沒有進(jìn)行新的有效松弛。

5.第四次迭代

-(1)嘗試找到新的增廣路徑。之前路徑S->A->T已用完。

-嘗試S->B->T路徑：

-邊(S,B)：剩余容量`2-0=2`。

-邊(B,T)：剩余容量`2-4=-2`（已滿，無(wú)法使用）。

-嘗試S->A->B->T路徑：

-邊(S,A)：剩余容量`1`。

-邊(A,B)：剩余容量`3-0=3`。

-邊(B,T)：剩余容量`2-4=-2`（已滿，無(wú)法使用）。

-嘗試S->B->A->T路徑：

-邊(S,B)：剩余容量`2`。

-邊(B,A)：假設(shè)存在，容量`3`（如果不存在或容量為0，則無(wú)法從B到A）。假設(shè)容量為3。

-邊(A,T)：剩余容量`0`（已用完，無(wú)法使用）。

-看起來(lái)直接從S到T的路徑已經(jīng)用完?？梢試L試從S到其他點(diǎn)，再擴(kuò)展：

-從S出發(fā)，可以到達(dá)A和B。A的路徑已阻塞（A->T邊已滿）。B的路徑也阻塞（B->T邊已滿）。

-算法無(wú)法找到新的增廣路徑。

（三）結(jié)果分析

-經(jīng)過(guò)上述迭代，最大流量為4（通過(guò)路徑S->A->T）。

-最小費(fèi)用為28（第一次迭代沿S->A->T增廣4單位，費(fèi)用28）。

-最終流量分布：

-邊(S,A)：流量4。

-邊(S,B)：流量0。

-邊(A,B)：流量0。

-邊(A,T)：流量4。

-邊(B,T)：流量0。

-注意：此示例迭代過(guò)程可能存在簡(jiǎn)化或邏輯上的不完全嚴(yán)謹(jǐn)之處，特別是關(guān)于反向邊和殘差網(wǎng)絡(luò)的處理。標(biāo)準(zhǔn)的SPFA實(shí)踐通常在殘差網(wǎng)絡(luò)上進(jìn)行松弛操作，每次迭代沿著增廣路徑增加流量，直到無(wú)法再增廣。上述示例嘗試在原始網(wǎng)絡(luò)中直接尋找路徑并增廣，可能不是最標(biāo)準(zhǔn)的SPFA應(yīng)用方式。更標(biāo)準(zhǔn)的做法是構(gòu)建殘差網(wǎng)絡(luò)，初始時(shí)正向邊和反向邊都存在（正向邊容量等于原始容量，費(fèi)用等于原始費(fèi)用；反向邊容量為0，費(fèi)用為負(fù)原始費(fèi)用），然后SPFA在殘差網(wǎng)絡(luò)上運(yùn)行，每次找到增廣路徑，更新原始網(wǎng)絡(luò)中的流量，并調(diào)整殘差網(wǎng)絡(luò)中的邊容量。如果按照標(biāo)準(zhǔn)方式，第一次迭代可能增廣的是路徑S->B->T（流量2），費(fèi)用2；然后增廣S->A->T（流量2），費(fèi)用6；總流量4，總費(fèi)用8。第二次迭代可能找不到增廣路徑。這表明同一網(wǎng)絡(luò)可能有不同解或迭代過(guò)程取決于路徑選擇。這里提供的示例是為了展示基本步驟，實(shí)際應(yīng)用需更精確地處理路徑選擇和殘差網(wǎng)絡(luò)。

四、注意事項(xiàng)

1.負(fù)權(quán)邊處理

-雖然最小費(fèi)用最大流問(wèn)題通常假設(shè)單位流費(fèi)用為非負(fù)，但在某些網(wǎng)絡(luò)建模中可能引入負(fù)費(fèi)用邊（例如，表示退回或懲罰）。SPFA算法能夠正確處理這種情況，前提是網(wǎng)絡(luò)中不存在負(fù)權(quán)環(huán)（即負(fù)費(fèi)用循環(huán)）。如果存在負(fù)權(quán)環(huán)，算法可能會(huì)陷入無(wú)限循環(huán)，無(wú)法找到最小費(fèi)用最大流。因此，在實(shí)際應(yīng)用中，需要確保費(fèi)用網(wǎng)絡(luò)是無(wú)負(fù)權(quán)環(huán)的?？梢酝ㄟ^(guò)在算法執(zhí)行結(jié)束后檢查`dist[T]`是否仍為無(wú)窮大（或某個(gè)預(yù)設(shè)的極大值）來(lái)間接判斷是否存在負(fù)權(quán)環(huán)。如果存在，則可能需要調(diào)整網(wǎng)絡(luò)模型或使用其他算法（如針對(duì)負(fù)權(quán)環(huán)的Bellman-Ford）。

-具體來(lái)說(shuō)，如果在SPFA算法執(zhí)行過(guò)程中，隊(duì)列非空但`dist[T]`仍然沒有收斂到某個(gè)有限值，或者`dist[T]`在多次迭代后仍然在變化（例如，通過(guò)某個(gè)負(fù)權(quán)環(huán)可以不斷降低費(fèi)用），則表明存在負(fù)權(quán)環(huán)。此時(shí)，最小費(fèi)用最大流可能不存在（如果允許無(wú)限流），或者算法需要修正。

2.性能優(yōu)化

-鄰接表存儲(chǔ)：使用鄰接表（鄰接鏈表）而不是鄰接矩陣來(lái)存儲(chǔ)網(wǎng)絡(luò)，可以顯著減少內(nèi)存占用，并提高邊的遍歷效率，尤其是在稀疏圖中。鄰接表通常是一個(gè)數(shù)組，每個(gè)元素是一個(gè)鏈表，鏈表中的節(jié)點(diǎn)表示與該頂點(diǎn)相連的邊。

-隊(duì)列優(yōu)化：使用雙端隊(duì)列（deque）而不是普通隊(duì)列來(lái)管理SPFA算法中的隊(duì)列。在SPFA中，當(dāng)節(jié)點(diǎn)被松弛時(shí)，它可能會(huì)被重新加入隊(duì)列。使用雙端隊(duì)列可以在隊(duì)首快速插入（對(duì)于某些實(shí)現(xiàn)可能更優(yōu)）或隊(duì)尾快速插入，這有助于提高算法的整體效率。

-標(biāo)記優(yōu)化：`inqueue`數(shù)組用于標(biāo)記節(jié)點(diǎn)是否在隊(duì)列中，以避免重復(fù)處理。確保`inqueue`數(shù)組訪問(wèn)和更新操作的高效性。

-EarlyTermination：在某些情況下，如果已經(jīng)找到一條增廣路徑，可以立即進(jìn)行增廣，而不是等待整個(gè)隊(duì)列處理完。但這需要更復(fù)雜的邏輯來(lái)確保不會(huì)遺漏更優(yōu)的路徑。

3.實(shí)際應(yīng)用

-物流配送：在物流網(wǎng)絡(luò)中，節(jié)點(diǎn)可以是倉(cāng)庫(kù)、配送中心、商店等，邊表示運(yùn)輸路徑，單位流費(fèi)用可以是運(yùn)輸成本（如油耗、時(shí)間）。SPFA算法可以用來(lái)規(guī)劃物流配送方案，使得在滿足需求的前提下，運(yùn)輸總成本最小。

-資源分配：在資源分配問(wèn)題中，節(jié)點(diǎn)可以表示資源需求方，邊表示資源供應(yīng)路徑，單位流費(fèi)用可以表示單位資源的獲取成本或分配成本。SPFA可以幫助找到資源分配方案，使得總成本最小。

-網(wǎng)絡(luò)流優(yōu)化：在通信網(wǎng)絡(luò)或水管網(wǎng)絡(luò)中，節(jié)點(diǎn)表示網(wǎng)絡(luò)節(jié)點(diǎn)或段，邊表示連接，單位流費(fèi)用可以表示傳輸延遲、帶寬成本等。SPFA可以用于優(yōu)化網(wǎng)絡(luò)流，最小化傳輸總成本。

-任務(wù)調(diào)度：在任務(wù)調(diào)度問(wèn)題中，節(jié)點(diǎn)可以表示任務(wù)或資源，邊表示任務(wù)依賴關(guān)系或資源分配，單位流費(fèi)用可以表示任務(wù)執(zhí)行成本或資源使用成本。SPFA可以用于找到任務(wù)執(zhí)行或資源分配方案，最小化總成本。

五、總結(jié)

SPFA算法是解決最小費(fèi)用最大流問(wèn)題的一種高效方法，特別是在稀疏圖中表現(xiàn)優(yōu)異。它基于Bellman-Ford算法，通過(guò)隊(duì)列優(yōu)化松弛操作，減少了不必要的計(jì)算，提高了收斂速度。正確理解和實(shí)現(xiàn)SPFA算法的關(guān)鍵在于掌握其初始化、松弛操作和迭代終止的規(guī)則，以及在處理負(fù)權(quán)邊和優(yōu)化數(shù)據(jù)結(jié)構(gòu)方面的技巧。通過(guò)本實(shí)踐指南的介紹和示例，可以更深入地理解SPFA算法的工作原理和應(yīng)用方法，為解決實(shí)際的最小費(fèi)用最大流問(wèn)題提供參考。

一、SPFA算法概述

SPFA（ShortestPathFasterAlgorithm）算法是基于Bellman-Ford算法的改進(jìn)版本，用于解決最小費(fèi)用最大流問(wèn)題。其核心思想是通過(guò)隊(duì)列優(yōu)化松弛操作，提高算法效率，特別適用于稀疏圖。SPFA算法在最小費(fèi)用最大流問(wèn)題中具有以下特點(diǎn)：

（一）算法原理

1.基本概念

-費(fèi)用網(wǎng)絡(luò)：包含容量和單位流費(fèi)用兩個(gè)屬性的網(wǎng)絡(luò)。

-可行流：滿足容量約束和流量守恒的流。

-最小費(fèi)用最大流：在所有可行流中，總費(fèi)用最小的最大流。

2.核心步驟

-構(gòu)建費(fèi)用網(wǎng)絡(luò)，確定源點(diǎn)、匯點(diǎn)及各邊屬性。

-通過(guò)多次迭代，不斷尋找最短費(fèi)用路徑，增加流量。

-更新路徑費(fèi)用，直至無(wú)法繼續(xù)增加流量為止。

（二）算法優(yōu)勢(shì)

1.效率提升：通過(guò)隊(duì)列緩存已松弛的節(jié)點(diǎn)，減少重復(fù)計(jì)算。

2.適用性廣：適用于大規(guī)模稀疏圖，收斂速度優(yōu)于Bellman-Ford。

3.穩(wěn)定性高：在負(fù)權(quán)邊存在時(shí)仍能正確運(yùn)行（需結(jié)合可行性判斷）。

二、SPFA算法實(shí)現(xiàn)步驟

SPFA算法的實(shí)現(xiàn)分為初始化、松弛操作和結(jié)果輸出三個(gè)階段，具體流程如下：

（一）初始化

1.設(shè)置初始流量與費(fèi)用

-源點(diǎn)流量設(shè)為0，匯點(diǎn)流量為目標(biāo)流量（如需最大流）。

-各邊初始費(fèi)用為網(wǎng)絡(luò)給定值，容量為邊上限。

2.構(gòu)建隊(duì)列與標(biāo)記

-創(chuàng)建空隊(duì)列用于緩存待松弛節(jié)點(diǎn)。

-使用標(biāo)記數(shù)組記錄節(jié)點(diǎn)是否被更新，避免重復(fù)處理。

（二）松弛操作

1.隊(duì)列處理流程

-(1)出隊(duì)節(jié)點(diǎn)，檢查相鄰邊是否可松弛。

-(2)若相鄰邊滿足容量和費(fèi)用條件，更新其費(fèi)用和流量。

-(3)若相鄰邊費(fèi)用降低，將其重新入隊(duì)。

2.費(fèi)用更新規(guī)則

-每次松弛操作需計(jì)算新的費(fèi)用值：

\[\text{新費(fèi)用}=\text{當(dāng)前費(fèi)用}+\text{邊費(fèi)用}\]

-若新費(fèi)用低于記錄值，則更新并標(biāo)記為待處理。

（三）終止條件

1.最大流判斷

-隊(duì)列為空且無(wú)可松弛邊時(shí)，當(dāng)前流量為最大流。

-若檢測(cè)到負(fù)權(quán)環(huán)（費(fèi)用持續(xù)降低），需調(diào)整網(wǎng)絡(luò)參數(shù)（如增加ε懲罰）。

2.結(jié)果輸出

-輸出總流量、最小費(fèi)用及各邊流量分布。

三、算法實(shí)踐示例

（一）網(wǎng)絡(luò)構(gòu)建

1.節(jié)點(diǎn)與邊

-源點(diǎn)S，匯點(diǎn)T，中間節(jié)點(diǎn)A、B。

-邊：S-A（容量5，費(fèi)用4），A-B（容量3，費(fèi)用2），B-T（容量2，費(fèi)用1）。

2.目標(biāo)

-最大流量為4，最小費(fèi)用需計(jì)算。

（二）迭代過(guò)程

1.初始狀態(tài)

-S流量0，T流量4，邊流量均0。

2.第一次迭代

-(1)隊(duì)列入S，松弛S-A：費(fèi)用4，流量1。

-(2)松弛A-B：費(fèi)用6，流量1。

-(3)松弛B-T：費(fèi)用7，流量1。

3.第二次迭代

-(1)隊(duì)列入A，松弛A-S（反向邊）：費(fèi)用-4，無(wú)效。

-(2)松弛A-B：無(wú)更新。

-(3)終止條件觸發(fā)，總費(fèi)用7。

（三）結(jié)果分析

-最大流量4，最小費(fèi)用7，流量分布：S-A=1，A-B=1，B-T=2。

四、注意事項(xiàng)

1.負(fù)權(quán)邊處理

-若存在負(fù)權(quán)環(huán)，需檢測(cè)算法是否發(fā)散（通過(guò)計(jì)數(shù)器限制迭代次數(shù)）。

2.性能優(yōu)化

-使用鏈?zhǔn)角跋蛐谴鎯?chǔ)鄰接表，減少查找時(shí)間。

-隊(duì)列改為雙端隊(duì)列可提升入隊(duì)效率。

3.實(shí)際應(yīng)用

-適用于物流調(diào)度、資源分配等費(fèi)用優(yōu)化場(chǎng)景。

-結(jié)合堆優(yōu)化（如Dijkstra變體）可進(jìn)一步提升效率。

一、SPFA算法概述

SPFA（ShortestPathFasterAlgorithm）算法是基于Bellman-Ford算法的改進(jìn)版本，用于解決最小費(fèi)用最大流問(wèn)題。其核心思想是通過(guò)隊(duì)列優(yōu)化松弛操作，提高算法效率，特別適用于稀疏圖。SPFA算法在最小費(fèi)用最大流問(wèn)題中具有以下特點(diǎn)：

（一）算法原理

1.基本概念

-費(fèi)用網(wǎng)絡(luò)：包含容量（Capacity）和單位流費(fèi)用（UnitCost）兩個(gè)屬性的網(wǎng)絡(luò)。容量表示邊上允許通過(guò)的最大流量，單位流費(fèi)用表示每單位流量通過(guò)該邊所需的成本。

-可行流：滿足容量約束（即每條邊的流量不超過(guò)其容量）和流量守恒（即除源點(diǎn)S和匯點(diǎn)T外，任意中間節(jié)點(diǎn)的凈流量為0）的流。

-最小費(fèi)用最大流：在所有可行流中，總費(fèi)用最小的最大流?？傎M(fèi)用是網(wǎng)絡(luò)中所有邊上的流量與其單位流費(fèi)用乘積的總和。

2.核心步驟

-構(gòu)建費(fèi)用網(wǎng)絡(luò)，明確源點(diǎn)、匯點(diǎn)以及各邊屬性（容量和單位流費(fèi)用）。

-初始化流量為0，費(fèi)用為0。

-通過(guò)迭代尋找從源點(diǎn)S到匯點(diǎn)T的最短費(fèi)用路徑，沿著該路徑增加流量。

-在每次迭代中，使用松弛操作更新路徑費(fèi)用和流量。松弛操作檢查是否存在通過(guò)當(dāng)前路徑可以以更低費(fèi)用到達(dá)某節(jié)點(diǎn)的路徑，如果存在，則更新該節(jié)點(diǎn)的最短路徑估計(jì)和前驅(qū)節(jié)點(diǎn)。

-當(dāng)無(wú)法找到從源點(diǎn)到匯點(diǎn)的增廣路徑時(shí)，算法終止，此時(shí)的流量即為最大流，累計(jì)費(fèi)用為最小費(fèi)用。

（二）算法優(yōu)勢(shì)

1.效率提升：通過(guò)隊(duì)列緩存已松弛的節(jié)點(diǎn)，減少重復(fù)計(jì)算。相比于原始的Bellman-Ford算法，SPFA在稀疏圖上具有更快的收斂速度，因?yàn)樗惶幚肀粚?shí)際松弛過(guò)的節(jié)點(diǎn)。

-具體來(lái)說(shuō)，當(dāng)節(jié)點(diǎn)i被加入隊(duì)列時(shí)，會(huì)檢查其所有出邊（i->j）。如果通過(guò)邊(i,j)松弛了節(jié)點(diǎn)j（即找到了一條從源點(diǎn)S到j(luò)的最短路徑，且路徑上的費(fèi)用總和比之前記錄的更?。?，則將節(jié)點(diǎn)j重新入隊(duì)。這樣，每個(gè)節(jié)點(diǎn)最多被加入隊(duì)列一次，大大減少了不必要的松弛操作。

2.適用性廣：適用于大規(guī)模稀疏圖，收斂速度優(yōu)于Bellman-Ford。因?yàn)橄∈鑸D意味著大多數(shù)邊的流量為0或接近0，因此大部分邊的松弛操作都不會(huì)被觸發(fā)，隊(duì)列的使用可以避免對(duì)大量無(wú)關(guān)節(jié)點(diǎn)的重復(fù)處理。

3.穩(wěn)定性高：在負(fù)權(quán)邊存在時(shí)仍能正確運(yùn)行（需結(jié)合可行性判斷）。雖然最小費(fèi)用最大流問(wèn)題通常假設(shè)單位流費(fèi)用為非負(fù)，但在某些實(shí)際應(yīng)用中可能存在負(fù)費(fèi)用邊。SPFA算法能夠正確處理這種情況，前提是網(wǎng)絡(luò)中不存在負(fù)權(quán)環(huán)導(dǎo)致費(fèi)用無(wú)限降低。

二、SPFA算法實(shí)現(xiàn)步驟

SPFA算法的實(shí)現(xiàn)分為初始化、松弛操作和結(jié)果輸出三個(gè)階段，具體流程如下：

（一）初始化

1.設(shè)置初始流量與費(fèi)用

-將源點(diǎn)S的流量初始化為0，匯點(diǎn)T的流量也初始化為0（流量將在后續(xù)迭代中累加）。

-將匯點(diǎn)T的流量設(shè)為目標(biāo)流量（如果問(wèn)題要求求最大流，則目標(biāo)流量通常是一個(gè)預(yù)設(shè)值或所有出邊容量的總和；如果問(wèn)題要求求特定流量，則目標(biāo)流量就是該特定值）。但在SPFA的標(biāo)準(zhǔn)實(shí)現(xiàn)中，我們通常是在每次迭代中增加流量，直到無(wú)法再增廣為止，此時(shí)得到的流量即為最大流。

-初始化各邊的流量為0。

-設(shè)置各邊的初始單位流費(fèi)用，通常存儲(chǔ)在一個(gè)二維數(shù)組或鄰接表中，例如`cost[u][v]`表示從節(jié)點(diǎn)u到節(jié)點(diǎn)v的邊的單位流費(fèi)用。

2.構(gòu)建隊(duì)列與標(biāo)記

-創(chuàng)建一個(gè)空隊(duì)列`queue`，用于緩存待處理（即可能被松弛）的節(jié)點(diǎn)。

-創(chuàng)建一個(gè)標(biāo)記數(shù)組`inqueue`，大小與節(jié)點(diǎn)總數(shù)相同，用于記錄節(jié)點(diǎn)是否當(dāng)前在隊(duì)列中。`inqueue[i]=false`表示節(jié)點(diǎn)i不在隊(duì)列中，`inqueue[i]=true`表示節(jié)點(diǎn)i在隊(duì)列中。這有助于避免重復(fù)將同一個(gè)節(jié)點(diǎn)加入隊(duì)列，從而提高效率。

（二）松弛操作

1.隊(duì)列處理流程

-(1)入隊(duì)源點(diǎn)：將源點(diǎn)S加入隊(duì)列`queue`，并設(shè)置`inqueue[S]=true`。

-(2)出隊(duì)并處理：當(dāng)隊(duì)列`queue`非空時(shí)，執(zhí)行以下操作：

-出隊(duì)一個(gè)節(jié)點(diǎn)`u`，即`u=queue.front();queue.pop();`，并設(shè)置`inqueue[u]=false`。

-對(duì)于節(jié)點(diǎn)`u`的每一個(gè)出邊`(u,v)`：

-檢查是否可以沿著邊`(u,v)`松弛節(jié)點(diǎn)`v`。松弛的條件通常是：

-`u`的流量`flow[u]`大于0（即邊`(u,v)`有剩余容量）。

-通過(guò)邊`(u,v)`到達(dá)`v`的當(dāng)前路徑費(fèi)用`dist[v]`大于通過(guò)邊`(u,v)`到達(dá)`v`的路徑費(fèi)用加上邊`(u,v)`的單位流費(fèi)用`cost[u][v]`。即`dist[v]>dist[u]+cost[u][v]`。

-如果滿足上述松弛條件，則進(jìn)行松弛操作：

-更新`v`的最短路徑估計(jì)：`dist[v]=dist[u]+cost[u][v]`。

-更新`v`的前驅(qū)節(jié)點(diǎn)：`pre[v]=u`。

-增加通過(guò)邊`(u,v)`的流量：`flow[u]-=1`，`flow[v]+=1`。

-如果`inqueue[v]`為`false`（即節(jié)點(diǎn)`v`當(dāng)前不在隊(duì)列中），則將節(jié)點(diǎn)`v`加入隊(duì)列`queue`，并設(shè)置`inqueue[v]=true`。

-(3)循環(huán)檢查：重復(fù)步驟(2)直到隊(duì)列為空。

2.費(fèi)用更新規(guī)則

-每次松弛操作的核心是更新目標(biāo)節(jié)點(diǎn)的最短路徑估計(jì)和前驅(qū)節(jié)點(diǎn)。具體來(lái)說(shuō)：

-計(jì)算通過(guò)邊`(u,v)`到達(dá)`v`的新路徑費(fèi)用：`new_dist[v]=dist[u]+cost[u][v]`。

-如果`new_dist[v]<dist[v]`，則說(shuō)明找到了一條更短的路徑到達(dá)`v`，因此更新`dist[v]=new_dist[v]`，并記錄這條路徑的新前驅(qū)節(jié)點(diǎn)`pre[v]=u`。

-松弛操作完成后，通過(guò)前驅(qū)節(jié)點(diǎn)數(shù)組`pre`可以回溯出從源點(diǎn)S到匯點(diǎn)T的最短費(fèi)用路徑。這條路徑上的流量可以增加（具體增加多少取決于路徑上各邊的剩余容量）。

（三）結(jié)果輸出

1.最大流判斷

-當(dāng)隊(duì)列為空且無(wú)法再找到從源點(diǎn)S到匯點(diǎn)T的增廣路徑時(shí)，算法終止。此時(shí)，當(dāng)前網(wǎng)絡(luò)中的流即為最大流。

-可以通過(guò)計(jì)算源點(diǎn)S的總出流量或匯點(diǎn)T的總?cè)肓髁縼?lái)確定最大流的流量值。這兩個(gè)值應(yīng)該相等，且等于最大流的總流量。

-如果在算法執(zhí)行過(guò)程中發(fā)現(xiàn)`dist[T]`仍然為無(wú)窮大（或某個(gè)預(yù)設(shè)的極大值），說(shuō)明網(wǎng)絡(luò)中存在負(fù)權(quán)環(huán)（即負(fù)費(fèi)用循環(huán)），此時(shí)算法無(wú)法找到最小費(fèi)用最大流。但在最小費(fèi)用最大流的標(biāo)準(zhǔn)問(wèn)題設(shè)定中，通常假設(shè)網(wǎng)絡(luò)是無(wú)負(fù)權(quán)環(huán)的。

2.結(jié)果輸出

-輸出最大流量值。

-輸出最小費(fèi)用值。最小費(fèi)用可以通過(guò)將最大流路徑上的流量乘以其單位流費(fèi)用并求和得到。

-輸出各邊的最終流量分布?？梢酝ㄟ^(guò)前驅(qū)節(jié)點(diǎn)數(shù)組`pre`回溯出每條邊是否在最大流路徑上，并根據(jù)路徑上的流量分配確定每條邊的具體流量。

三、算法實(shí)踐示例

（一）網(wǎng)絡(luò)構(gòu)建

1.節(jié)點(diǎn)與邊

-節(jié)點(diǎn)集合：{S,A,B,T}。

-邊集合及屬性：

-(S,A)：容量`capacity[S][A]=5`，單位流費(fèi)用`cost[S][A]=4`。

-(S,B)：容量`capacity[S][B]=2`，單位流費(fèi)用`cost[S][B]=1`。

-(A,B)：容量`capacity[A][B]=3`，單位流費(fèi)用`cost[A][B]=2`。

-(A,T)：容量`capacity[A][T]=4`，單位流費(fèi)用`cost[A][T]=3`。

-(B,T)：容量`capacity[B][T]=2`，單位流費(fèi)用`cost[B][T]=5`。

-注意：在實(shí)際的費(fèi)用網(wǎng)絡(luò)表示中，通常需要存儲(chǔ)所有可能的邊（包括方向性），即使某些邊的容量為0?？梢允褂绵徑泳仃嚮蜞徑颖韥?lái)存儲(chǔ)這些信息。

2.目標(biāo)

-求該網(wǎng)絡(luò)的最小費(fèi)用最大流。即找到一種流配置，使得從源點(diǎn)S到匯點(diǎn)T的總流量最大，同時(shí)滿足所有邊的容量約束和流量守恒，并且使得該流的總費(fèi)用（所有邊上的流量乘以其單位流費(fèi)用的總和）最小。

（二）迭代過(guò)程

1.初始狀態(tài)

-所有邊的流量`flow`初始化為0。

-源點(diǎn)S的流量為0，匯點(diǎn)T的流量為0（或目標(biāo)流量，如果指定）。

-最短路徑估計(jì)`dist`初始化：`dist[S]=0`，`dist[A]=∞`，`dist[B]=∞`，`dist[T]=∞`。

-前驅(qū)節(jié)點(diǎn)數(shù)組`pre`初始化：`pre[S]=-1`，`pre[A]=-1`，`pre[B]=-1`，`pre[T]=-1`。

-總費(fèi)用`total_cost`初始化為0。

2.第一次迭代

-(1)將源點(diǎn)S加入隊(duì)列`queue`，`inqueue[S]=true`。

-(2)隊(duì)列非空，出隊(duì)S。檢查S的出邊：

-邊(S,A)：松弛條件檢查：`flow[S]=0`（不滿足，不能松弛）。

-邊(S,B)：松弛條件檢查：`flow[S]=0`（不滿足，不能松弛）。

-(3)隊(duì)列為空，本次迭代結(jié)束，沒有進(jìn)行松弛操作。流量未增加。

3.第二次迭代

-(1)需要找到一條從S到T的增廣路徑。嘗試從S出發(fā)擴(kuò)展：

-從S出發(fā)，可以到達(dá)A和B。選擇一條路徑，例如S->A->T。

-檢查路徑S->A->T是否可行：

-邊(S,A)：剩余容量`capacity[S][A]-flow[S][A]=5-0=5`，滿足。

-邊(A,T)：剩余容量`capacity[A][T]-flow[A][T]=4-0=4`，滿足。

-計(jì)算路徑費(fèi)用：`cost[S][A]+cost[A][T]=4+3=7`。

-計(jì)算路徑上的最小剩余容量（即增廣流量的上限）：`min(5,4)=4`。

-(2)沿路徑S->A->T增廣流量4單位：

-更新流量：`flow[S][A]+=4`->4，`flow[A][T]+=4`->4。

-更新剩余容量：`capacity[S][A]-=4`->1，`capacity[A][T]-=4`->0。

-更新總費(fèi)用：`total_cost+=47=28`。

-(3)更新最短路徑估計(jì)和前驅(qū)節(jié)點(diǎn)（用于后續(xù)迭代）：

-對(duì)于路徑上的節(jié)點(diǎn)A和T：

-`dist[A]=min(dist[A],dist[S]+cost[S][A])=min(∞,0+4)=4`。

-`dist[T]=min(dist[T],dist[S]+cost[S][A]+cost[A][T])=min(∞,0+4+3)=7`。

-`pre[A]=S`，`pre[T]=A`。

-(4)將被更新的節(jié)點(diǎn)（或根據(jù)SPFA邏輯，將路徑終點(diǎn)T加入隊(duì)列）`queue`，`inqueue[T]=true`。

4.第三次迭代

-(1)隊(duì)列非空，出隊(duì)T。檢查T的出邊：

-邊(B,T)：松弛條件檢查：`flow[B]=0`，`flow[T]=4`，`dist[B]=∞`，`dist[T]=7`，`cost[B][T]=5`。`dist[B]>dist[T]+cost[B][T]`即`∞>7+5`成立?？梢运沙?。

-更新`dist[B]=12`，`pre[B]=T`。

-更新流量：`flow[B]+=4`->4，`flow[T]-=4`->0。

-更新剩余容量：`capacity[B][T]-=4`->-2（表示邊已滿，邏輯上不應(yīng)再松弛）。這里可能需要調(diào)整松弛邏輯或處理邊滿的情況。

-更新總費(fèi)用：`total_cost+=45=20`。

-將B加入隊(duì)列`queue`，`inqueue[B]=true`。

-(2)隊(duì)列非空，出隊(duì)B。檢查B的出邊：

-邊(B,T)：已經(jīng)處理過(guò)，流量為0，剩余容量為0，無(wú)法松弛。

-邊(B,A)：松弛條件檢查：`flow[B]=4`，`flow[A]=4`，`dist[A]=4`，`dist[B]=12`，`cost[B][A]`（假設(shè)存在，反向邊）需要定義。如果定義反向邊(B,A)的容量為0（即不允許反向流），則無(wú)法松弛。如果定義反向邊用于殘差網(wǎng)絡(luò)，則需要根據(jù)殘差網(wǎng)絡(luò)規(guī)則判斷。

-假設(shè)反向邊(B,A)容量為1，單位流費(fèi)用為-2（常見于殘差網(wǎng)絡(luò)表示最小費(fèi)用流問(wèn)題，但這里直接在原始網(wǎng)絡(luò)中反向松弛可能不直觀，且與最小費(fèi)用流的標(biāo)準(zhǔn)定義可能略有偏差）。如果反向松弛(B,A)：

-檢查：`flow[B]>0`，`dist[A]>dist[B]-cost[B][A]`即`4>12-(-2)`即`4>14`不成立，不能松弛。

-假設(shè)邊(B,A)不存在或容量為0，無(wú)法松弛。

-(3)隊(duì)列為空，本次迭代結(jié)束，沒有進(jìn)行新的有效松弛。

5.第四次迭代

-(1)嘗試找到新的增廣路徑。之前路徑S->A->T已用完。

-嘗試S->B->T路徑：

-邊(S,B)：剩余容量`2-0=2`。

-邊(B,T)：剩余容量`2-4=-2`（已滿，無(wú)法使用）。

-嘗試S->A->B->T路徑：

-邊(S,A)：剩余容量`1`。

-邊(A,B)：剩余容量`3-0=3`。

-邊(B,T)：剩余容量`2-4=-2`（已滿，無(wú)法使用）。

-嘗試S->B->A->T路徑：

-邊(S,B)：剩余容量`2`。

-邊(B,A)：假設(shè)存在，容量`3`（如果不存在或容量為0，則無(wú)法從B到A）。假設(shè)容量為3。

-邊(A,T)：剩余容量`0`（已用完，無(wú)法使用）。

-看起來(lái)直接從S到T的路徑已經(jīng)用完?？梢試L試從S到其他點(diǎn)，再擴(kuò)展：

-從S出發(fā)，可以到達(dá)A和B。A的路徑已阻塞（A->T邊已滿）。B的路徑也阻塞（B->T邊已滿）。

-算法無(wú)法找到新的增廣路徑。

（三）結(jié)果分析

-經(jīng)過(guò)上述迭代，最大流量為4（通過(guò)路徑S->A->T）。

-最小費(fèi)用為28（第一次迭代沿S->A->T增廣4單位，費(fèi)用28）。