一、最短路徑問(wèn)題

從圖中的某個(gè)頂點(diǎn)出發(fā)，到達(dá)另一個(gè)頂點(diǎn)的所經(jīng)過(guò)的邊的權(quán)重之和最小的一條路徑。

1.1 兩個(gè)指定頂點(diǎn)之間的最短路徑

問(wèn)題如下：給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，求一條最短鐵路線。

1.1.1 Dijkstra算法

迪杰斯特拉(Dijkstra)算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的。是尋找從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，可用來(lái)解決最短路徑問(wèn)題。詳細(xì)的講解可參考：數(shù)據(jù)結(jié)構(gòu)–Dijkstra算法最清楚的講解

更正：第2、3步中，B(23)應(yīng)為B(13)。

迪杰斯特拉算法采用貪心算法的策略，將所有頂點(diǎn)分為已標(biāo)記點(diǎn)和未標(biāo)記點(diǎn)兩個(gè)集合，從起始點(diǎn)開(kāi)始，不斷在未標(biāo)記點(diǎn)中尋找距離起始點(diǎn)路徑最短的頂點(diǎn)，并將其標(biāo)記，直到所有頂點(diǎn)都被標(biāo)記為止。 需要注意的一點(diǎn)是該方法不能處理帶有負(fù)權(quán)邊的圖，下面我們舉出一個(gè)實(shí)例并通過(guò)迪杰斯特拉方法對(duì)其進(jìn)行求解。

【例】 某公司在六個(gè)城市 $c_1,c_2,c_3,...,c_6$ 中有分公司，從 $c_i$ 到 $c_j$ 的直接航程票價(jià)記在下述矩陣的 $(i,j)$ 位置上(∞表示無(wú)直接航路)。請(qǐng)幫助該公司設(shè)計(jì)一張城市 $c_1$ 到其他城市間的票價(jià)最便宜的路線圖。

用矩陣 $a_{n\times n}$ (n為頂點(diǎn)個(gè)數(shù)) 存放各邊權(quán)的鄰接矩陣，行向量 分別用來(lái)存放 $P$ 標(biāo)號(hào)信息、標(biāo)號(hào)頂點(diǎn)順序、標(biāo)號(hào)頂點(diǎn)索引、最短通路的值。其中分量

$inde{x}_2(i)$ 存放始點(diǎn)到第 $i$ 頂點(diǎn)最短通路中第 $i$ 頂點(diǎn)的序號(hào)；$d(i)$ 存放由始點(diǎn)到第 $i$ 頂點(diǎn)最短通路的值。

求第一個(gè)城市到其他城市的最短路徑的Matlab程序如下：

clc,clear
a=zeros(6); %鄰接矩陣初始化
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a';  % 兩點(diǎn)之間的距離是一樣的→對(duì)稱矩陣
a(a==0)=inf;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
d(1:length(a))=inf;d(1)=0;
temp=1; %最新的P標(biāo)號(hào)的頂點(diǎn)
while sum(pb)<length(a)
   tb=find(pb==0);
   d(tb)=min(d(tb),d(temp)+a(temp,tb));
   tmpb=find(d(tb)==min(d(tb)));
   temp=tb(tmpb(1)); %可能有多個(gè)點(diǎn)同時(shí)達(dá)到最小值，只取其中的一個(gè)
   pb(temp)=1;
   index1=[index1,temp];
   temp2=find(d(index1)==d(temp)-a(temp,index1));
   index2(temp)=index1(temp2(1));
end
d, index1, index2

運(yùn)行結(jié)果為：

結(jié)果表示，最終求得的 $c_1$ 到 $c_2,...,c_6$ 的最便宜票價(jià)分別為35，45，35，25，10。

1.1.2 Matlab函數(shù)

【例】 在下圖中，用點(diǎn)表示城市，現(xiàn)有 $v_1,v_2,...,v_5$ 共5個(gè)城市。點(diǎn)與點(diǎn)之間的連線表示城市間有道路相連。連線旁的數(shù)字表示道路的長(zhǎng)度?，F(xiàn)計(jì)劃從城市 $v_1$ 到城市 $v_3$ 鋪設(shè)一條天然氣管道，請(qǐng)?jiān)O(shè)計(jì)出最小長(zhǎng)度管道鋪設(shè)方案。

除了上面提到的迪杰斯特拉求兩點(diǎn)之間最短路徑外，我們還可以使用MATLAB自帶的graphshortestpath函數(shù)。

W = [10,5,1,2,4,7,6,3,9,2];
% sparse生成稀疏矩陣，除了標(biāo)注的元素外，其余都是0
DG = sparse([1,1,2,2,3,4,4,5,5,5],...  % sparse第一個(gè)矩陣，三個(gè).代表沒(méi)寫(xiě)完，下一行接著
            [2,5,3,5,4,1,3,2,3,4],W)  % sparse第二個(gè)矩陣
% sparse里第一個(gè)和第二個(gè)矩陣相同位置的元素值就是非零元素的值，W是每條邊的權(quán)值
% dist是最短路徑的值，path是最短路徑的節(jié)點(diǎn)順序，pred是每一個(gè)節(jié)點(diǎn)的最短路徑的終點(diǎn)前一個(gè)節(jié)點(diǎn)
[dist,path,pred] = graphshortestpath(DG,1,3)  % 節(jié)點(diǎn)1到3的最短路徑
point_name = ["city1","city2","city3","city4","city5"];
p = biograph(DG,point_name,'ShowWeights','on')
h = view(p)  % biograph生成圖對(duì)象，view顯示該圖

我們可以查看一下sparse生成的稀疏矩陣DG：

從矩陣的角度看：

用view顯示此時(shí)生成的圖對(duì)象：

然后，我們將通過(guò)該函數(shù)計(jì)算得到的最短路徑節(jié)點(diǎn)以紅色顯示：

% 將最短路徑的結(jié)點(diǎn)以紅色顯示
set(h.Nodes(path),'Color',[1 0.4 0.4]);
% 將最短路徑的弧以紅色顯示
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));  % getedgesbynodeid得到圖h指定便的句柄，第一個(gè)參數(shù)是圖，第二個(gè)是邊的出點(diǎn)，第三個(gè)是邊的入點(diǎn)  
% get查詢圖的屬性   set用來(lái)設(shè)置圖形屬性
set(edges,'LineColor',[1 0 0]);  % RGB數(shù)值
set(edges,'LineWidth',2.0);

注意：這里的ID是Matlab自帶的。

1.2 每對(duì)頂點(diǎn)之間的最短路徑

1.2.1 Dijkstra算法

計(jì)算賦權(quán)圖中各對(duì)頂點(diǎn)之間最短路徑，顯然可以調(diào)用Dijkstra算法。具體方法是：每
次以不同的頂點(diǎn)作為起點(diǎn)，用Dijkstra算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑， 反復(fù)執(zhí)行n-1次這樣的操作，就可得到從每一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。這種算法的時(shí)間復(fù)雜度 $O(n^3)$ 為。

1.2.2 Floyd算法

第二種解決這一問(wèn)題的方法是由R. W. Floyd提出的算法，稱為Floyd算法。其時(shí)間復(fù)雜度也是 $O(n^3)$ ，但形式上要簡(jiǎn)單些。

對(duì)于賦權(quán)圖 $G=(V,E,A_0)$ ，其中，頂點(diǎn)集 $V$ = {$v_1,...,v_n$}，鄰接矩陣

其中，

Floyd算法的基本思想是遞推產(chǎn)生一個(gè)矩陣序列 $A_1,...A_k,...A_n$， 其中矩陣A的第 $i$ 行第 $j$ 列元素 $A_k(i,j)$ 表示從頂點(diǎn) $v_i$ 到頂點(diǎn) $v_j$ 的路徑上所經(jīng)過(guò)的頂點(diǎn)序號(hào)不大于 $k$ 的最短路徑長(zhǎng)度。

計(jì)算時(shí)利用迭代公式：

舉一個(gè)簡(jiǎn)單的例子幫助大家理解：

對(duì)上述信息初始化：

第一次迭代時(shí)，以 a 為起點(diǎn)判斷矩陣是否需要更新：

第二次迭代，加入頂點(diǎn) b，即k=1時(shí)判斷矩陣是否需要更新：

第三次迭代，加入頂點(diǎn) c，即k=2時(shí)判斷矩陣是否需要更新：

上述案例來(lái)自B站：數(shù)據(jù)結(jié)構(gòu)

【例】用Floyd算法求解和之前同樣的問(wèn)題。

Matlab代碼如下：

clear;clc;
n=6; a=zeros(n);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25; a(5,6)=55;
a=a+a'; 
a(a==0)=inf;  % 把所有零元素替換成無(wú)窮
a([1:n+1:n^2])=0;  % 對(duì)角線元素替換成零，Matlab中數(shù)據(jù)是逐列存儲(chǔ)的★
path=zeros(n);
for k=1:n
   for i=1:n
      for j=1:n
         if a(i,j)>a(i,k)+a(k,j)
            a(i,j)=a(i,k)+a(k,j);
            path(i,j)=k;
         end 
      end
   end
end
a, path

求出來(lái)的結(jié)果為：

矩陣 $a$ 的第一行求得 $c_1$ 到 $c_2,...,c_6$ 的最便宜票價(jià)分別為35，45，35，25，10。

1.2.3 Matlab函數(shù)

利用graphallshortestpaths函數(shù)，可以求出所有結(jié)點(diǎn)之間的最短路徑。

Dists = graphallshortestpaths(DG)  %求所有最短路徑

以1.1.2中的為例，我們可以看到求得的矩陣中城市 $v_1$ 到城市 $v_3$ 的最小路徑為9。

二、最小生成樹(shù)問(wèn)題

欲修筑連接 n 個(gè)城市的鐵路，已知 $i$ 城與 $j$ 城之間的鐵路造價(jià)為 $c_{ij}$ 設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。上述問(wèn)題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹(shù)。賦權(quán)圖的具有最小權(quán)的生成樹(shù)叫做最小生成樹(shù)。 下面介紹構(gòu)造最小生成樹(shù)的兩種常用算法。

2.1 Kruskal算法

1、把圖 $G$ 中的所有邊全部去掉，得到所有單獨(dú)的頂點(diǎn) $V$ 構(gòu)成圖 $T=(V,$ { } $)$，其中 $V$ 是頂點(diǎn)集合；
2、從 $G$ 中取出當(dāng)前權(quán)值最小的邊，如果該邊加入 $T$ 的邊的集合后 $T$ 不形成回路，則加入 $T$ ；否則舍棄；
3、重復(fù)第2步，直到 $T$ 中有 $n?1$ 條邊 （ $n$ 是頂點(diǎn)數(shù)）；
4、若第2步中遇到兩條權(quán)值相同的最小權(quán)值邊，任選一條即可，所以最小生成樹(shù)可能不唯一，但權(quán)值之和相同。

Kruskal簡(jiǎn)單理解就是每次都選一條權(quán)值最小的邊。適合邊少點(diǎn)多的圖。

用Kruskal算法求解上圖的Matlab代碼為：

clc;clear; 
% 輸入鄰接矩陣
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; 
a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30; 
a(4,7)=42; a(5,6)=70;  
[i,j,b]=find(a);

[i,j,b]=find(a)這一步的含義是求出有權(quán)值邊的索引。

構(gòu)建弧表表示矩陣data，及所有邊的索引矩陣index：

data=[i';j';b']
index=data(1:2,:)

loop=max(size(a))-1;
result=[];
while length(result)<loop 
   temp=min(data(3,:));  % 30
   flag=find(data(3,:)==temp);  % 7-->在第七個(gè)位置上
   flag=flag(1);
   v1=data(1,flag);  % 第7個(gè)位置上對(duì)應(yīng)的第一行數(shù)據(jù)為4
   v2=data(2,flag);  % 第7個(gè)位置上對(duì)應(yīng)的第二行數(shù)據(jù)為6
   if index(1,flag)~=index(2,flag) 
      result=[result,data(:,flag)]; % 4 6 30
   end 
   index(find(index==v2))=v1; % 把index里面的6全部改成4
   data(:,flag)=[]; % 刪除第七個(gè)位置的三個(gè)值 4 6 30
   index(:,flag)=[]; % 刪除第七個(gè)位置的索引
end 
result 

求得的結(jié)果為：

在圖上標(biāo)注出最小生成樹(shù)如下：

2.2 Prim算法

1、設(shè)置一個(gè)圖 $U$ ，將原圖 $G$ 中任意一頂點(diǎn)取出加入 $U$ 中；
2、在所有 $u\in U$， $v\in (V?U)$ 的邊 $(u,v)$ 中找到一條權(quán)值最小的邊，并入圖 $U$ 中；
3、重復(fù)步驟2，直到 $U$ 中包含了所有頂點(diǎn)；
4、若第2步中遇到兩條權(quán)值相同的最小權(quán)值邊，任選一條即可，所以最小生成樹(shù)可能不唯一，但權(quán)值之和相同。

Prim算法簡(jiǎn)單理解就是選頂點(diǎn)。適合邊多點(diǎn)少的圖。

使用Prim算法求解的Matlab代碼如下：

a=zeros(7);
a(1,2)=50; 
a(1,3)=60; 
a(2,4)=65; 
a(2,5)=40; 
a(3,4)=52;
a(3,7)=45; 
a(4,5)=50; 
a(4,6)=30;
a(4,7)=42; 
a(5,6)=70;  
a=a+a';
a(find(a==0))=inf;

初始化之后的矩陣 $a$ 為：

result=[]  % 存儲(chǔ)最小生成樹(shù)
p=1;  % 選取頂點(diǎn)1
tb=2:length(a)  % 剩余頂點(diǎn)
while length(result)~=length(a)-1  % 當(dāng)邊的個(gè)數(shù)=n-1時(shí)，退出循環(huán)
   temp=a(p,tb);  % tb中存儲(chǔ)著其他未處理的頂點(diǎn),temp存儲(chǔ)著未處理的邊的權(quán)重
   temp=temp(:); 
   d=min(temp); 
   [jb,kb]=find(a(p,tb)==d);  % 找到最小權(quán)的橫縱坐標(biāo)
   j=p(jb(1));  % j存儲(chǔ)找到的邊的起始位置，可能有多最小權(quán)，但我們只取一個(gè)
   k=tb(kb(1));  % k存儲(chǔ)找到的邊的末位置，可能有多最小權(quán)，但我們只取一個(gè)
   result=[result,[j;k;d]];  % 存儲(chǔ)找到的此條邊的信息
   p=[p,k];  % 包含新加入的頂點(diǎn)
   tb(find(tb==k))=[];  % 在tb中刪除與剛加入的邊相連接的點(diǎn) 
end 
result

最終得到的結(jié)果為：

求得的最小生成樹(shù)在圖上標(biāo)注為：

我們可以看到，當(dāng)邊的權(quán)值無(wú)重復(fù)值時(shí)，用Kruskal和Prim求得的最小生成樹(shù)是一致的。

三、網(wǎng)絡(luò)最大流問(wèn)題

網(wǎng)絡(luò)流優(yōu)化問(wèn)題一般是指在有向圖中分配流量，使每條邊的流量不會(huì)超過(guò)它的容量約束（Capacity），同時(shí)達(dá)到路徑長(zhǎng)度最小或者花費(fèi)最小等目標(biāo)函數(shù)的優(yōu)化問(wèn)題。因?yàn)樵谶\(yùn)籌學(xué)中，我們經(jīng)常把有向圖稱為網(wǎng)絡(luò)。所以這類基于有向圖流量分配的優(yōu)化問(wèn)題也被稱之為網(wǎng)絡(luò)流優(yōu)化問(wèn)題。網(wǎng)絡(luò)流優(yōu)化屬于組合優(yōu)化問(wèn)題的一種。

3.1 網(wǎng)絡(luò)流問(wèn)題基礎(chǔ)

本小節(jié)內(nèi)容參考B站（強(qiáng)推?。。。?3-1: 網(wǎng)絡(luò)流問(wèn)題基礎(chǔ) Network Flow Problems

左圖邊的權(quán)重表示水管的容量，允許多少水流入。右圖邊的權(quán)重表示水管的空閑量，初始值是相同的，剛開(kāi)始時(shí)沒(méi)有水流入水管。算法在執(zhí)行時(shí)，我們會(huì)用到右邊的圖。

第一次迭代： 選取一條從起點(diǎn) $s$ 到 $t$ 的簡(jiǎn)單路徑（不能有回路）。假設(shè)找到了一條路徑，用紅色標(biāo)注為：

路徑上的權(quán)重為3、3、2，由于短板效應(yīng)，這條路徑上只能通過(guò)流量為2的水。我們讓容量為2的水通過(guò)該條路徑，那么就要更新Residual的值。

注意上面有兩條管道Residual值為0，已經(jīng)飽和，代表它們不能輸送更多的水流了，在圖中我們將這兩條管道刪除。

以上就是第一輪循環(huán)。

第二輪迭代： 仍然是找到一條從起點(diǎn) $s$ 到 $t$ 的簡(jiǎn)單路徑。

同樣地，更新Residual的值。

刪除飽和的邊：

第三輪迭代： 找到一條從起點(diǎn) $s$ 到 $t$ 的簡(jiǎn)單路徑。

更新Residual的值。

在圖上刪除已經(jīng)飽和的邊：

第四輪迭代： 仍然試圖找到一條從起點(diǎn) $s$ 到 $t$ 的簡(jiǎn)單路徑。但是此時(shí)不存在這樣的路徑，算法終止。

根據(jù) $Flow=Capacity?Residual$ 計(jì)算可得 $flow$（圖中紅色標(biāo)注）。

那么，我們可以得到總流量為5。兩個(gè)角度可以計(jì)算總流量：有兩份水從起點(diǎn)流出，流量分別為3和2。此外，有兩份水流入終點(diǎn)，流量分別為2和3。

以上是一種簡(jiǎn)單的找網(wǎng)絡(luò)流的算法，但是該算法不能保證最優(yōu)性（結(jié)果不一定是最大流），舉一個(gè)簡(jiǎn)單的例子。

假設(shè)第一輪循環(huán)找的路徑為：$S?v_1?v_4?t$，更新Residual的值。

第二輪找到的路徑為：$S?v_1?v_3?t$，更新Residual的值。

第三輪循環(huán)，找不到一條能從起點(diǎn)到重點(diǎn)的路徑，算法結(jié)束。但是此時(shí) $flow=4$ 并不是網(wǎng)絡(luò)的最大流。

$flow=4$ 稱為 $Blocking$ $Flow$，它雖然不是最大流，但是它將管道堵住了不能讓更多的水流通過(guò)，所以稱為阻塞流。顯而易見(jiàn)，最大流也是一種阻塞流。

我們可以看到，尋找路徑的先后順序變了之后，就有可能找不到最大流。所以，之后我們需要學(xué)習(xí)一些優(yōu)化算法。

3.2 Ford-Fulkerson算法

3.1小節(jié)中的簡(jiǎn)單算法有個(gè)缺陷：一旦找到一條不是最大流的路徑，就不能更正。這節(jié)課所學(xué)的算法，可以反悔，將不好的路徑撤銷。該節(jié)內(nèi)容依舊是參考：13-2: Ford-Fulkerson Algorithm 尋找網(wǎng)絡(luò)最大流
該算法比之前講的簡(jiǎn)單算法多了一步：增加反向路徑。

仍然是之前那個(gè)例子。第一次循環(huán) 找到路徑 $S?v_1?v_4?t$ （允許讓容量為3 的水通過(guò)），更新Residual的值。

然后，增加一個(gè)反向路徑，允許讓容量為3的水原路流回去，這樣的話，選擇的路徑不是最好的，我們就可以選擇撤銷。

第二輪循環(huán)，找到路徑 $S?v_1?v_3?t$ ，并添加反向路徑：

合并方向相同的路徑：

第三輪循環(huán)，假如沒(méi)有反向路徑的化，算法就會(huì)終止。但是添加了反向路徑之后，有下面這樣的結(jié)果：

合并方向相同邊的權(quán)重：

第四輪循環(huán)，沒(méi)有任何水流能流入 $v_3$ 和 $t$。找不到路徑，算法終止。

算法結(jié)束后，不再需要反向流，將其去除。

最壞情況下的時(shí)間復(fù)雜度：

如果每次找的都是100→1→100這樣的路徑，那么要200次才能找到最大流。

更多細(xì)節(jié)可參考：最大流問(wèn)題與Ford-Fulkerson算法介紹

3.3 Edmonds-Karp算法

Edmonds-Karp算法與Ford-Fulkerson算法唯一的區(qū)別就在于，前者在尋找路徑時(shí)使用最短路徑算法（將Residual圖所有邊的權(quán)重都視為1，找到步長(zhǎng)最短的那一條路徑）。而后者允許使用任意方法尋找路徑，因此可以將Edmonds-Karp算法看作是后者的一種特殊情況。

這個(gè)算法的貢獻(xiàn)在于提升了時(shí)間復(fù)雜度，不依賴于網(wǎng)絡(luò)流的大小，之和邊和結(jié)點(diǎn)有關(guān)。

Edmonds-Karp算法時(shí)間復(fù)雜度分析：

• 記 $m$ 為圖中邊的數(shù)量， $n$ 為圖中頂點(diǎn)的數(shù)量，每一輪循環(huán)都是要找到一條最短路徑，所以每一輪循環(huán)的時(shí)間復(fù)雜度為 $O(m)$。
• 原圖中有 $m$ 條邊，那么最多會(huì)有 $m$ 條反向邊，所以Residual graph最多含有 $2m$ 條邊。
• 算法證明最多循環(huán) $m\times n$ 輪。（證明過(guò)程略復(fù)雜，省略）
• 每一輪需要$O(m)$，最多循環(huán) $m\times n$ 輪，所以最壞時(shí)間復(fù)雜度為$O(m^2?n)$。
• 這個(gè)時(shí)間復(fù)雜度與最大流大小無(wú)關(guān)，實(shí)際應(yīng)用中即使最大流很大，也不會(huì)有影響，因此該算法要優(yōu)于Ford-Fulkerson算法。

3.4 Dinic’s算法

該算法引入了一個(gè)新的概念：Level Graph。下面簡(jiǎn)單演示一下如何構(gòu)建Level Graph。

從起點(diǎn) $s$ 開(kāi)始，將一步能到達(dá)的節(jié)點(diǎn) $v_1$ 和 $v_2$ 記作第一層節(jié)點(diǎn)，并保留其權(quán)重邊。

再?gòu)牡谝粚拥墓?jié)點(diǎn) $v_1$ 和 $v_2$ 出發(fā)，走一步能到達(dá)的節(jié)點(diǎn)有 $v_3$ 和 $v_4$ ，將這兩個(gè)節(jié)點(diǎn)加入到Level Graph中的第二層節(jié)點(diǎn)，并保留權(quán)值邊。

再?gòu)牡诙拥墓?jié)點(diǎn) $v_3$ 和 $v_4$ 出發(fā)，走一步能到達(dá)終點(diǎn) $t$。將終點(diǎn) $t$ 當(dāng)作第三層節(jié)點(diǎn)。

Level Graph中只允許從上一層節(jié)點(diǎn)到下一層節(jié)點(diǎn)邊的存在，不允許其他邊（同層之間或從下層到上層）的存在。

一個(gè)更復(fù)雜的例子，大家可以先自行畫(huà)出Level Graph，看看是否與左邊的結(jié)果一致：

下面正式以一個(gè)簡(jiǎn)單的例子來(lái)講解Dinic’s算法。

初始化：

第一輪循環(huán)： 把Residual Graph作為輸入，構(gòu)建其Level Graph。

然后在左邊構(gòu)造好的Level Graph中尋找阻塞流（blocking flow）。 （注意：阻塞流未必是最大流），下圖中用紅色標(biāo)識(shí)阻塞流。

讓阻塞流通過(guò)Residual Graph，那么就要相應(yīng)更新Residual Graph的值。

然后增加反向流。刪除此輪構(gòu)造的Level Graph。

第二輪循環(huán)： Residual Graph沿用第一輪更新后的樣子。構(gòu)造其Level Graph。

找到該Level Graph中的阻塞流，并更新Residual Graph。

然后增加反向流（注意有相同方向的邊需要合并權(quán)重值）。刪除此輪構(gòu)造的Level Graph。

第三輪循環(huán)： Residual Graph沿用第二輪更新后的樣子。構(gòu)造其Level Graph。注意這里與之前不同的是，該輪中從起點(diǎn)走一步只能到達(dá)一個(gè)節(jié)點(diǎn)，并且后續(xù)無(wú)法到達(dá)其他節(jié)點(diǎn)，所以將其他節(jié)點(diǎn)設(shè)為∞。

此時(shí)，我們就要終止程序，并將最后得到的Residual Graph中反向邊刪去。

仍然用 $Flow=Capacity?Residual$ 計(jì)算流量，最終算出最大流為19。

時(shí)間復(fù)雜度：

3.5 最小割問(wèn)題（Min-Cut）

3.5.1 S-T Cut

將頂點(diǎn)集合 $V$ 切割為兩個(gè)集合 $S$ 和 $T$ 之后， $S\cup T=V$ 且 $S\cap T=?$，其中起點(diǎn) $s\in S$，終點(diǎn) $t\in T$。那么$(S,T)$稱為 S-T Cut。

S-T Cut 容量（Capacity） 的定義為離開(kāi)集合 $S$ 的邊的權(quán)重之和。上圖中$Capacity(S,T)=6$。S-T Cut 并不唯一，下圖中容量為3。

Min-cut簡(jiǎn)單來(lái)說(shuō)，就是所有S-T Cut中容量最小的。意味著我們想要割斷少數(shù)的細(xì)的管道就能阻斷水流（花的代價(jià)?。?。

最小割可能并不唯一。

3.5.2 ★最大流-最小割定理（Max-Flow Min-Cut Theorem）

網(wǎng)絡(luò)的最大流等于最小割容量。

3.5.3 尋找最小割的方法

只要找到最小割就可以找到最大流。

1、首先用任意的最大流算法得到最終的Residual graph，并忽略其中的反向邊。
2、在Residual graph中，將從起點(diǎn) $s$ 一步能到達(dá)的節(jié)點(diǎn)歸入集合 $S$。將無(wú)法到達(dá)的節(jié)點(diǎn)歸入集合 $T$。這樣，我們就得到了最小割 $(S,T)$。

舉一個(gè)簡(jiǎn)單的例子，首先用最大流算法得到Residual graph。

然后從Residual graph中得到最小割。

上述內(nèi)容來(lái)自B站：13-5: 最小割 Min-Cut

四、二分圖

挖坑------------------------------未完待續(xù)-----------------------------------文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-784008.html

到了這里，關(guān)于數(shù)學(xué)建模十大算法04—圖論算法（最短路徑、最小生成樹(shù)、最大流問(wèn)題、二分圖）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！