資源描述：
《圖論-4(最短路問題)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第七章圖論引言7.1圖的基本概念7.2路與連通7.3圖的矩陣表示7.4最短路徑問題7.5圖的匹配8.1Euler圖和Hamilton圖8.2樹8.3生成樹8.4平面圖7.4最短路問題一、問題的提出賦權(quán)圖（網(wǎng)絡(luò)）：G=(V,E)中，給每條邊a=賦予一個非負實數(shù)權(quán)wij，得到一個有向網(wǎng)絡(luò)7.4最短路問題路徑路徑長度非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和[距離矩陣]對上述網(wǎng)絡(luò)，定義D=(dij)n?n，n=
2、V
3、wij當?Edij=?其它[帶權(quán)路徑長度]對上述網(wǎng)絡(luò)，路徑v1,v2
4、,…,vk的帶權(quán)路徑長度定義為7.4最短路問題最短路問題在實際工作中應(yīng)用1、通訊網(wǎng)絡(luò)中最可靠問題2、最大容量問題3、統(tǒng)籌方法中求關(guān)鍵路線4、背包問題5、選址問題6、工件加工順序問題7、中國郵遞員問題背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。7.4最短路問題例一位旅客要從A城到B城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時間
5、最短的路線；他希望選擇一條途中費用最小的路線；v5v4v3v2v1v01006030101020550這些問題均是帶權(quán)圖上的最短路徑問題。邊上的權(quán)表示一站邊上的權(quán)代表距離邊的權(quán)代表費用7.4最短路問題Dijkstra算法Floyd算法Floyd-Warshall算法7.4最短路問題Dijkstra算法Dijkstra算法是由荷蘭計算機科學(xué)家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。荷蘭計算機科學(xué)教授EdsgerW.Dijkstra(1930
6、-)在1972年獲得美國計算機協(xié)會授予的圖靈獎，這是計算機科學(xué)中最具聲望的獎項之一。Dijkstra算法是求出一個連通加權(quán)簡單圖中從結(jié)點a到結(jié)點z的最短路。邊(i,j)的權(quán)ω(i,j)＞0，且結(jié)點x的標號為L(x)。結(jié)束時，L(z)是從a到z的最短長度。舉例來說，如果圖中的頂點表示城市，而邊上的權(quán)重表示城市間開車行經(jīng)的距離。Dijkstra算法可以用來找到兩個城市之間的最短路徑。7.4.1Dijkstra算法Dijkstra算法基本思想:把圖中所有結(jié)點分為兩組，每一個結(jié)點對應(yīng)一個距離值。第一組：包括已確定最短路徑的結(jié)點，結(jié)點對應(yīng)的距離值是由
7、v0到此結(jié)點的最短路徑長度；第二組：包括尚未確定最短路徑的結(jié)點，結(jié)點對應(yīng)的距離值是v0經(jīng)由第一組結(jié)點（中間結(jié)點）至此結(jié)點的最短路徑長度。按最短路徑長度遞增的順序把第二組的結(jié)點加到第一組中去，直至v0可達的所有結(jié)點都包含于第一組。在這個過程中，總保持從v0到第一組各結(jié)點的最短路徑長度都不大于從v0至第二組任何結(jié)點的路徑長度。7.4.1Dijkstra算法設(shè)源點為v0初始時v0進入第一組，v0的距離值為0；第二組包含其它所有結(jié)點，這些結(jié)點對應(yīng)的距離值這樣確定（設(shè)vi為第二組中的結(jié)點）然后每次從第二組的結(jié)點中選一個其距離值為最小的結(jié)點vm加到第一
8、組中。每往第一組加入一個結(jié)點vm，就要對第二組的各結(jié)點的距離值作一次修正（設(shè)vi為第二組的結(jié)點）：若加進vm做中間結(jié)點使得v0至vi的路徑長度更短（即vi的距離值>vm的距離值+Wmi），則要修改vi的距離（vi的距離值←vm的距離值+Wmi）。修改后再選距離值最小的一個結(jié)點加入到第一組中，…。如此進行下去，直至第一組囊括圖的所有結(jié)點或再無可加入第一組的結(jié)點存在。顯然，這種從第二組的結(jié)點中選距離值最小的結(jié)點擴展是一種貪心策略。7.4.1Dijkstra算法procedureDijkstra(G:所有權(quán)都為正數(shù)的加權(quán)連通簡單圖){G帶有頂點a
9、＝v0,v1,…,vn＝z和權(quán)ω(vi,vj)，若(vi,vj)不是G的邊，則ω(vi,vj)＝∞}fori:＝1tonL(vi)＝∞L(a):＝0S:＝（初始化標記，a的標記為0，其余結(jié)點標記為∞，S是空集}whilezSbeginu:＝不屬于S的L(u)最小的一個頂點S:＝S∪{u}for所有不屬于S的頂點vifL(u)＋ω(u,v)＜L(v)thenL(v):＝L(u)＋ω(u,v){這樣就給S中添加帶最小標記的頂點并且更新不在S中的頂點的標記}end{L(z)＝從a到z的最短長度}dij7.4.1Dijkstra算法下面給出該算法的
10、框圖：通過框圖，容易計算該算法計算量。7.4.1Dijkstra算法下面通過一個實例來說明Dijkstra算法是如何工作的?！?.4.1Dijkstra算法7.4.1Dijkst
