圖論及其應(yīng)用教學(xué)課件

1、圖論及其應(yīng)用第1頁，共101頁。圖論發(fā)展史 圖論在現(xiàn)代科學(xué)技術(shù)中有著重要的理論價值和廣泛的應(yīng)用背景，如：線性代數(shù)、密碼學(xué)、物理化學(xué)、網(wǎng)絡(luò)設(shè)計、計算機科學(xué)、信息科學(xué)、DNA的基因譜的確定和計數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中的優(yōu)化方法等都廣泛的應(yīng)用了圖論及其算法。 首先我們通過圖的發(fā)展過程來了解一下圖論所研究的內(nèi)容。 圖論起源于18世紀的一個游戲-俄羅斯的哥尼斯堡七橋問題。 （1736年 瑞士數(shù)學(xué)家歐拉圖論之父）第2頁，共101頁。A B D C 轉(zhuǎn)化 Euler1736年 B D CA 圖論中討論的圖 問題：是否能從A，B，C，D中的任一個開始走，通過每座橋恰好一次再回到起點？是否能從任意一個頂點開始，

2、通過每條邊恰好一次再回到起點？轉(zhuǎn)化包含兩個要素：對象（陸地）及對象間的二元關(guān)系（是否有橋連接）七 橋 問 題第3頁，共101頁。中國郵遞員問題1962年中國數(shù)學(xué)家管梅谷提出圖論中的“中國郵遞員問題”。問題：一個郵遞員從街區(qū)的某一點出發(fā)，經(jīng)過街區(qū)每條街道至少一次又回到原出發(fā)點，如何設(shè)計投遞路線，使總路程最短？第4頁，共101頁。 Hamilton問題源于1856年，英國數(shù)學(xué)家Hamilton設(shè)計了一個名為周游世界的游戲：他用一個正十二面體的二十個端點表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿著十二面體的棱通過每個端點恰好一次的行走路線。反映到圖論上就是判斷一個給定的圖是否存

3、在一條含所有頂點的回路。Hamilton問題第5頁，共101頁。 四色問題是世界近代三大數(shù)學(xué)難題之一。 四色問題的內(nèi)容是：任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。 它的提出來自英國。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色?！边@個現(xiàn)象能不能從數(shù)學(xué)上加以嚴格證明呢？四色問題第6頁，共101頁。 1872年，英國當(dāng)時最著名的數(shù)學(xué)家凱利正式向倫敦數(shù)學(xué)學(xué)會提出了這個問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題。 18781880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證

4、明四色猜想的論文，宣布證明了四色定理，大家都認為四色猜想從此也就解決了。 1890年，在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計算指出了肯普在證明上的漏洞。不久，泰勒的證明也被人們否定了。后來，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。第7頁，共101頁。 進入20世紀以來，科學(xué)家們對四色猜想的證明基本上是按照肯普的想法在進行。后來美國數(shù)學(xué)家富蘭克林于1939年證明了22國以下的地圖都可以用四色著色。1950年，有人從22國推進到35國。1960年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨后又推進到了50國。 1976年6月，美國伊利諾大學(xué)哈肯與

5、阿佩爾在兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明，轟動了世界。 然而，真正數(shù)學(xué)上的嚴格證明仍然沒有得到！數(shù)學(xué)家仍為此努力，并由此產(chǎn)生了多個不同的圖論分支。第8頁，共101頁。幾個事實：任意的6個人中，總有3個人互相認識或有3個人互不認 識。任意的9個人中，總有3個人互相認識或有4個人互不認 識。問題： 對任意的自然數(shù)k和t，是否存在一個最小的正整數(shù)r(k,t)，使得每個至少有r(k,t)個人的團體，總有k個人互相認識或有t個人互不認識。 拉姆瑟（F.P. Ramsey）在1930年證明了這個數(shù) r(k,t)是存在的，人們稱之為 Ramsey數(shù)。確定

6、其精確值是個公開的難題。Ramsey 問題第9頁，共101頁。Ramsey數(shù)R(p,q)第10頁，共101頁。Ramsey數(shù)的計算Ramsey數(shù)的計算是對人類智力的挑戰(zhàn)！例如R(4,5)=25 (1993年計算機11年的計算量)Erds用如下比喻說明其困難程度：一伙外星人入侵地球，要求一年內(nèi)求得R(5,5)，否則將滅絕人類！那么也許人類能集中所有計算機和專家來求出它以自保；但如果外星人問的是R(6,6) ，那么人類將別無選擇，只能拼死一戰(zhàn)了。第11頁，共101頁。Ramsey理論的哲理意義完全的無序是不可能的(Complete disorder is impossible)。任一足夠大的結(jié)構(gòu)中

7、必定包含一個給定大小的規(guī)則子結(jié)構(gòu)。無序無意的行為產(chǎn)生了有規(guī)律的后果，發(fā)人深思耐人尋味。古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。但根據(jù)Ramsey 定理，只要隨機分布的星星數(shù)目足夠多，就可以描繪出各種圖形的輪廓。1994年Statistical Science的一篇論文利用統(tǒng)計方法證明：圣經(jīng)隱藏了許多訊息，而這些訊息是有意安排的，絕非文字排列偶然造成的。 1997 年Michael Drosnin的The Bible Code 通過計算機掃讀圣經(jīng)中的304805個字母，發(fā)現(xiàn)圣經(jīng)密碼當(dāng)中傳達的訊息除了拉賓被刺殺外，還包括美國肯尼迪和林肯兩位總統(tǒng)，以及印度總理甘地遇刺的

8、事件，日本神戶、美國舊金山的大地震、世界末日與廣島原子彈轟炸等，種種過去與未來發(fā)生的大事件。Ramsey理論的哲理意義第12頁，共101頁。最精美的組合定理Rota：如果要求在組合學(xué)中僅舉出一個精美的定理，那么大多數(shù)組合學(xué)家會提名Ramsey定理。1984年Wolf獎得主Erds1997年Fulkerson獎得主Kim1998年Fields獎得主Gowers1999年Wolf獎得主Lovasz2003年Steele獎得主Graham2005年Gdel獎得主Alon2006年Fields獎得主Tao 均對Ramsey理論有杰出貢獻第13頁，共101頁。第14頁，共101頁。Ramsey理論的哲理

9、意義第15頁，共101頁。某村里有n 個男士與n 個女士，每個男士恰好認識 r 個女士，每個女士也恰好認識 r 個男士，問：在這個村中，能否做到：每個男士與其認識的女士結(jié)婚，每個女士也恰好與其認識的男士結(jié)婚?；橐銎ヅ涞?6頁，共101頁。圖論相關(guān)的交叉研究 代數(shù)圖論 拓撲圖論 化學(xué)圖論 算法圖論 隨機圖論 極值圖論 超圖以往數(shù)學(xué)家習(xí)慣將純數(shù)學(xué)應(yīng)用于其它學(xué)科，Gowers將圖論和組合數(shù)學(xué)中的Ramsey理論應(yīng)用于泛函分析的研究，獲得了1998年的Fields獎。第17頁，共101頁。內(nèi)容提要圖的基本概念圖的基本概念；二部圖及其性質(zhì)；圖的同構(gòu)；關(guān)聯(lián)矩陣與鄰接矩陣。路、圈與連通圖；最短路問題。樹及其

10、基本性質(zhì)；最小生成樹。圖的連通性割點、割邊和塊；邊連通與點連通；連通度；Whitney 定理；可靠通信網(wǎng)絡(luò)的設(shè)計。匹配問題匹配與最大匹配；完美匹配；二部圖的最大匹配。第18頁，共101頁。歐拉圖與哈密爾頓圖歐拉圖；中國郵遞員問題；哈密爾頓圖；旅行商問題。獨立集、覆蓋集與團點獨立集、點覆蓋集、邊覆蓋集與團的概念。圖的著色問題點著色；邊著色；平面圖；四色猜想。網(wǎng)絡(luò)流理論有向圖；網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念；最大流最小割定理；求最大流的標號算法；網(wǎng)絡(luò)流理論的應(yīng)用。第19頁，共101頁。主要參考書1 J.A. Bondy and U.S. Murty, Graph Theory with Applicati

11、ons, 1976 （GTM244, 2008）。2 B. Bollobas, Modern Graph Theory (現(xiàn)代圖論)，科學(xué)出版社，2001。3 王樹禾，圖論，科學(xué)出版社，2004。4 蔣長浩，圖論與網(wǎng)絡(luò)流，中國林業(yè)出版社，2001。5 徐俊明，圖論及其應(yīng)用，中國科技大學(xué)出版社，1998。第20頁，共101頁。第一章 圖和子圖1.1 圖和簡單圖1.2 子圖1.3 圖的同構(gòu)1.4 頂點的度1.5 路、圈和連通1.6 關(guān)聯(lián)矩陣和鄰接矩陣1.7 應(yīng)用： 最短路問題第21頁，共101頁。1.1 圖和簡單圖第22頁，共101頁。圖graph， 頂點vertex，邊edge圖的定義其中V(G

12、) 是非空的頂點集， E(G)是不與V(G)相交的邊集，而 是關(guān)聯(lián)函數(shù)，它使G的每條邊對應(yīng)于G 的無序頂點對。若e是一條邊，而u和v是使得 的頂點，則稱 e連接 u 和 v ；頂點 u 和 v 稱為 e 的端點。 一個圖 G 是指一個有序三元組 ，第23頁，共101頁。例 1此時， 定義為這便定義出一個圖。第24頁，共101頁。圖的圖形表示 通常，圖的頂點可用平面上的一個點來表示，邊可用平面上的線段來表示（直的或曲的），而邊僅在端點處相交， 這樣畫出的平面圖形稱為圖的圖形表示。第25頁，共101頁。G = (V, E) ，其中這便定義出一個圖。例2注：由于表示頂點的平面點的位置的任意性，同一個

13、圖可以畫出形狀迥異的很多圖示。例2中圖的另一個圖示：第26頁，共101頁。 圖的圖示直觀易懂，因此以后一般說到一個圖，我們總是畫出它的一個圖示來表示。 閱讀書P.2-3頁，理解平面圖和非平面圖，并且完成課后習(xí)題1.1.2。第27頁，共101頁。一些概念和術(shù)語：（1） 點與邊的關(guān)聯(lián)(incident)（2） 點與點的相鄰(adjacent)（3） 邊與邊的相鄰（4）（自）環(huán)(loop)、連桿(link)（5）重邊(parallel edge)（6）簡單圖(simple graph)（7）有限圖(finite graph)（8）平凡圖(trivial graph)和非平凡圖（9）空圖(empty

14、graph)和零圖（null graph)（10）圖的頂點數(shù)（圖的階order） 、邊數(shù)(size)第28頁，共101頁。1.2 圖的同構(gòu) 由前已知，同一個圖有不同形狀的圖示。反過來，兩個不同的圖也可以有形狀相同的圖示。比如： 可見 G1 和 G2 的頂點及邊之間都一一對應(yīng)，且連接關(guān)系完全相同，只是頂點和邊的名稱不同而已。這樣的兩個圖稱為是同構(gòu)的(isomorphic)。第29頁，共101頁。 從數(shù)學(xué)上看，同構(gòu)的兩個圖，其頂點間可建立一一對應(yīng)，邊之間也能建立一一對應(yīng)，且若一圖的兩點間有邊，則在另一圖中對應(yīng)的兩點間有對應(yīng)的邊。嚴格的數(shù)學(xué)定義如下。定義: 兩個圖G = (V (G), E(G) 與

15、H = (V (H), E(H) ，如果存在兩個一一映射： :V (G) V (H) ， : E(G) E(H) ，使得對任意e = (u,v) E(G) ，都有( (u), (v) E(H) 且 (e) = ( (u), (v) ，則稱圖G 與H 同構(gòu)。記為G H 。第30頁，共101頁。 G1、G2 在對應(yīng)viui (i=1,2,3,4,5,6)下是同構(gòu)的。例3x1x2y1x3y2y3v1v2v3v4v5v6第31頁，共101頁。畫出所有的階數(shù)不大于4，大小為3的所有非同構(gòu)簡單圖：第32頁，共101頁。畫出階數(shù)為5大小為3的所有非同構(gòu)簡單圖G1G2G3G4第33頁，共101頁。無標號的圖注

16、：判斷兩個圖是否同構(gòu)目前沒有好算法。第34頁，共101頁。一些特殊圖類：（1） 完全圖(complete graph)例 4K3K4K5K5第35頁，共101頁。（2） 二部圖 (bipartite graph)：若圖G 的頂點集可劃分為兩個非空子集X 和Y，使得任一條邊有一個端點在X 中，另一個端點在Y 中，則稱G 為二部圖（或偶圖），記為G (X U Y , E) ，(X ,Y ) 稱為G 的一個劃分（二分類）。第36頁，共101頁。K3,3 K2,4 （3）完全二部圖(complete bipartite graph)：在簡單二部圖G = (X U Y , E) 中，若X 的每個頂點與Y

17、的每個頂點有邊連接，則稱G 為完全二部圖；若| X |= m，|Y |= n ，則記此完全二部圖為K m , n。特別地， K 1 , n 稱為星。第37頁，共101頁。（4） r部圖、完全r部圖任意一個Vi 內(nèi)部都沒有邊。完全 r-部圖K(n1,n2,nr)：如果任意Vi中的所有點與Vj中的所有點都相連。一個簡單圖叫作r-部圖, 如果第38頁，共101頁。（6） G的補圖(complement)： 設(shè)G 是一個圖，以V (G) 為頂點集，以(x, y) | (x, y) E(G)為邊集的圖稱為G 的補圖，記為GC。第39頁，共101頁。1.3 子圖(1) 子圖(subgraph)： 如果V

18、(H) V (G) 且 E(H) E(G) ，則稱圖 H 是G 的子圖，記為 H G 。(2) 生成子圖(spanning subgraph): 若H 是G 的子圖且V(H)=V(G)，則稱H 是G 的生成子圖。(3) 點導(dǎo)出子圖(induced subgraph)： 設(shè)V V (G) ，以V 為頂點集，以兩端點均在 V 中的邊的全體為邊集所組成的子圖，稱為 G 的由頂點集 V 導(dǎo)出的子圖，簡稱為 G 的點導(dǎo)出子圖，記為GV 。第40頁，共101頁。(4) 邊導(dǎo)出子圖(edge-induced subgraph)：設(shè)E E(G) ，以 E 為邊集，以 E 中邊的端點全體為頂點集所組成的子圖，稱

19、為G 的由邊集 E 導(dǎo)出的子圖，簡稱為 G 的邊導(dǎo)出子圖，記為 GE。(5) 定義G - V (6) 定義G - E (7) 基礎(chǔ)簡單圖：壓縮平行邊，去掉環(huán)基礎(chǔ)簡單圖第41頁，共101頁。例6第42頁，共101頁。v2v5v3v4v1Ge1e8e7e6e5e4e3e2v2v3v4v1e1e8e6e5e4v2v5v4v1e1e7e3e2v2v5v4e7e6e5e3v2v5v3v4v1e1e7e6e4e3例7第43頁，共101頁。子圖的運算：第44頁，共101頁。G2G1G2G1圖的運算：第45頁，共101頁。G2G1第46頁，共101頁。1.4 頂點的度頂點v 的度(degree)：d(v) =

20、 頂點v 所關(guān)聯(lián)的邊的數(shù)目（環(huán)邊計兩次）。圖G 的最大度： (G) = maxd G (v) | v V (G)圖G 的最小度： (G) = mind G (v) | v V (G)正則圖(regular graph)：每個頂點的度都相等的圖。度序列：見習(xí)題1.5.5孤立點： d(v) =0 第47頁，共101頁。定理 1.1證明：按每個頂點的度來計數(shù)邊，每條邊恰數(shù)了兩次。推論1.1 任何圖中，奇度頂點的個數(shù)總是偶數(shù)（包括0）。設(shè)V1 和 V2 分別是G中奇點集和偶點集，由證明：而 是偶數(shù)，所以 是偶數(shù)，故 是偶數(shù)。定理1.1知，是偶數(shù)，第48頁，共101頁。例 晚會上大家握手言歡，試證握過奇

21、次手的人數(shù)是偶數(shù)。證明：以參加晚會的人為頂點集構(gòu)造一個圖G，當(dāng)且僅當(dāng)二人握手時，在相應(yīng)的兩頂點之間連一條邊。于是每人握手的次數(shù)即為G的相應(yīng)頂點的度數(shù)。由推論1.1，得證。第49頁，共101頁。例 空間中不可能有這樣的多面體存在，它的面數(shù)是奇數(shù)，而且每個面由奇數(shù)條線段圍成證明：如果有這樣的多面體，以此多面體的面集合為頂點集構(gòu)造一個圖G，當(dāng)且僅當(dāng)兩個面有公共邊界時，在相應(yīng)的兩頂點之間連一條邊。于是G有奇數(shù)個頂點，且每個頂點都為奇點，與定理1.1矛盾。故這種多面體不存在。第50頁，共101頁。1.5 路、圈和連通(1) 途徑(walk)：圖G 中一個頂點和邊交替出現(xiàn)的有限非 空序列注1：起點(v0)

22、；終點(vk) ；內(nèi)部頂點（內(nèi)點）；長(k)注2：簡單圖中的途徑可以用頂點來表示若在非簡單圖中，則表示通過這些頂點的任意途徑。注3： W-1； W1W2; 注4： W的(vi,vj)節(jié)路和圈有關(guān)概念第51頁，共101頁。(2) 跡(trail)：各邊相異的途徑。(3) 路(path): 各頂點相異的跡（P_k)。第52頁，共101頁。(4) 閉途徑(closed walk)：具有正的長且起點和終點相同的途徑。 閉跡(closed trail) 也稱為回路（circuit）。(5) 圈(cycle): 各頂點相異的閉跡。 k圈（C_k)；3圈常稱為三角形 圖G 中長為奇數(shù)和偶數(shù)的圈分別稱為奇圈(

23、odd cycle)和偶圈(even cycle)。 圖G 的圍長(girth) 是指G 中最短圈的長；若G沒有圈，則定義為無窮大。 最長圈的長稱為圖G 的周長(circumference)。第53頁，共101頁。v2v5v3v4v1Ge1e8e7e6e5e4e3e2途徑長為 5。長為 5。跡 長為 3。試著尋找其它的 (v1, v3)-路?路例8第54頁，共101頁。圖 K4, E3, P4, C4 and C5 第55頁，共101頁。圖的分支（component）：若圖G 的頂點集V(G)可劃分為若干非空子集V 1,V 2, ,V ，使得兩頂點屬于同一子集當(dāng)且僅當(dāng)它們在G 中連通，則稱每個

24、子圖GV i 為圖G 的一個分支（ i = 1,2, ）。連通性的概念圖中兩點的連通：如果在圖G 中存在(u，v) 路，則稱頂點u，v 在圖G 中連通。連通圖（connected graph）：圖G 中任二頂點都連通。第56頁，共101頁。 非連通圖，三個分支v1v2v3v4e2e3e4e5e6e7 連通圖注：（1）圖G 的分支是G 的一個極大連通子圖。 （2）圖G 連通當(dāng)且僅當(dāng)1。第57頁，共101頁。有四個分支的不連通圖例第58頁，共101頁。注：（1）若在G中頂點 x 和 y 是連通的 ，則 x 和 y 之間 的距離(distance) d G(x, y) 是G 中最短 (x, y) 路

25、的長；若沒有路連接 x 和 y，則定義d G(x, y)為無窮大。（2）圖G 的直徑(diameter): D = maxd G (x, y) | x, y V (G) 。第59頁，共101頁。定理1.2 一個圖是二部圖當(dāng)且僅當(dāng)它不含奇圈。證明： 必要性：設(shè) C = v 0 v 1 v k v 0 是二部圖G = (X U Y , E) 的一個圈。不妨設(shè)v 0 X ，由二部圖的定義知v 1 Y ，v 2 X ， ，一般地，v 2 i X ，v 2 i +1 Y ，（ i = 0,1,）。又因v 0 X ，故v k Y ，因而k 是奇數(shù)。注意到圈C 上共有k + 1條邊，因此是偶圈。偶圖的判定條

26、件第60頁，共101頁。充分性：顯然對連通圖證明即可。設(shè)G 不含奇圈。任取 u V (G) ，令X = v V (G) | d(u, v)是奇數(shù)，Y = v V (G) | d(u, v)是偶數(shù)。現(xiàn)證（X,Y）是G的一個二分類。任取一條邊 e = v1v2，欲證, v1 ，v2分屬于X 和Y。 設(shè)P，Q 分別是u 到 v1 ，v2 的最短路。Puv1v2（1）如果 P = Q + v 2 v 1或 Q = P + v 1 v 2 ，則 v 1, v 2到u 的距離奇偶性相反， v 1 , v 2分屬于X和Y。第61頁，共101頁。 假如P，Q 的奇偶性相同，則P 的(u , v 1 ) 節(jié)和Q

27、 的(u , v 2 ) 節(jié)奇偶性相同，它們與邊e 構(gòu)成一個奇圈，與定理條件矛盾?？梢奝，Q 的奇偶性不同，從而 v 1, v 2分屬于X 和Y。證畢。（2）否則，設(shè)u是P 與Q 的最后一個公共頂點，因P 的(u, u) 節(jié)和Q 的(u, u) 節(jié)都是最短的(u,u) 路，故長相等。Puuv1Qv2Puv1Puv1Puv1Puv1Puv1v1第62頁，共101頁。由定理 1.2可知圖 (a) 所示的圖不是二部圖，因為它包含一個三角形；圖 (b) 所示的圖是一個二部圖，它不含長為奇數(shù)的圈。第63頁，共101頁。證明：設(shè)P = v0v1 v k 為G 中的一條最長路 。因 d (v 0) 2 ，故

28、除 v 1外，存在頂點 v 與 v 0相鄰。若v V(P) ，則得到比 P 更長的路，這與 P 的取法矛盾。因此必有 v V(P) ，從而 G 包含圈。證畢。例9 設(shè)G 是一個簡單圖，若 (G) 2 ，則G 包含圈。v0v1v2vk第64頁，共101頁。例10 設(shè) G 是簡單圖，若 (G) 3 ，則 G 包含偶圈。v0v1v2vkvivj第65頁，共101頁。證明：設(shè) P =v0v1 v k 是G 的最長路。因為 d (v 0) 3 ， 所以存在兩個與 v 1 相異的頂點 v, v 與 v 0 相鄰。v, v 必都在路 P 上，否則會得到比 P 更長的路。不妨設(shè) v = v i , v = v

29、 j , (i 0。（w = 0時，可令兩端點重合；第81頁，共101頁。 若路 P = u 0 u 1 u k 1 u k 是從 u 0到 u k的最短路，則 P = u 0 u 1 u k 1必 u 0到u k 1的最短路。基于這一原理，算法由近及遠地逐次求出u 0到其它各點的最短路。二、Dijkstra 算法1. 算法思想下面通過例子說明具體做法。第82頁，共101頁。（1）令 ， ，求 到 中最近點的最短路，結(jié)果找到 。（2）令: ，求 到 中最近點的最短路。此時除了考慮 到 的直接連邊外，還要考慮 通過 向 的連邊，即選取 中第83頁，共101頁。一點 ，使得結(jié)果找到u 2 。一般地

30、，若 以及相應(yīng)的最短路已找到。則可應(yīng)用(*)式來選取新的 ，獲得 到 的最短路。第84頁，共101頁。例1472122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u0195第85頁，共101頁。 1) 置 ，對 ， ， 且 . 2) 對每個 ，用代替 ，計算 ，并把達到這個最小值的一個頂點記為 ，置 3) 若 ，則停止；若 ，則用 i+1 代替i，并轉(zhuǎn)2).

31、2算法實現(xiàn)標號法第86頁，共101頁。計算實例：求連接 vs、vt 的最短路.開始，給vs以 P 標號，P(vs)=0,其余各點給 T 標號 T(vi)=+.227414731555vsv2v1vtv4v5v3Step 1: 迭代 1 Dijkstra算法基本步驟：例15第87頁，共101頁。 若 vi 為剛得到 P 標號的點,考慮這樣的點 vj : (vi ,vj)E 且vj 為 T 標號。227414731555vsv2v1vtv4v5v3Step 2: 對vj的T 標號進行如下更改T(vj)=minT(vj),P(vi)+wij245迭代 1 考察vs , T(v2)=minT(v2),

32、P(vs)+ws2= min+,0+5=5T(v1)=minT(v1),P(vs)+ws1= min+,0+2=2第88頁，共101頁。 比較所有具有 T 標號的點，把最小者改為P 標號，227414731555vsv2v1vtv4v5v3Step 3: 245即 P(vi)=minT(vi).當(dāng)存在兩個以上最小者時,可同時改為P 標號。若全部點為P標號,則停止。否則用vi代替vi轉(zhuǎn)step 2.-2迭代 1 全部T標號中,T(v1)最小,令P(v1)=2,記錄路徑(vs ,v1).第89頁，共101頁。227414731555vsv2v1vtv4v5v394 若 vi 為剛得到 P 標號的點

33、,考慮這樣的點 vj : (vi ,vj)E 且vj 為 T 標號。Step 2: 對vj的T 標號進行如下更改T(vj)=minT(vj),P(vi)+wij迭代 2 考察v1 , T(v4)=minT(v4),P(v1)+w14= min+,2+7=9T(v2)=minT(v2),P(v1)+w12= min5,2+2=4第90頁，共101頁。227414731555vsv2v1vtv4v5v344迭代 2 比較所有具有 T 標號的點，把最小者改為P 標號，Step 3: 即 P(vi)=minT(vi).-全部 T 標號中,T(v2),T(v3)最小,令P(v2)=4, P(v3)=4,記錄路徑(v1 ,v2