第五部分圖論第二部分教學課件

第五章圖論

(第二部分)1.通路2.圖的連通性3.賦權(quán)圖的最短通路1賦權(quán)圖與邊的權(quán)[定義]權(quán)在圖的點或者邊上標明的信息(數(shù)量)稱為權(quán)。邊e的權(quán)記為W(e)；如果用兩個端點的序列(u,v)表示邊，則邊(u,v)的權(quán)記為W(u,v)。規(guī)定：

(1)W(uu)=0，若(u,u)E(G),(2)W(uv)=∞,若(u,v)E(G)。[定義]賦權(quán)圖頂點或邊含有權(quán)的圖稱為賦權(quán)圖。賦權(quán)圖可以是有向圖或者無向圖。2例:賦權(quán)圖邊權(quán)值例W(a,b)=5，W(a,a)=0，W(b,d)=∞，W(a,d)=8

abcd51248203最短通路[定義]最短通路在一個邊賦權(quán)的圖G中，從u到v的所有通路中，邊權(quán)值和最小的通路，稱為u到v的最短通路（最短路徑），最短通路的邊權(quán)和稱為u到v的距離。

兩點間的最短通路必為基本通路。

4最短通路例515217420268AFBCDE5枚舉法求最短通路

求a到c的最短通路a到c的基本通路有：(a,b,c)邊權(quán)和為5+4=9;(a,c)邊權(quán)和為12;(a,d,c)邊權(quán)和為8+20=28。最短路為：abc，因此a到c的距離為9abcd51248206狄克斯特洛(Dijkstra)算法求圖G=(V,E)中從結(jié)點a到結(jié)點z的最短通路。

基本思想－動態(tài)規(guī)劃法

(1)

求出以a為起點，V-{a}中的點為終點的最小最短通路P1；設P1終點為t1;

若t1=z，則P1為a到z的最短通路；否則，執(zhí)行(2)(2)求出以a為起點，V-{a,t1}中的點為終點的最小最短通路P2；設P2終點為t2；若t2=z，則P2為a到z的最短通路；否則，執(zhí)行(3)(3)求出以a為起點，V-{a,t1,t2}中的點為終點的最小最短通路P3；設P3終點為t3；若t3=z，則P3為a到z的最短通路；否則，執(zhí)行(4)(4)依此類推，直到求得的第k條最短通路Pk；終點為z。7狄克斯特洛算法：相關(guān)定義設G=(V,E)，求G中a到z的最短通路。[定義]目標集目標集T是滿足以下條件的集合：(1)TV(2)zT,z是最短通路的終點(3)aT,a是最短通路的起點[定義]指標設t1

T，由a到t1但不通過目標集T中其它頂點的所有通路中，各邊的權(quán)之和的最小者，稱為t1關(guān)于目標集T的指標，記作DT(t1).設T={c,e,f,g,z},求DT(c).a到c但不通過目標集T中其它頂點的所有基本通路:(a,b,c):各邊權(quán)之和:1+2=

3(a,c):各邊權(quán)之和:4(a,d,c):各邊權(quán)之和:4+3=7∴DT(c)=3badecfgz1442396357143TG8狄克斯特洛算法：原理[原理]:

設目標集T={t1,t2,……,tn},其中t1為T中指標最小的點，即：DT(t1)=

min{DT(t1),DT(t2),……,DT(tn)}(1)始點a到t1的最短通路的邊權(quán)和就是DT(t1)(2)對任意2

in，a到t1的最短通路

a到ti的最短通路設T={e,f,g,z},已求得DT(e)=9;DT(f)=6;DT(g)=8;DT(z)=∞;

在T的所有結(jié)點中，a到f的最短通路最小并且a到f的最短通路的邊權(quán)值和為DT(f)=6。badecfgz1442396357143TG9狄克斯特洛算法：原理證明（1）

證明：

(1)(反證法)

假設a到t1的最短通路的權(quán)和不是DT(t1).

已知DT(t1)是從a到t1但不通過T中其它頂點的通路中權(quán)和最小者，所以如果存在另一條權(quán)和小于DT(t1)的新通路，則該通路一定至少通過T中一個其它頂點。10狄克斯特洛算法：原理證明（2）證明(續(xù))：設新通路的邊權(quán)和為dnew，則

dnew

<DT(t1)

設t2是新通路上經(jīng)過T中的第一個頂點，則：

dnew

=DT(t2)+W(t2t1)>

DT(t1)

其中w(t2t1)表示新通路中t2到t1的各邊權(quán)之和。

這與“dnew

<DT(t1)”矛盾?！郺到t1的最短通路的權(quán)和只能是DT(t1).aTt1t211狄克斯特洛算法：原理證明（2）證明(續(xù))：

(2)(反證法)

假設存在ti(i2)，使得a到ti的最短通路小于a到t1的最短通路。設該通路為P，邊權(quán)值和為d。則d<DT(t1)且d<DT(ti)。已知DT(ti)是從a到ti但不通過T中其它頂點的通路中權(quán)和最小者，則P一定至少通過T中一個其它頂點。設t2是P經(jīng)過T中的第一個頂點，則：

d=DT(t2)+W(t2ti)>

DT(t1)

其中w(t2t1)表示P中t2到ti的各邊權(quán)之和。

這與“d<DT(t1)”矛盾?！?2)得證。aTtit212狄克斯特洛算法求圖G=(V,E)中a到z的最短通路。步驟：（1）令初始目標集T1＝V-{a}。求T1中指標最小的結(jié)點，設為t1。若t1=z，則DT1(t1)為a到z的最短通路邊權(quán)和。否則，執(zhí)行（2）（2）令T2=T1-{t1},求T2中指標最小的結(jié)點，設為t2。若t2=z,則DT2(t2)為a到z最短通路邊權(quán)和。否則，執(zhí)行(3)

（3）依此類推，直到求得某個目標集Tk，使得z為Tk中指標最小的結(jié)點，則DTk(z)為a到z的最短通路的邊權(quán)和。關(guān)鍵：求結(jié)點關(guān)于目標集Ti的指標。13采用“遞推”的方法求目標集中的指標已知當前目標集為Tm={tm,tm+1,…,tn}，且DTm(ti)是ti關(guān)于目標集T的指標，tm是最小指標點。要求新的目標集Tm+1=Tm

－{tm}中任意點ti的指標可用下公式求得：tmtntm+1…tmTmTm+1…tm-1t2t1a…注：當tm與ti不鄰接時，W(tm,ti)＝∞14狄克斯特洛算法：執(zhí)行步驟求圖G=(V,E)中a到z的最短通路。[算法]執(zhí)行步驟：(1)將目標集設置為：T=V–{a}(2)對任意vT，令DT(v)=W(a,v)；(3)

將T中指標值最小的點t從T中剔除，即令T＝T－{t}；。(4)若t=z，則DT(z)為a到z的最短路徑權(quán)值，算法結(jié)束。否則（即t≠z），執(zhí)行以下操作：對所有vT，令DT(v)=min(DT(v),DT(t)+W(t,v))；重復(3).算法執(zhí)行結(jié)束后，DT(z)就是從a到z的最短通路的權(quán)和。15狄克斯特洛算法求最短通路舉例例：求下圖中從始點a到終點z的最短通路。16首先，取初始目標集T1＝{b,c,d,e,f,g,z}。易見:DT1(b)=1（通路：ab）DT1(c)=4（通路：ac）DT1(d)=4（通路：ad）DT1(e)=DT1(f)=DT1(g)=DT1(z)=∞（無通路）T1比較各點的指標可知，b是最小的指標點，b的指標對應的通路為ab。17c是指標最小的點。T2通路：abc通路：ad通路：abe通路：無通路：無通路：無a到c的最短通路為：abc,邊權(quán)和為DT2(c)=3

DT1(b)=1（通路：ab）DT1(c)=4（通路：ac）DT1(d)=4（通路：ad）DT1(e)=DT1(f)=DT1(g)=DT1(z)=∞（無通路）18通路：ad通路：abce通路：abcf通路：abcg通路：無比較T3中各點指標可知：d的指標最小，故DT3(d)=4是a到d的最短路徑長度，ad是a到d的最短路徑T319令T4＝T3－zjo9k1m={e,f,g,z}T4中各結(jié)點的指標為：

通路：abce通路：abcf通路：abcg通路：無比較T4中各點指標可知：f的指標最小，故DT4(f)=6是a到f的最短路徑長度，abcf是a到f的最短路徑。T420比較T4中各點指標可知：e和g的指標相同，且最小，故可選其中一個，DT5(e)=8是a到e的最短路徑長度，abcfe是a到e的最短路徑。令T5＝T4－{f}={e,g,z}T5中各結(jié)點的指標為：

通路：abcfeT5通路：abcg通路：abcg21令T6＝T5－{e}={g,z}T6中各結(jié)點的指標為：

T6比較T6中各點指標可知：f的指標最小，故DT6(g)=6是a到g的最短路徑長度，abcg是a到g的最短路徑。通路：abcg通路：abcfez22令T7＝T6－{g}={z}

T7中各結(jié)點的指標為：

故a到z的最短通路邊權(quán)和為DT7(z)=9，通路為abcfez通路：abcfezT723求最短通路的表格表示法步驟：

(1)先把T1=V–{a}中各點寫在第一行上，把各點的指標寫在第二行上然后圈出其中最小指標點。bcdefgz44∞∞∞∞1①T124bcdefgz①44∞∞∞∞

(2)在第三行上，相應地寫上T2=T1－中各點的指標。在求T2中點t的指標時，利用公式求出T2中各點的指標后，圈出最小指標點。bcdefgz①44∞∞∞∞410∞∞∞3③T2T1T125在第四行上，相應地寫上T3=T2－{c}中各點的指標。利用公式：求出T3的指標以后，圈出其中最小指標的點。bcdefgz①44∞∞∞∞③410∞∞∞968∞4④T2T1T326采用同樣的方法，可得完整的表格如下：bcdefgz①44∞∞∞∞③410∞∞∞④968∞9⑥8∞⑧810⑧9⑨T1T2T3T4T5T6T727逆向檢查法，找最短通路28bcdefgz①44∞∞∞∞③410∞∞∞④968∞9⑥8∞⑧810⑧9⑨e→zf→e→zc→f→e→zb→c→f→e→z所以最短通路為：a→b→c→f→e→zT1T2T3T4T5T6T729例：采用表格表示法求下圖中a點到z點的最短路徑330bcdefghz56∞∞∞∞①1∞T13表格求解步驟（1）31表格求解步驟（2）69∞∞∞④4∞T23bcdefghz①56∞∞∞∞∞T132表格求解步驟（3）698∞∞⑥7T23bcdefghz①56∞∞∞∞∞④69∞∞∞∞T1T333