數(shù)學(xué)建模圖論模型學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)學(xué)建模圖論數(shù)學(xué)建模圖論(t ln)模型模型第一頁(yè)，共75頁(yè)。第1頁(yè)/共74頁(yè)第二頁(yè)，共75頁(yè)。 1. 幾個(gè)(j )引例2. 基本概念 3. 最短路(dunl)問(wèn)題及算法 4. 簡(jiǎn)單(jindn)應(yīng)用 第2頁(yè)/共74頁(yè)第三頁(yè)，共75頁(yè)。ABCD哥尼斯堡七橋示意圖問(wèn)題1:七橋問(wèn)題 能否從任一陸地出發(fā)通過(guò)(tnggu)每座橋恰好一次而回到出發(fā)點(diǎn)？1. 幾個(gè)(j )引例第3頁(yè)/共74頁(yè)第四頁(yè)，共75頁(yè)。七橋問(wèn)題(wnt)模擬圖ABDC歐拉指出：如果(rgu)每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過(guò)每座橋恰好一次而回到出發(fā)地。第4頁(yè)/共74頁(yè)第五頁(yè)，共75頁(yè)。 萊昂哈德歐拉(L

2、eonhard Euler，) 瑞士的數(shù)學(xué)家和物理學(xué)家(w l xu ji)。他被稱為歷史上最偉大的兩位數(shù)學(xué)家之一（另一位是卡爾弗里德里克高斯）。歐拉出生于瑞士，在那里受教育。他是一位數(shù)學(xué)神童。作為數(shù)學(xué)教授，他先后任教于圣彼得堡(1727-1741)和柏林，爾后再返圣彼得堡(1766)。 歐拉的一生很虔誠(chéng)。然而，那個(gè)廣泛流傳的傳說(shuō)卻不是真的。傳說(shuō)中說(shuō)到，歐拉在葉卡捷琳娜二世的宮廷里，挑戰(zhàn)德尼狄德羅：“先生，(a+b)n/n = x；所以上帝存在，這是回答！” 歐拉的離世也很特別：據(jù)說(shuō)當(dāng)時(shí)正是下午茶時(shí)間，正在逗孫兒玩的時(shí)候，被一塊蛋糕卡在喉頭窒息而死。 歐拉是第一個(gè)使用“函數(shù)”一詞來(lái)描述包含各種

3、參數(shù)的表達(dá)式的人，例如：y = F(x) (函數(shù)的定義由萊布尼茲在1694年給出)。他是把微積分應(yīng)用于物理學(xué)的先驅(qū)者之一。歐拉是有史以來(lái)最多產(chǎn)的數(shù)學(xué)家，他的全集共計(jì)75卷。歐拉實(shí)際上支配了18世紀(jì)的數(shù)學(xué)，對(duì)于當(dāng)時(shí)新發(fā)明的微積分，他推導(dǎo)出了很多結(jié)果。在他生命的最后7年中，歐拉的雙目完全失明，盡管如此，他還是以驚人的速度產(chǎn)出了生平一半的著作。 小行星歐拉2002是為了紀(jì)念歐拉而命名的。萊昂哈德歐拉 第5頁(yè)/共74頁(yè)第六頁(yè)，共75頁(yè)。問(wèn)題2:哈密頓圈（環(huán)球旅行游戲）十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次(yc)經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？第6頁(yè)/共74頁(yè)

4、第七頁(yè)，共75頁(yè)。問(wèn)題(wnt)3:四色問(wèn)題(wnt) 對(duì)任何(rnh)一張地圖進(jìn)行著色，兩個(gè)共同邊界的國(guó)家染不同的顏色，則只需要四種顏色就夠了。德摩爾根致哈密頓的信（1852年10月23日） 我的一位學(xué)生今天請(qǐng)我解釋一個(gè)我過(guò)去不知道，現(xiàn)在仍不甚了了的事實(shí)。他說(shuō)如果任意劃分一個(gè)圖形并給各部分著上顏色，使任何具有(jyu)公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）。第7頁(yè)/共74頁(yè)第八頁(yè)，共75頁(yè)。問(wèn)題4(關(guān)鍵路徑問(wèn)題) 一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺(tái)機(jī)床,一架電視機(jī), 都要包括許多工序.這些工序相互約束,只有在某些工序完

5、成之后, 一個(gè)工序才能開(kāi)始. 即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知(y zh)的, 而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間. 這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目, 影響工程進(jìn)度的要害工序是哪幾個(gè)？ 第8頁(yè)/共74頁(yè)第九頁(yè)，共75頁(yè)。1) 圖的概念(ginin)2) 賦權(quán)圖與子圖3) 圖的矩陣(j zhn)表示4) 圖的頂點(diǎn)度5) 路和連通第9頁(yè)/共74頁(yè)第十頁(yè)，共75頁(yè)。 定義 一個(gè)(y )圖G是指一個(gè)(y )二元組(V(G),E(G)，其中: 其中元素(yun s)稱為圖G的頂點(diǎn).組成的集合，即稱為邊集,其中元素稱為邊.),(jivv 定義

6、 圖G的階是指圖的頂點(diǎn)數(shù)|V(G)|, 用來(lái)表示；v圖的邊的數(shù)目|E(G)|用來(lái)表示. 也用來(lái)表示邊jivv).,(jivv,)(21vvvGV是非空有限集，稱為頂點(diǎn)集，1)2) E(G)是頂點(diǎn)集V(G)中的無(wú)序或有序的元素偶對(duì)).,(EVG )(),(GEGVG 表示圖，簡(jiǎn)記 用第10頁(yè)/共74頁(yè)第十一頁(yè)，共75頁(yè)。 其為有限圖. 只有一個(gè)頂點(diǎn)的圖稱為平凡(pngfn)圖，其他的 所有(suyu)圖都稱為非平凡圖.第11頁(yè)/共74頁(yè)第十二頁(yè)，共75頁(yè)。,稱G為有向),(jivv邊 為無(wú)向邊，稱e連接(linji) 和 ，頂點(diǎn) 和 稱圖. 稱邊為有向邊或弧,稱),(jivve 是從),(jiv

7、ve iv連接(linji)jv，稱 為e的尾，稱 為e的頭. ivjv 若圖G中的邊均為無(wú)序偶對(duì) ，稱G為無(wú)向圖.稱jivv為e的端點(diǎn). jivve ivjvivjv 既有無(wú)向邊又有有向邊的圖稱為混合圖.第12頁(yè)/共74頁(yè)第十三頁(yè)，共75頁(yè)。1) 邊和它的兩端點(diǎn)稱為互相(h xing)關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個(gè)(lin )端點(diǎn)稱為相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰的邊. 3) 端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)， 端點(diǎn)不相同的邊稱為連桿.4) 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為重邊5) 既沒(méi)有環(huán)也沒(méi)有重邊的圖，稱為簡(jiǎn)單圖 第13頁(yè)/共74頁(yè)第十四頁(yè)，共75頁(yè)。 常用(c

8、hn yn)術(shù)語(yǔ)6) 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單(jindn)圖,稱為完全圖. 記為Kv. 7) 若 ， ，且X 中任意(rny)兩頂點(diǎn)不YXGV)(YX ， 相鄰，Y 中任意兩頂點(diǎn)不相鄰，則稱為二部圖或 偶圖；若X中每一頂點(diǎn)皆與Y 中一切頂點(diǎn)相鄰,稱為完全二部圖或完全偶圖,記為 (m=|X|,n=|Y|)nmK,8) 圖 叫做星.nK, 1:X1x2x3x:Y1y2y3y4y二部圖6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K第14頁(yè)/共74頁(yè)第十五頁(yè)，共75頁(yè)。)(),(GEGVG 一個(gè)(y )實(shí)數(shù)w(e)，稱w(e)為邊e的權(quán)，G 連同邊上的權(quán)稱為(chn wi)賦權(quán)圖.

9、定義 設(shè) 和 是兩個(gè)圖.),(EVG ),(EVG 1) 若 ,稱 是 的一個(gè)子圖,記 EEVV,GG.GG 2) 若 ， ，則稱 是 的生成子圖.VV EE GG 3) 若 ，且 ，以 為頂點(diǎn)集，以兩端點(diǎn) VV VV 均在 中的邊的全體為邊集的圖 的子圖，稱 VG 為 的由 導(dǎo)出的子圖，記為 .GVVG4) 若 ，且 ，以 為邊集，以 的端點(diǎn)EE EEE 集為頂點(diǎn)集的圖 的子圖，稱為 的由 導(dǎo)出的GGE 邊導(dǎo)出的子圖，記為 . EG第15頁(yè)/共74頁(yè)第十六頁(yè)，共75頁(yè)。,321vvvG,6543eeeeG 3) 若 ，且 ，以 為頂點(diǎn)集，以兩端點(diǎn) VV VV 均在 中的邊的全體為邊集的圖 的

10、子圖，稱 VG4) 若 ，且 ，以 為邊集，以 的端點(diǎn)EE EEE 集為頂點(diǎn)集的圖 的子圖，稱為 的由 導(dǎo)出的GGE 邊導(dǎo)出的子圖，記為 . EGGVVG 為 的由 導(dǎo)出的子圖，記為 .第16頁(yè)/共74頁(yè)第十七頁(yè)，共75頁(yè)。鄰接矩陣:1) 對(duì)無(wú)向圖 ，其鄰接矩陣 ，其中： G)(ijaA., 0, 1不相鄰與若相鄰與若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假設(shè)(jish)圖為簡(jiǎn)單圖).第17頁(yè)/共74頁(yè)第十八頁(yè)，共75頁(yè)。2) 對(duì)有向圖 ,其鄰接矩陣 ,其中： )(ijaA),(EVG .),(, 0,),(,

11、 1EvvEvvajijiij若若432143210100001000001110uuuuAuuuu第18頁(yè)/共74頁(yè)第十九頁(yè)，共75頁(yè)。其中(qzhng)：3) 對(duì)有向賦權(quán)圖 , 其鄰接矩陣 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，為其權(quán)，且若43214321040608730uuuuAuuuu對(duì)于(duy)無(wú)向賦權(quán)圖的鄰接矩陣可類似定義. 第19頁(yè)/共74頁(yè)第二十頁(yè)，共75頁(yè)。1) 對(duì)無(wú)向圖 ，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM其中(qzhng)：., 0, 1不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiijevevm5432154321100

12、0001000111100010100011vvvvvMeeeee第20頁(yè)/共74頁(yè)第二十一頁(yè)，共75頁(yè)。2) 對(duì)有向圖 ，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM., 0, 1, 1的頭與尾不是若的頭是若的尾是若jijijiijevevevm其中(qzhng)：43215432111000101100001101101uuuuMeeeee第21頁(yè)/共74頁(yè)第二十二頁(yè)，共75頁(yè)。 鄰接矩陣 A = (aij )nn , EvvEvvajijiij, 0, 1例 寫出右圖的鄰接矩陣0101100101001010A解：第22頁(yè)/共74頁(yè)第二十三頁(yè)，共75頁(yè)。 權(quán)矩陣(j zhn)A = (aij

13、 ) nn EvvjiEvvvvFajijijiij , , 0 ,例 寫出右圖的權(quán)矩陣(j zhn)：05420370860A解：圖的矩陣(j zhn)表示第23頁(yè)/共74頁(yè)第二十四頁(yè)，共75頁(yè)。定義(dngy) 1) 在無(wú)向圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為(chn wi)頂點(diǎn)v的度或次數(shù)，記為d(v)或 dG(v).稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為偶點(diǎn).2) 在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn) v的出度，記為d+(v)，從頂點(diǎn)v引入的邊的數(shù)目稱為 v的入度，記為d -(v). 稱d(v)= d+(v)+d -(v)為頂點(diǎn)v的 度或次數(shù)定理.2)(Vvvd的個(gè)

14、數(shù)為偶數(shù)推論 任何圖中奇點(diǎn)4)(1vd1)(3ud2)(3ud3)(3ud第24頁(yè)/共74頁(yè)第二十五頁(yè)，共75頁(yè)。 定義(dngy)1) 無(wú)向圖G的一條途徑（或通道或鏈）是指一個(gè)有限非空序列 ，它的項(xiàng)交替kkveevevW2110 地為頂點(diǎn)和邊，使得對(duì) ， 的端點(diǎn)是 和 ,ki 1ie1iviv稱W是從 到 的一條途徑，或一條 途徑. 整0vkv),(0kvv數(shù)k稱為W的長(zhǎng). 頂點(diǎn) 和 分別稱為的起點(diǎn)和終點(diǎn) ,0vkv而 稱為W的內(nèi)部頂點(diǎn).121,kvvv 2) 若途徑W的邊互不相同但頂點(diǎn)(dngdin)可重復(fù)，則稱W為跡或簡(jiǎn)單鏈. 3) 若途徑W的頂點(diǎn)和邊均互不相同，則稱W為路或路徑. 一條

15、起點(diǎn)為 ,終點(diǎn)為 的路稱為 路0vkv),(0kvv記為).,(0kvvP第25頁(yè)/共74頁(yè)第二十六頁(yè)，共75頁(yè)。 定義(dngy) 1) 途徑 中由相繼項(xiàng)構(gòu)成子序列kkvevevW.110 稱為途徑W的節(jié).jjiiivevev.11 2) 起點(diǎn)與終點(diǎn)(zhngdin)重合的途徑稱為閉途徑. 3) 起點(diǎn)與終點(diǎn)重合的的路稱為(chn wi)圈(或回路)，長(zhǎng)為k的圈稱為k階圈，記為Ck. 4) 若在圖G中存在(u,v)路，則稱頂點(diǎn)u和v在圖G中連通. 5) 若在圖G中頂點(diǎn)u和v是連通的，則頂點(diǎn)u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長(zhǎng)；若沒(méi)沒(méi)有路連接u和v，則定義為無(wú)窮大.第26

16、頁(yè)/共74頁(yè)第二十七頁(yè)，共75頁(yè)。 6) 圖G中任意(rny)兩點(diǎn)皆連通的圖稱為連通圖 7) 對(duì)于有向圖G，若 ，且 有kkveevevW2110ie 類似(li s)地，可定義有向跡，有向路和有向圈.頭 和尾 ，則稱W為有向途徑.iv1iv 例 在右圖中： 途徑(tjng)或鏈： 跡或簡(jiǎn)單鏈： 路或路徑： 圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg第27頁(yè)/共74頁(yè)第二十八頁(yè)，共75頁(yè)。例 一擺渡人欲將一只狼，一頭羊，一籃菜從河西(h x)渡過(guò)河到河?xùn)|，由于船小，一次只能帶一物過(guò)河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。第28頁(yè)/共74頁(yè)

17、第二十九頁(yè)，共75頁(yè)。解：用四維0-1向量表示(biosh)（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取1，否則取0.）共24=16種狀態(tài)(zhungti)，由題設(shè)，狀態(tài)(zhungti)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對(duì)應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，圖論的基本概念第29頁(yè)/共74頁(yè)第三十頁(yè)，共75頁(yè)。人在河西(h x)：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人

18、在河?xùn)|(h dn)：以十個(gè)向量作為頂點(diǎn)，將可能(knng)互相轉(zhuǎn)移的狀態(tài)連線，則得10個(gè)頂點(diǎn)的偶圖。問(wèn)題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開(kāi)始，沿關(guān)聯(lián)邊到達(dá)沒(méi)有到達(dá)的相鄰頂點(diǎn)，到（0,0,0,0）終止，得到有向圖即是。圖論的基本概念第30頁(yè)/共74頁(yè)第三十一頁(yè)，共75頁(yè)。 最短路問(wèn)題(wnt)是圖論應(yīng)用的基本問(wèn)題(wnt)，很多實(shí)際問(wèn)題，如線路(xinl)的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用流等問(wèn)題,都可通過(guò)建立最短路問(wèn)題模型來(lái)求解.最短路的定義最短路問(wèn)題的兩種方法：Dijkstra和Floyd算法 .1) 求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路.2

19、) 求賦權(quán)圖中任意兩點(diǎn)間的最短路.第31頁(yè)/共74頁(yè)第三十二頁(yè)，共75頁(yè)。 2) 在賦權(quán)圖G中，從頂點(diǎn)(dngdin)u到頂點(diǎn)(dngdin)v的具有最小權(quán)定義(dngy) 1) 若H是賦權(quán)圖G的一個(gè)子圖，則稱H的各邊的權(quán)和 為H的權(quán). 類似地，若)()()(HEeewHw稱為(chn wi)路P的權(quán)若P(u,v)是賦權(quán)圖G中從u到v的路,稱)()()(PEeewPw 的路P*(u,v)，稱為u到v的最短路 3) 把賦權(quán)圖G中一條路的權(quán)稱為它的長(zhǎng)，把(u,v)路的最小權(quán)稱為u和v之間的距離，并記作 d(u,v). 第32頁(yè)/共74頁(yè)第三十三頁(yè)，共75頁(yè)。 假設(shè)(jish)G為賦權(quán)有向圖或無(wú)向圖

20、，G邊上的權(quán)均非負(fù)若 ，則規(guī)定 )(),(GEvu.),(vuw最短路(dunl)是一條路，且最短路(dunl)的任一節(jié)也是最短路(dunl)求下面賦權(quán)圖中頂點(diǎn)u0到其余頂點(diǎn)的最短路第33頁(yè)/共74頁(yè)第三十四頁(yè)，共75頁(yè)。Dijkstra算法(sun f): 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，

21、并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ul第34頁(yè)/共74頁(yè)第三十五頁(yè)，共75頁(yè)。Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul第35頁(yè)/共74頁(yè)第三十六頁(yè)，共

22、75頁(yè)。02Su Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul第36頁(yè)/共74頁(yè)第三十七頁(yè)，共75頁(yè)。03Su )(3ulDijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ，

23、 ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul第37頁(yè)/共74頁(yè)第三十八頁(yè)，共75頁(yè)。04Su )(3ulDijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(m

24、invuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul第38頁(yè)/共74頁(yè)第三十九頁(yè)，共75頁(yè)。05Su )(3ulDijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv

25、一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul第39頁(yè)/共74頁(yè)第四十頁(yè)，共75頁(yè)。06Su )(3ulDijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i

26、+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul第40頁(yè)/共74頁(yè)第四十一頁(yè)，共75頁(yè)。07Su Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluS

27、j1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul第41頁(yè)/共74頁(yè)第四十二頁(yè)，共75頁(yè)。Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)

28、(6ul)()(min10ulvlSv8)(7ul第42頁(yè)/共74頁(yè)第四十三頁(yè)，共75頁(yè)。Dijkstra算法(sun f): 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2mi

29、n)(2ul2)(2ul第43頁(yè)/共74頁(yè)第四十四頁(yè)，共75頁(yè)。Dijkstra算法: 求G中從頂點(diǎn)u0到其余(qy)頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ul第44頁(yè)

30、/共74頁(yè)第四十五頁(yè)，共75頁(yè)。Dijkstra算法: 求G中從頂點(diǎn)u0到其余(qy)頂點(diǎn)的最短路. 1) 置 ，對(duì) ， ， 且 .0)(0ul0uv )(vl00uS 0i 2) 對(duì)每個(gè) ，用iSv),()(),(minvuwulvlii代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的)(vl)(minvliSv一個(gè)頂點(diǎn)記為 ，置1iu.11iiiuSS 3) 若 ，則停止；若 ，則用 i+1 代1i1i替i，并轉(zhuǎn)2).第45頁(yè)/共74頁(yè)第四十六頁(yè)，共75頁(yè)。第46頁(yè)/共74頁(yè)第四十七頁(yè)，共75頁(yè)。定義 根據(jù)頂點(diǎn)v的標(biāo)號(hào)l(v)的取值途徑，使 到v0u的最短路中與v相鄰的前一個(gè)頂點(diǎn)(dngdin)w，稱

31、為v的先驅(qū)點(diǎn)，記為z(v), 即z(v)=w.先驅(qū)(xinq)點(diǎn)可用于追蹤最短路徑. 例5的標(biāo)號(hào)過(guò)程也可按如下方式(fngsh)進(jìn)行：首先寫出左圖帶權(quán)鄰接矩陣024782063446046340357630135102273201847210W因G是無(wú)向圖，故W是對(duì)稱陣第47頁(yè)/共74頁(yè)第四十八頁(yè)，共75頁(yè)。第48頁(yè)/共74頁(yè)第四十九頁(yè)，共75頁(yè)。1u0u6u7u2u4u3u5u第49頁(yè)/共74頁(yè)第五十頁(yè)，共75頁(yè)。Dijkstra算法：求G中從頂點(diǎn)u0到其余(qy)頂點(diǎn)的最短路設(shè)G為賦權(quán)有向圖或無(wú)向圖，G邊上(bin shn)的權(quán)均均非負(fù). 對(duì)每個(gè)頂點(diǎn)(dngdin)，定義兩個(gè)標(biāo)記（l(v)

32、，z(v)），其中: l(v) ：表從頂點(diǎn)u0到v的一條路的權(quán) z(v) ：v的先驅(qū)點(diǎn)，用以確定最短路的路線.l(v)為從頂點(diǎn)u0到v的最短路的權(quán)算法的過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終S：具有永久標(biāo)號(hào)的頂點(diǎn)集.輸入: G的帶權(quán)鄰接矩陣 w(u,v)備用-將求最短路與最短路徑結(jié)合起來(lái):第50頁(yè)/共74頁(yè)第五十一頁(yè)，共75頁(yè)。算法(sun f)步驟：l(v)u0vl(u)uw(u,v)第51頁(yè)/共74頁(yè)第五十二頁(yè)，共75頁(yè)。首先(shuxin)寫出帶權(quán)鄰接矩陣024782063446046340357630135102273201847210W例 求下圖從頂點(diǎn)u0到其余(qy)頂點(diǎn)的最短路因

33、G是無(wú)向圖，故W是對(duì)稱(duchn)陣第52頁(yè)/共74頁(yè)第五十三頁(yè)，共75頁(yè)。第53頁(yè)/共74頁(yè)第五十四頁(yè)，共75頁(yè)。1u0u6u7u2u4u3u5u第54頁(yè)/共74頁(yè)第五十五頁(yè)，共75頁(yè)。 （I）求距離矩陣(j zhn)的方法.（II）求路徑矩陣的方法.（III）查找最短路路徑的方法. Floyd算法：求任意兩頂點(diǎn)間的最短路. 舉例說(shuō)明第55頁(yè)/共74頁(yè)第五十六頁(yè)，共75頁(yè)。第56頁(yè)/共74頁(yè)第五十七頁(yè)，共75頁(yè)。第57頁(yè)/共74頁(yè)第五十八頁(yè)，共75頁(yè)。在建立(jinl)距離矩陣的同時(shí)可建立(jinl)路徑矩陣R 第58頁(yè)/共74頁(yè)第五十九頁(yè)，共75頁(yè)。ivjv然后(rnhu)用同樣的方法再

34、分頭查找若：1av2av3avkav1bv2bvmbv第59頁(yè)/共74頁(yè)第六十頁(yè)，共75頁(yè)。第60頁(yè)/共74頁(yè)第六十一頁(yè)，共75頁(yè)。例 求下圖中加權(quán)圖的任意(rny)兩點(diǎn)間的距離與路徑. ,053142503330212044401210 )0(D,654321654321654321654321654321654321 )0(R第61頁(yè)/共74頁(yè)第六十二頁(yè)，共75頁(yè)。,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入(ch r)點(diǎn) v1，得：,053132503330212043401210)1(D,65431

35、1654321654321654321154321654321 )1 (R矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后(yhu)有變化的元素.第62頁(yè)/共74頁(yè)第六十三頁(yè)，共75頁(yè)。,min) 1() 1() 1()(kkjkikkijkijdddd插入(ch r)點(diǎn) v2，得：,053132503330212043401210)1(D矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后(yhu)有變化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R第63頁(yè)/共74頁(yè)第六十四頁(yè)，共75頁(yè)。,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入(ch r)點(diǎn) v3，得：,05313250333021204534012510)2(D第64頁(yè)/共74頁(yè)第六十五頁(yè)，共75頁(yè)。,min) 1() 1() 1()(kkjkikkijkijdddd,053132