算法設(shè)計與分析 ch7 學(xué)習(xí)課件

2/28/2025第七章

圖論算法王宏志計算機科學(xué)與工程系

2/28/20257.1

最短路徑問題7.2

網(wǎng)絡(luò)流問題7.3

匹配問題提要

2/28/2025

7.1最短路徑問題

2/28/2025單源最短路徑問題:給定一個有權(quán)的有向圖G，找到從給定源結(jié)點v到另一個結(jié)點v的最短路徑。

2/28/2025最短路徑的性質(zhì)優(yōu)化子結(jié)構(gòu):最短路徑包含最短子路徑證明:如果某條子路徑不是最短子路徑必然存在最短子路徑用最短子路徑替換當(dāng)前子路徑當(dāng)前路徑不是最短路徑，矛盾!

2/28/2025最短路徑的性質(zhì)

(u,v)是從u到v最短路徑的權(quán)重最短路徑滿足

三角不等式:(u,v)(u,x)+(x,v)“證明”:xuv這條路徑不會比另外兩條之和長

2/28/2025最短路徑的性質(zhì)如果圖中包含負圈，某些最短路徑可能不存在

(Why?):<0

2/28/2025松弛最短路徑算法的核心技術(shù)是松弛Relax(u,v,w){if(d[v]>d[u]+w)thend[v]=d[u]+w;}952752Relax652652Relax

2/28/2025Bellman-Ford算法BellmanFord()foreachvVd[v]=;d[s]=0;fori=1to|V|-1foreachedge(u,v)ERelax(u,v,w(u,v));foreachedge(u,v)Eif(d[v]>d[u]+w(u,v))return“nosolution”;Relax(u,v,w):if(d[v]>d[u]+w)thend[v]=d[u]+w時間復(fù)雜性？

2/28/2025Bellman-Ford算法BellmanFord()foreachvVd[v]=;d[s]=0;fori=1to|V|-1foreachedge(u,v)ERelax(u,v,w(u,v));foreachedge(u,v)Eif(d[v]>d[u]+w(u,v))return“nosolution”;Relax(u,v,w):if(d[v]>d[u]+w)thend[v]=d[u]+w初始化d

松弛:

進行|V|-1輪,松弛每條邊檢驗結(jié)果

何時得到解?

2/28/2025Bellman-FordAlgorithmBellmanFord()foreachvVd[v]=;d[s]=0;fori=1to|V|-1foreachedge(u,v)ERelax(u,v,w(u,v));foreachedge(u,v)Eif(d[v]>d[u]+w(u,v))return“nosolution”;Relax(u,v,w):if(d[v]>d[u]+w)thend[v]=d[u]+w運行時間是多少？A:O(VE)

2/28/2025Bellman-FordAlgorithmBellmanFord()foreachvVd[v]=;d[s]=0;fori=1to|V|-1foreachedge(u,v)ERelax(u,v,w(u,v));foreachedge(u,v)Eif(d[v]>d[u]+w(u,v))return“nosolution”;Relax(u,v,w):if(d[v]>d[u]+w)thend[v]=d[u]+wBEDCA-1221-3534s

2/28/2025Bellman-Ford注意到處理邊的順序影響到收斂速度正確性:證明|V|-1輪之后d[v]=(s,v)引理:d[v](s,v)總成立起始顯然令v是滿足d[v]<(s,v)的第一個點令u使得d[v]發(fā)生變化:

d[v]=d[u]+w(u,v)那么d[v] <(s,v)

(s,v)(s,u)+w(u,v) (Why?)

(s,u)+w(u,v)d[u]+w(u,v) (Why?)因此d[v]<d[u]+w(u,v).矛盾.

2/28/2025Bellman-Ford證明:|V|-1輪之后,所有d

的值正確考慮從s到v的最短路徑:

sv1v2v3v4v開始,d[s]=0正確,不發(fā)生變化(Why?)1輪之后,d[v1]正確(Why?)不發(fā)生變化2輪之后,d[v2]正確不發(fā)生變化…|V|-1輪之后停下:(Why?)

2/28/2025DAG中最短路徑Problem:尋找DAG中最短路徑Bellman-Ford時間是O(VE).能否做的好一點呢？Idea:使用拓撲排序如果沿著最短路徑作，則可以一遍完成DAG中的每條路徑都是拓撲排序得到結(jié)點序列的一個子序列，那么，如果按照這個順序處理，我們將沿著路徑進行處理因此，掃描一次就夠了.時間復(fù)雜性是多少？

2/28/2025Dijkstra算法如果沒有負邊，我們可以超越類似BFS從隊列中取結(jié)點類似Prim算法使用以d[v]為鍵的優(yōu)先隊列

2/28/2025Dijkstra’sAlgorithmDijkstra(G)foreachvVd[v]=;d[s]=0;S=;Q=V;while(Q)u=ExtractMin(Q);S=SU{u};foreachvu->Adj[]if(d[v]>d[u]+w(u,v))d[v]=d[u]+w(u,v);松弛步驟Note:調(diào)用了

Q->DecreaseKey()BCDA1043215

2/28/2025Dijkstra算法Dijkstra(G)foreachvVd[v]=;d[s]=0;S=;Q=V;while(Q)u=ExtractMin(Q);S=SU{u};foreachvu->Adj[]if(d[v]>d[u]+w(u,v))d[v]=d[u]+w(u,v);正確性:我們必須證明，當(dāng)u從Q中取出時，它已經(jīng)收斂了

2/28/2025Dijkstra算法的正確性d[v](s,v)v令u是第一個選出的結(jié)點s.t.存在比d[u]更短的路徑 d[u]>(s,u)令y是su真實最短路徑上的第一個V-S的結(jié)點d[y]=(s,y)d[u] >(s,u)

=(s,y)+(y,u)(Why?)

=d[y]+(y,u)

d[y] 但是如果d[u]>d[y],則不會選擇u.矛盾sxyup2p2

2/28/2025任意兩點最短路徑Problem:

找到圖中每一對結(jié)點間最短路徑

圖可能包含負邊但是不包含負圈

表示：權(quán)矩陣

2/28/2025圖和權(quán)矩陣v1v2v3v4v53224131935

2/28/2025子問題如何定義更小的問題？一種方法是將路徑限制在僅包含一個有限集合中的結(jié)點

開始這個集合是空的

這個集合可以一直增長到包含所有結(jié)點。

2/28/2025子問題令

D(k)[i,j]=從vi

到vj僅包含{v1,v2,…,vk}的路徑。D(0)=WD(n)=D

目標矩陣如何從D(k-1)計算D(k)?

2/28/2025遞歸定義因為

D(k)[i,j]=D(k-1)[i,j]or

D(k)[i,j]=D(k-1)[i,k]+D(k-1)[k,j].

我們得到

D(k)[i,j]=min{D(k-1)[i,j],D(k-1)[i,k]+D(k-1)[k,j]}.ViVjVk僅包含{V1,...Vk-1}的最短路徑僅包含{V1,...Vk

}的最短路徑

2/28/2025Floyd算法1.D0

W//初始化D

2.P

0//初始化P

3.fork1ton

4.dofori1ton

5.doforj1ton

6.

if(Dk-1[i,j]>Dk-1

[i,k]+Dk-1

[k,j])

7. thenDk[i,j]Dk-1

[i,k]+Dk-1

[k,j]

7. P[i,j]

k;

9. elseDk[i,j]Dk-1

[i,j]

2/28/2025例子W=D0=40520

-30123123000000000123123P=1235-324

2/28/2025

D1=405207

-30123123000001000123123P=1235-324D1[2,3]=min(D0[2,3],D0[2,1]+D0[1,3]) =min(,7) =7D1[3,2]=min(D0[3,2],D0[3,1]+D0[1,2]) =min(-3,) =-340520

-30123123D0=

2/28/2025

D2=405207-1-30123123000001200123123P=D2[1,3]=min(D1[1,3],D1[1,2]+D1[2,3]) =min(5,4+7) =5D2[3,1]=min(D1[3,1],D1[3,2]+D1[2,1]) =min(,-3+2) =-11235-324

D1=405207

-30123123

2/28/2025

D3=205207-1-30123123300001200123123P=D3[1,2]=min(D2[1,2],D2[1,3]+D2[3,2]) =min(4,5+(-3)) =23[2,1]=min(D2[2,1],D2[2,3]+D2[3,1]) =min(2,7+(-1)) =2

D2=405207-1-301231231235-324

2/28/2025Floyd算法:使用兩個D矩陣Floyd

1.D

W

2.P

0

3.fork1ton

//ComputingD’fromD

4.dofori1ton

5.doforj1ton

6.

if(D[i,j]>D[i,k]+D[k,j])

7. thenD’[i,j]D[i,k]+D[k,j]

7. P[i,j]

k;

9. elseD’[i,j]D[i,j]

10. MoveD’toD.

2/28/2025Floyd算法：使用1個DFloyd

1.D

W

2.P

0

3.fork1ton

4.dofori1ton

5.doforj1ton

6.

if(D[i,j]>D[i,k]+D[k,j])

7. thenD[i,j]D[i,k]+D[k,j]

7. P[i,j]

k;

2/28/2025打印出從p到r的路徑path(indexq,r) if(P[q,r]!=0) path(q,P[q,r])

println(“v”+P[q,r]) path(P[q,r],r)

return; //nointermediatenodes

else

return300001200123123P=1235-324

2/28/2025

7.2網(wǎng)絡(luò)流問題

2/28/2025網(wǎng)絡(luò)有向圖G=(V,E)

滿足每個有向邊e

有一個非負容量ce有一個源結(jié)點s

沒有入邊有一個目標點t(target)沒有出邊20ts10uv201030u,v–中間結(jié)點

2/28/2025流G=(V,E)

中的s-t流是一個從E

到R+的函數(shù)f滿足容量條件:

對每個e,0

f(e)

ce保存條件:

對每個中間結(jié)點v,∑einv

f(e)=

∑eoutv

f(e)源和匯滿足:∑eint

f(e)=

∑eouts

f(e)20ts10uv20103020ts10uv201010流:網(wǎng)絡(luò):

2/28/2025相關(guān)定義給定圖G=(V,E)中s-t流f

和任意結(jié)點集合Sfin(S)=∑einS

f(e)fout(S)=∑eoutS

f(e)性質(zhì):fin(t)=fout(s)例子:fin(u,v)=fout(u,v)=3020ts10uv20103020ts10uv201010流:網(wǎng)絡(luò):

2/28/2025問題對于給定的圖G=(V,E)，最大的fin(t)是多少？如何高效地計算?假設(shè):

容量都是正數(shù).例:fin(t)=fout(s)=3020ts10uv20103020ts10uv201010流:網(wǎng)絡(luò):

2/28/202538余圖給定圖G.中的流f余圖Gf

同樣的結(jié)點，中間結(jié)點和s,t對于每條邊e

滿足ce>f(e)

賦給權(quán)重ce-f(e)(剩余容量)對于每條邊e=(u,v)

給其逆向邊(v,u)賦給權(quán)重f(e)(剩余容量)20ts10uv20103020ts0uv20020流:20ts10v10余圖:u1020網(wǎng)絡(luò):

2/28/2025增廣路徑和增廣給定圖G中的流f,及其對應(yīng)的余圖Gf

找到余圖中的一條新流，該流通過一條沒有重復(fù)結(jié)點的路徑并且值和該路徑上的最小容量相等(增廣路徑)沿著路徑更新余圖20ts10uv201030新的流:20ts10v2010新的余圖:u201020ts10v20101010u20網(wǎng)絡(luò):

2/28/2025Ford-Fulkerson算法對于所有e初始化f(e)=0While余圖中存在s-t路徑

P沿著路徑P增廣

f

得到新的f

和新的余圖沿著P增廣

f

:找到路徑的最小容量沿著路徑修改權(quán)重20ts10uv201030新流:20ts10v2010新余圖:u201020ts10v20101010u20網(wǎng)絡(luò):

2/28/2025分析正確性:最大流–一會證明可終止行–每次流是一個整數(shù)且最少增加1(假定整數(shù)容量)時間:O(mC)最多C

輪iterations,其中

C

是最大流的值

m

是邊數(shù)每一輪O(m+n)

步–使用DFS查找路徑P20ts10uv201030新的流:20ts10v2010新的余圖:u201020ts10v20101010u20網(wǎng)絡(luò):

2/28/2025流vs.割(A,B)–圖G的割:A,B

是結(jié)點的劃分,s

在A中,t

在B中c(A,B)

=∑eoutA

c(e)=∑einB

c(e)是這個割的

容量性質(zhì):最小割等于最大流例:c(A,B)

=5020ts10uv20103020ts10uv201030AB

2/28/2025最大流vs.最小割對于任意包含s的集合A

我們執(zhí)行如下三個步驟:value(f)

=∑vinA∑eoutv

f(e)-∑vinA∑einv

f(e)value(f)

=fout(A)-fin(A)c(A,B)

fout(A)-fin(A)=value(f)

結(jié)論:Min-cut

value(f)例:

c(A,B)

=50and

fout(A)=3020ts10uv20103020ts10/10uv2010/1030/10AB

2/28/2025FF算法可以求得最大流設(shè)FF-算法在流f上停止：從s出發(fā)的DFS不包含t這意味著在余圖中DFS經(jīng)過的結(jié)點和其余結(jié)點之間割的容量是0因此這個割中的每條邊都被增廣流逆轉(zhuǎn)過，這意味著c(DFS,DFS’)=value(f)

根據(jù)Min-cut

value(f)可得到

f

最大20ts10uv20103020ts10v2010余圖:u2010DFSMin-cut

2/28/2025

7.3匹配問題

2/28/20257.3.1問題與應(yīng)用

2/28/2025匹配邊集合

MíE滿足不存在結(jié)點是多于一條邊的頂點極大匹配不存在e

?E滿足Mè{e}也是匹配最大匹配|M|最大的匹配完美匹配|M|=n/2:每個結(jié)點都是M中邊的頂點

2/28/2025有權(quán)版本每條邊有一個代價，尋找具有最小代價的匹配多項式時間可解，但是較難

2/28/2025相關(guān)問題給定一個圖G,尋找極大匹配:easy(貪心法)最大匹配多項式時間;noteasy.較容易的情況:二分圖完美匹配最大匹配的特例關(guān)于正則二分圖的定理和Schrijver算法

2/28/2025應(yīng)用人員指派教室指派任務(wù)安排賽程安排

2/28/20257.3.2二分圖匹配

2/28/2025二分圖匹配:使用最大流算法在二分圖中尋找最大匹配:建模為流問題并求解：確定算法找到基本流st容量1

2/28/2025同樣的技術(shù)對變體有效二分圖上最小代價完美匹配建模成最小代價流問題二分圖中的b-匹配函數(shù)b:V?

N.尋找邊集合M,其中每個頂點v在M中恰有b(v)條邊

2/28/20257.2.3Edmonds算法:無向圖中的匹配

2/28/2025M-增廣路徑M-增廣路徑:不匹配變化為在流的增廣階段

2/28/2025如下定理對于非二分圖也成立定理.令M是圖G中的一個匹配，M是最大匹配當(dāng)且僅當(dāng)其中沒有M-增廣路徑如果有M-增廣路徑，M不是最大匹配假設(shè)M不是最大匹配，令N是更大的匹配，考慮N*M=NèM–N?

M.N*M中每個結(jié)點的度是0,1,2:這是路徑和圈的集合.每個圈中的邊交替地在M和N中N*M中必然有一條路徑在N中的邊比M中多:有一條增廣路徑

2/28/2025Edmonds算法在多項式時間尋找圖的最大匹配

2/28/2025JackEdmonds

2/28/2025JackEdmonds

2/28/2025M-blossom定義M-交替跡:(可能非簡單的)路徑，其邊交替在M和非M中M-花M-交替跡，其起點是一個未匹配結(jié)點，終點是:

2/28/2025尋找M-增廣路徑或M-花–I令X

為未匹配結(jié)點的集合.令Y

為到X中的結(jié)點沒有邊在M中的結(jié)點集合建立有向圖D=(V,A)其中A={(u,v)|存在x

滿足{u,x}?E-M且{x,v}?M}.尋找X中的點到Y(jié)中的點長度至少為1的最短路徑P.(在D中BFS.)構(gòu)造P’:P之后加上X中的一條邊.P’是在兩個未匹配結(jié)點間的M增廣路徑

2/28/2025尋找M-增廣路徑或M-花––II兩種情況:P’是簡單路徑:它就是M增廣路徑P’不是簡單路徑.尋找P’的起點直到某個結(jié)點被訪問了兩次這是一個M-花:跡的圈部分不可能有偶數(shù)的結(jié)點，否則可以將其刪除以得到一個D中更短的跡

2/28/2025算法的idea從某個匹配M開始，尋找M增廣路