第十一章圖與網(wǎng)絡(luò)分析

第十一章圖與網(wǎng)絡(luò)分析第1頁，共190頁，2023年，2月20日，星期四第十一章圖與網(wǎng)絡(luò)分析11.1引言第2頁，共190頁，2023年，2月20日，星期四引言圖論是專門研究圖的理論的一門數(shù)學(xué)分支，屬于離散數(shù)學(xué)范疇，與運籌學(xué)有交叉，它有200多年歷史，大體可劃分為三個階段。第3頁，共190頁，2023年，2月20日，星期四引言第一階段從十八世紀(jì)中葉到十九世紀(jì)中葉，處于萌芽階段，多數(shù)問題由游戲而產(chǎn)生，最有代表性的工作是所謂的Euler七橋問題，即一筆畫問題。第4頁，共190頁，2023年，2月20日，星期四引言第二階段從十九世紀(jì)中葉到二十世紀(jì)中葉，這時，圖論問題大量出現(xiàn)，如Hamilton問題，地圖染色的四色問題以及可平面性問題等，這時，也出現(xiàn)用圖解決實際問題，如Cayley把樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff用樹去研究電網(wǎng)絡(luò)等.第5頁，共190頁，2023年，2月20日，星期四引言第三階段二十世紀(jì)中葉以后，由生產(chǎn)管理、軍事、交通、運輸、計算機網(wǎng)絡(luò)等方面提出實際問題，以及大型計算機使大規(guī)模問題的求解成為可能，特別是以Ford和Fulkerson建立的網(wǎng)絡(luò)流理論，與線性規(guī)劃、動態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透，促進了圖論對實際問題的應(yīng)用。第6頁，共190頁，2023年，2月20日，星期四ABCD哥尼斯堡七橋問題

第7頁，共190頁，2023年，2月20日，星期四哥尼斯堡七橋問題

最后，數(shù)學(xué)家Euler在1736年巧妙地給出了這個問題的答案，并因此奠定了圖論的基礎(chǔ)Euler把A、B、C、D四塊陸地分別收縮成四個頂點，把橋表示成連接對應(yīng)頂點之間的邊，問題轉(zhuǎn)化為從任意一點出發(fā)，能不能經(jīng)過各邊一次且僅一次，最后返回該點。這就是著名的Euler問題。第8頁，共190頁，2023年，2月20日，星期四ABCD哥尼斯堡七橋問題

第9頁，共190頁，2023年，2月20日，星期四哥尼斯堡七橋問題ACBD第10頁，共190頁，2023年，2月20日，星期四圍坐問題有7個人圍桌而坐，如果要求每次相鄰的人都與以前完全不同，試問不同的就座方案共有多少種？用頂點表示人，用邊表示兩者相鄰，因為最初任何兩個人都允許相鄰，所以任何兩點都可以有邊相連。第11頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第12頁，共190頁，2023年，2月20日，星期四假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊。圍坐問題第13頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第14頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第15頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第16頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第17頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第18頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第19頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第20頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第21頁，共190頁，2023年，2月20日，星期四假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊。圍坐問題第22頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第23頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第24頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第25頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第26頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第27頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第28頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第29頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第30頁，共190頁，2023年，2月20日，星期四假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊，只留下7點孤立點，所以該問題只有三個就座方案。圍坐問題第31頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第32頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第33頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第34頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第35頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第36頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第37頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第38頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第39頁，共190頁，2023年，2月20日，星期四1237645圍坐問題第40頁，共190頁，2023年，2月20日，星期四假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允許這些頂點之間繼續(xù)相鄰，只能從圖中刪去這些邊，只留下7點孤立點，所以該問題只有三個就座方案。圍坐問題第41頁，共190頁，2023年，2月20日，星期四哈密頓（Hamilton）回路是十九世紀(jì)英國數(shù)學(xué)家哈密頓提出，給出一個正12面體圖形，共有20個頂點表示20個城市，要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次，最后回到原處的周游世界線路（并不要求經(jīng)過每條邊）。哈密頓回路第42頁，共190頁，2023年，2月20日，星期四哈密頓回路第43頁，共190頁，2023年，2月20日，星期四哈密頓回路第44頁，共190頁，2023年，2月20日，星期四哈密頓回路第45頁，共190頁，2023年，2月20日，星期四哈密頓回路第46頁，共190頁，2023年，2月20日，星期四哈密頓回路第47頁，共190頁，2023年，2月20日，星期四哈密頓回路第48頁，共190頁，2023年，2月20日，星期四哈密頓回路第49頁，共190頁，2023年，2月20日，星期四哈密頓回路第50頁，共190頁，2023年，2月20日，星期四哈密頓回路第51頁，共190頁，2023年，2月20日，星期四哈密頓回路第52頁，共190頁，2023年，2月20日，星期四哈密頓回路第53頁，共190頁，2023年，2月20日，星期四哈密頓回路第54頁，共190頁，2023年，2月20日，星期四哈密頓回路第55頁，共190頁，2023年，2月20日，星期四哈密頓回路第56頁，共190頁，2023年，2月20日，星期四哈密頓回路第57頁，共190頁，2023年，2月20日，星期四哈密頓回路第58頁，共190頁，2023年，2月20日，星期四哈密頓回路第59頁，共190頁，2023年，2月20日，星期四哈密頓回路第60頁，共190頁，2023年，2月20日，星期四引言瑞士數(shù)學(xué)家Euler在1736年發(fā)表的一篇題為“依據(jù)幾何位置的解題方法”的論文，有效的解決了哥尼斯堡七橋問題，是有記載的第一篇圖論論文，Euler被認(rèn)為是圖論的創(chuàng)始人。圖論的第一本專著是匈牙利的OKonig寫的“有限圖與無限圖的理論”，發(fā)表于1936。從1736到1936，前后200年，總的來講這一時期圖論發(fā)展緩慢。直到20世紀(jì)中葉，電子計算機的發(fā)展和零散數(shù)學(xué)問題具有越來越重要的地位，使得圖論得以迅速發(fā)展第61頁，共190頁，2023年，2月20日，星期四第十一章圖與網(wǎng)絡(luò)分析11.1引言11.2圖與網(wǎng)絡(luò)的基本概念第62頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念圖論是專門研究圖的理論的一門數(shù)學(xué)分支，主要研究點和線之間的幾何關(guān)系第63頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念定義：圖是由點集V=（vi）和V中元素的無序?qū)Φ囊粋€集合E=（ek）所構(gòu)成的二元組，記為G=（V，E），其中：V=（v1，v2，…...vm）是m個頂點集合；E=（e1，e2，…...en）是n條邊集合。當(dāng)V，E為有限集合時，G稱為有限圖，否則稱為無限圖，本章只討論有限圖。第64頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2第65頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念V=（v1，v2，…...v6）E=（e1，e2，…...e8）e1=（v1，v2）e2=（v1，v2）e7=（v3，v5）e8=（v4，v4）稱為自回路(環(huán))；第66頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念說明：（1）V非空，即沒有頂點的圖不討論；（2）E無非空條件，即允許沒有邊；（3）E是一個不與V中頂點相交的邊集合；（指點只在邊的端點處相交）（4）任一條邊必須與一對頂點關(guān)聯(lián)，反之不然。第67頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念V=（v1，v2，…...v6）E=（e1，e2，…...e8）e1=（v1，v2）e2=（v1，v2）e7=（v3，v5）e8=（v4，v4）稱為自回路(環(huán))；第68頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念定義對任一條邊（vi，vj）屬于E，如果邊（vi，vj）的端點無序，則它是無向邊，此時圖為無向圖。如果如果邊（vi，vj）的端點有序，則它表示以vi為始點，vj為終點的有向邊（或稱為?。?，此時圖為有向圖。第69頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2第70頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖第71頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念定義（鏈）如果圖中的某些點、邊可以排列成點和邊的交錯序列，則稱此為一條鏈。定義（圈）如一條鏈中起點和終點重合，則稱此為一條圈。第72頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2第73頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2第74頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2鏈，點邊交錯序列v1,e5,v4,e4,v3第75頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2圈,起點和終點重合v1,e5,v4,e4,v3,e6,v1第76頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v3v2v4v6v5e1e3e5e6e4e8e7e2第77頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念定義（鏈）如果圖中的某些點、邊可以排列成點和邊的交錯序列，則稱此為一條鏈。定義（圈）如一條鏈中起點和終點重合，則稱此為一條圈。第78頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v5v4v2v3e1e8e7e6e5e4e3e2鏈：v3,e2,v2第79頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v5v4v2v3e1e8e7e6e5e4e3e2鏈：v3,e2,v2,e4,v4第80頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v5v4v2v3e1e8e7e6e5e4e3e2鏈：v3,e2,v2,e4,v4,e3,v1第81頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v5v4v2v3e1e8e7e6e5e4e3e2鏈：v3,e2,v2,e4,v4,e7,v5第82頁，共190頁，2023年，2月20日，星期四v1v5v4v2e1e7e6e3§11.2圖與網(wǎng)絡(luò)的基本概念第83頁，共190頁，2023年，2月20日，星期四v1v5v4v2e1e7e6e3§11.2圖與網(wǎng)絡(luò)的基本概念第84頁，共190頁，2023年，2月20日，星期四v1v5v4v2e1e7e6e3§11.2圖與網(wǎng)絡(luò)的基本概念第85頁，共190頁，2023年，2月20日，星期四v1v5v4v2e1e7e6e3§11.2圖與網(wǎng)絡(luò)的基本概念第86頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念定義（鏈）如果圖中的某些點、邊可以排列成點和邊的交錯序列，則稱此為一條鏈。定義（圈）如一條鏈中起點和終點重合，則稱此為一條圈。第87頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念圖的矩陣表示一個圖非常直觀，但是不容易計算，特別不容易在計算機上進行計算，一個有效的解決辦法是將圖表示成矩陣形式，通常采用的矩陣是鄰接矩陣、邊長鄰接矩陣、弧長矩陣和關(guān)聯(lián)矩陣。第88頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念鄰接矩陣表示圖G的頂點之間的鄰接關(guān)系，它是一個nxn的矩陣，如果兩個頂點之間有邊相聯(lián)時，記為1，否則為0。v1v2v3v4第89頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v2v3v4v1v2v3v4v10111v21110v31101v41010第90頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念v1v5v4v3v2v1v2v3v4v5v100011v210010v301100v401101v510010第91頁，共190頁，2023年，2月20日，星期四§11.2圖與網(wǎng)絡(luò)的基本概念賦權(quán)圖或網(wǎng)絡(luò)在圖的各邊上一個數(shù)量指標(biāo)（cij），具體表示這條邊的權(quán)（距離，單價，通過能力等）。無向網(wǎng)絡(luò)；有向網(wǎng)絡(luò)；混合網(wǎng)絡(luò)；邊權(quán)網(wǎng)絡(luò)；點權(quán)網(wǎng)絡(luò)。第92頁，共190頁，2023年，2月20日，星期四第十一章圖與網(wǎng)絡(luò)分析11.1引言11.2圖與網(wǎng)絡(luò)的基本概念11.3最短路問題第93頁，共190頁，2023年，2月20日，星期四§11.3最短路問題對一個賦權(quán)的有向圖D;指定的兩個點Vs和Vt；找到一條從Vs到Vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最??；這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)總和被稱為從Vs到Vt的距離。第94頁，共190頁，2023年，2月20日，星期四§11.3最短路問題一、求解最短路的Dijkstra算法(迪科斯徹，雙標(biāo)號法）對圖中的點Vj賦予兩個標(biāo)號（lj,kj）,第一個標(biāo)號lj表示從起點Vs到Vj的最短路的長度，第二個標(biāo)號kj表示在Vs到Vj的最短路上Vj前面一個鄰點的下標(biāo)。例如：V6（8,4)表示，從起點V１到V６的最短路的長度為８在這條最短路上V６的前一個鄰點為V４。第95頁，共190頁，2023年，2月20日，星期四§11.3最短路問題步驟：給出點V1以標(biāo)號(0，s)找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合

如果上述弧的集合是空集，則計算結(jié)束。

如果Vt已標(biāo)號（lt,kt），則Vs到Vt的距離為lt。如果Vt未標(biāo)號，則可以斷言不存在從Vs到Vt的有向路。

如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。對上述弧的集合中的每一條弧，計算sij=li+cij

。在所有的sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點以雙標(biāo)號（scd,c）,返回步驟2。第96頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例求下圖中v1到v6的最短路v23527531512v1v6v5v3v4第97頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4１.給出點V1以標(biāo)號(0，s)(0，s)第98頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)２.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J，以及弧的集合第99頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)２.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1｝J＝｛V2,V3,V4,V5,V6｝第100頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)２.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1｝J＝｛V2,V3,V4,V5,V6｝弧的集合＝｛(V1,V2),(V1,V3),(V1,V4)第101頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)2.對每一條弧，計算sij=li+cij

。找到其值為最小的弧,給此弧的終點以雙標(biāo)號s12=l1+c12=0+3=3s13=l1+c13=0+2=2s14=l1+c14=0+5=5MIN(s12,

s13,

s14)=

s13=2(2，1)第102頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)3.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1,V3｝J＝｛V2,V4,V5,V6｝(2，1)第103頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)3.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1,V3｝J＝｛V2,V4,V5,V6｝弧的集合＝｛(V1,V2),(V1,V4),(V3,V4)(2，1)第104頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)3.對每一條弧，計算sij=li+cij

。找到其值為最小的弧,給此弧的終點以雙標(biāo)號s12=l1+c12=0+3=3s14=l1+c14=0+5=5s34=l3+c34=2+1=3MIN(s12,

s14,

s34)=

s12=s34=3(2，1)(3，1)(3，3)第105頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)4.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1,V2,V3,V4｝J＝｛V5,V6｝(2，1)(3，1)(3，3)第106頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)4.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1,V2,V3,V4｝J＝｛V5,V6｝弧的集合＝｛(V2,V6),(V4,V6)}(2，1)(3，1)(3，3)第107頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)4.對每一條弧，計算sij=li+cij

。找到其值為最小的弧,給此弧的終點以雙標(biāo)號s26=l2+c26=3+7=10s46=l4+c46=3+5=8MIN(s26,

s46)=

s46=8(2，1)(3，1)(3，3)(8，4)第108頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)5.找出已標(biāo)號點的集合I，沒標(biāo)號的點的集合J,以及弧的集合I＝｛V1,V2,V3,V4,V6｝J＝｛V6｝(2，1)(3，1)(3，3)上述弧的集合是空集，計算結(jié)束。

第109頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法v23527531512v1v6v5v3v4(0，s)(2，1)(3，1)(3，3)(8，4)由于V６已標(biāo)號（８,４）則V１到V６的距離為８。最短路徑為(由倒推得到)V１－V３－V４－V６第110頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。V1（甲地）15176244431065V2V7（乙地）V3V4V5V6第111頁，共190頁，2023年，2月20日，星期四§11.3最短路問題

這是一個求無向圖的最短路的問題?？梢园褵o向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號的點到未標(biāo)號點弧的集合改成已標(biāo)號點到未標(biāo)號點邊的集合即可。第112頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例求下圖中v1到v７的最短路V11517624431065V2V3V4V5V6V7第113頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法１.給出點V1以標(biāo)號(0，s)(0，s)V11517624431065V2V3V4V5V6V7第114頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法2.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V1,V2),(V1,V3)}(0，s)V11517624431065V2V3V4V5V6V7第115頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法s12=l1+c12=0+15=15s13=l1+c13=0+10=10MIN(s12,

s13)=

s13=102.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V1,V2),(V1,V3)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)第116頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法3.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V1,V2),(V3,V2),(V3,V5)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)第117頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法3.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V1,V2),(V3,V2),(V3,V5)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)s12=l1+c12=0+15=15s32=l3+c32=10+3=13s35=l3+c35=10+4=14MIN(s12,

s32,

s35)=

s32=13(13，3)第118頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法4.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V4),(V2,V7),(V3,V5)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)第119頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法s24=l2+c24=13+6=19s27=l2+c27=13+17=30s35=l3+c35=10+4=14MIN(s24,

s27,

s35)=

s35=144.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V4),(V2,V7),(V3,V5)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，3)第120頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法5.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V4),(V2,V7),(V5,V4),(V5,V6)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，3)第121頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法5.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V4),(V2,V7),(V5,V4),(V5,V6)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，3)s24=l2+c24=13+6=19s27=l2+c27=13+17=30s54=l5+c54=14+4=18s56=l5+c56=14+2=16MIN(s24,

s27,

s54,

s56)=

s56=16(16，5)第122頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法6.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V4),(V2,V7),(V5,V4),(V6,V7)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，3)(16，5)第123頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法6.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V4),(V2,V7),(V5,V4),(V6,V7)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，3)(16，5)s24=l2+c24=13+6=19s27=l2+c27=13+17=30s54=l5+c54=14+4=18s67=l6+c67=16+6=22MIN(s24,

s27,

s54,

s67)=

s54=18(18，5)第124頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法7.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V7),(V4,V7),(V6,V7)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，5)(16，5)(18，5)第125頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法7.已標(biāo)號點至沒標(biāo)號的點的邊的集合｛(V2,V7),(V4,V7),(V6,V7)}(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，5)(16，5)(18，5)s27=l2+c27=13+17=30s47=l4+c47=18+5=23s67=l6+c67=16+6=22MIN(s27,

s47,

s67)=

s67=22(22，6)第126頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法8.已標(biāo)號點至沒標(biāo)號的點的邊的集合為空，計算結(jié)束(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，5)(16，5)(18，5)(22，6)第127頁，共190頁，2023年，2月20日，星期四§11.3最短路問題解采用Dijkstra算法(0，s)V11517624431065V2V3V4V5V6V7(10，1)(13，3)(14，3)(16，5)(18，5)(22，6)由于V7已標(biāo)號（22,6）則V１到V６的距離為22。最短路徑為V１－V3－V5－V6－V7第128頁，共190頁，2023年，2月20日，星期四§11.3最短路問題習(xí)題采用Dijkstra算法求V１到V8的最短路4954167654475V1V8V2V4V6V3V5V7第129頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)第130頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)第131頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)第132頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)第133頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)第134頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)第135頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)第136頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)第137頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)第138頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)(13，5)第139頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)(13，5)第140頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)(13，5)(14，5)第141頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)(13，5)(14，5)第142頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)(13，5)(14，5)(15，7)第143頁，共190頁，2023年，2月20日，星期四§11.3最短路問題4954167654475V1V8V2V4V6V3V5V7(0，s)(4，1)(6，1)(8，2)(9，2)(13，5)(14，5)(15，7)由于V8已標(biāo)號（15,7）則V１到V8的距離為15。最短路徑為V１－V2－V5－V7－V8第144頁，共190頁，2023年，2月20日，星期四§11.3最短路問題6V1V8V2V5V7(0，s)(4，1)(8，2)(14，5)(15，7)由于V8已標(biāo)號（15,7）則V１到V8的距離為15。最短路徑為V１－V2－V5－V7－V8第145頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當(dāng)然新設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。第146頁，共190頁，2023年，2月20日，星期四§11.3最短路問題設(shè)備每年年初的價格表設(shè)備維修費如下表年份12345年初價格1111121213使用年數(shù)0-11-22-33-44-5每年維修費用5681118第147頁，共190頁，2023年，2月20日，星期四年份12345年初價格1111121213使用年數(shù)0-11-22-33-44-5每年維修費用5681118123456第1年購入新設(shè)備1622304159第2年購入新設(shè)備16223041第3年購入新設(shè)備172331第4年購入新設(shè)備1723第5年購入新設(shè)備18第6年購入新設(shè)備第148頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723第149頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723第150頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6（v1,v4）表示，第1年年初購進一臺新設(shè)備，使用到第4年年初。（v4,v5）表示，第4年年初購進一臺新設(shè)備，使用到第5年年初（v5,v6）表示，第5年年初購進一臺新設(shè)備，使用到第6年年初301718第151頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)第152頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)第153頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)第154頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)第155頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)第156頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)第157頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)第158頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)(41，1)第159頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,弧（vi,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)(41，1)第160頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)(41，1)(53，3)(53，4)第161頁，共190頁，2023年，2月20日，星期四§11.3最短路問題例3的解：用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)(41，1)(53，3)(53，4)第162頁，共190頁，2023年，2月20日，星期四§11.3最短路問題其最短路有兩條:V１－V3－V6;V１－V4－V6.即第1年年初購進新設(shè)備使用到第3年年初，第3年年初購進新設(shè)備使用到第5年年底；或第1年年初購進新設(shè)備使用到第4年年初，第4年年初購進新設(shè)備使用到第5年年底。費用均為53。v1v2v3v4v5v6162230415916223041312317181723(0，s)(16，1)(22，1)(30，1)(41，1)(53，3)(53，4)第163頁，共190頁，2023年，2月20日，星期四§11.3最短路問題其最短路有兩條:V１－V3－V6;V１－V4－V6.即第1年年初購進新設(shè)備使用到第3年年初，第3年年初購進新設(shè)備使用到第5年年底；或第1年年初購進新設(shè)備使用到第4年年初，第4年年初購進新設(shè)備使用到第5年年底。費用均為53。v1v2v3v4v5v6311822(53，3)(22，1)第164頁，共190頁，2023年，2月20日，星期四§11.3最短路問題其最短路有兩條:V１－V3－V6;V１－V4－V6.即第1年年初購進新設(shè)備使用到第3年年初，第3年年初購進新設(shè)備使用到第5年年底；或第1年年初購進新設(shè)備使用到第4年年初，第4年年初購進新設(shè)備使用到第5年年底。費用均為53。v1v2v3v4v5v63023(53，4)(30，1)第165頁，共190頁，2023年，2月20日，星期四§11.3最短路問題第1年第2年第3年第4年第5年購買費1112131414機器役齡0－11－22－33－44－5維修費5681118殘值43210習(xí)題：工廠使用一臺設(shè)備，每年年初作出決定，如果繼續(xù)使用舊的，要支付維修費，如果購買新的支付購買費。試制定五年更新計劃第166頁，共190頁，2023年，2月20日，星期四§11.3最短路問題123456第1年購入新設(shè)備1219284059第2年購入新設(shè)備13202941第3年購入新設(shè)備142130第4年購入新設(shè)備1522第5年購入新設(shè)備15第6年購入新設(shè)備第1年第2年第3年第4年第5年購買費1112131414機器役齡0－11－22－33－44－5維修費5681118殘值43210第167頁，共190頁，2023年，2月20日，星期四v1v2v3v4v5v61219284059表示，第1年年初購進一臺新設(shè)備，使用到第2-6年年初的費用。第168頁，共190頁，2023年，2月20日，星期四v1v2v3v4v5v61219284059202941表示，第2年年初購進一臺新設(shè)備，使用到第3-6年年初的費用。13第169頁，共190頁，2023年，2月20日，星期四v1v2v3v4v5v61219284059202941表示，第3年年初購進一臺新設(shè)備，使用到第4-6年年初的費用。14213013第170頁，共190頁，2023年，2月20日，星期四v1v2v3v4v5v61219284059201329