matlab圖與網(wǎng)絡(luò)分析模型選講(1)

1、.1第七章第七章 圖與網(wǎng)絡(luò)分析模型選講圖與網(wǎng)絡(luò)分析模型選講一、圖論的基本知識(shí)一、圖論的基本知識(shí)1.圖的概念圖的概念定義定義 圖圖G(V,E)是指一個(gè)二元組是指一個(gè)二元組(V(G),E(G)，其中，其中: (1)V(G)=v1,v2, vn是非空有限集，稱為是非空有限集，稱為頂頂點(diǎn)集點(diǎn)集，(2)E(G)是是V(G)中的元素對中的元素對(vi,vj)組成的集合組成的集合稱為稱為邊集。邊集。 圖圖G： V(G)=v1,v2,v3,v4E(G)= e1,e2,e3,e4,e5,e6e3=(v1,v3).2若圖若圖G是的邊是有方向的，稱是的邊是有方向的，稱G是有向圖，有向圖的是有向圖，有向圖的邊稱為有向

2、邊或弧。邊稱為有向邊或弧。常用術(shù)語常用術(shù)語 邊和它的兩端點(diǎn)稱為互相邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián)關(guān)聯(lián). 與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱為為相鄰相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)的頂點(diǎn)，與同一個(gè)頂點(diǎn)點(diǎn)關(guān)聯(lián)的兩條邊稱為點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰相鄰的邊的邊.3)端點(diǎn)重合為一點(diǎn)的邊稱為端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)環(huán).4) 若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為稱為重邊重邊5)既沒有環(huán)也沒有重邊的圖，稱為既沒有環(huán)也沒有重邊的圖，稱為簡單圖簡單圖 v1v2v3v4v5e1e2e3e4e5e6.36) 若圖若圖G的每一條邊的每一條邊e 都賦以一個(gè)實(shí)數(shù)都賦以

3、一個(gè)實(shí)數(shù)w(e)，稱稱w(e)為邊為邊e的的權(quán)權(quán)，G連同邊上的權(quán)稱為連同邊上的權(quán)稱為賦權(quán)圖賦權(quán)圖 ,記為：記為：G(V,E,W)， W=w(e)| eEv1v2v3v45327) 圖圖G的中頂點(diǎn)的個(gè)數(shù)，的中頂點(diǎn)的個(gè)數(shù)， 稱為圖稱為圖G的階；圖中與某的階；圖中與某個(gè)頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，個(gè)頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，稱為該頂點(diǎn)的度。稱為該頂點(diǎn)的度。8）完全圖：若無向圖的任）完全圖：若無向圖的任意兩個(gè)頂點(diǎn)之間都存在著一意兩個(gè)頂點(diǎn)之間都存在著一條邊，稱此圖為完全圖。條邊，稱此圖為完全圖。.42.圖的矩陣表示圖的矩陣表示鄰接矩陣鄰接矩陣: (以下均假設(shè)圖為簡單圖以下均假設(shè)圖為簡單圖). 圖圖G的鄰接矩陣是表

4、示頂點(diǎn)之間相鄰關(guān)系的矩陣：的鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣： A=(aij)， 01ija若若vi與與vj相鄰相鄰若若vi與與vj不相鄰不相鄰或權(quán)值，或權(quán)值，或或，其中：其中：.5v1v2v3v4 0010001111010110Av1v2v3v45431 040314305150A無向圖無向圖G鄰接矩陣鄰接矩陣A=(aij).6有向圖有向圖G鄰接矩陣鄰接矩陣A=(aij)v1v2v3v4v1v2v3v45431 0000001110000010A 00314050A.7二、最大流問題二、最大流問題定義：設(shè)定義：設(shè)G(V,E)為有向圖，若在每條邊為有向圖，若在每條邊e上定義一個(gè)非上定義一

5、個(gè)非負(fù)權(quán)負(fù)權(quán)c，則稱圖，則稱圖G為一個(gè)網(wǎng)絡(luò)，稱為一個(gè)網(wǎng)絡(luò)，稱c為邊為邊e的容量函數(shù)，的容量函數(shù)，記為記為c(e)。若在有向圖若在有向圖G(V,E)中有兩個(gè)不同的頂點(diǎn)中有兩個(gè)不同的頂點(diǎn)vs與與vt ，若頂點(diǎn)若頂點(diǎn)vs只有出度沒有入度，稱只有出度沒有入度，稱vs為圖為圖G的源，的源，若頂點(diǎn)若頂點(diǎn)vt只有入度沒有出度，稱為只有入度沒有出度，稱為G的匯，的匯，若頂點(diǎn)若頂點(diǎn)v 既不是源也不是匯，稱為既不是源也不是匯，稱為v中間頂點(diǎn)。中間頂點(diǎn)。v2v4v1v3vsvt48375737.8v2v4v1v3vsvt48375737設(shè)設(shè)u,v網(wǎng)絡(luò)網(wǎng)絡(luò)G(V,E)的相鄰頂點(diǎn)，邊的相鄰頂點(diǎn)，邊(u,v)上的函數(shù)上的

6、函數(shù)f(u,v)稱為邊稱為邊(u,v)上的實(shí)際流量；上的實(shí)際流量；若對網(wǎng)絡(luò)若對網(wǎng)絡(luò)G(V,E)的任意相鄰頂點(diǎn)的任意相鄰頂點(diǎn)u,v 均成立：均成立： 0 f(u,v) c(u,v) ， 稱該網(wǎng)絡(luò)為相容網(wǎng)絡(luò)。稱該網(wǎng)絡(luò)為相容網(wǎng)絡(luò)。若若v為網(wǎng)絡(luò)為網(wǎng)絡(luò)G(V,E)的中間頂點(diǎn)，的中間頂點(diǎn)， Vuvuf),( Vwwvf),(有：有：.9v2v4v1v3vsvt48375737網(wǎng)絡(luò)的總流量為從源網(wǎng)絡(luò)的總流量為從源vs 流出的總流量：流出的總流量： VwswvffV),()(流入?yún)R流入?yún)Rvt 總流量：總流量： VutvuffV),()(.10定義：設(shè)網(wǎng)絡(luò)定義：設(shè)網(wǎng)絡(luò)G(V,E)為相容網(wǎng)絡(luò)，為相容網(wǎng)絡(luò)，u,v是

7、是G的相鄰頂點(diǎn)，的相鄰頂點(diǎn)， G的容量函數(shù)為的容量函數(shù)為c(u,v)，實(shí)際流量函數(shù)為，實(shí)際流量函數(shù)為f(u,v)，vs 和和vt分分別為別為G(V,E)的源和匯，的源和匯，V(f)為從源為從源vs流出的總流量，流出的總流量，若：若： Vuuvf),( Vuvuf),( ttssvvfVvvvvvfV ),(, , 0 ),(則稱該網(wǎng)絡(luò)稱為守恒網(wǎng)絡(luò)。則稱該網(wǎng)絡(luò)稱為守恒網(wǎng)絡(luò)。守恒網(wǎng)絡(luò)中的流守恒網(wǎng)絡(luò)中的流 f 稱為可行流。稱為可行流。 若存在一個(gè)可行流若存在一個(gè)可行流f *，使得對所有可行流，使得對所有可行流 f 都都有有V(f *) V(f )成立，則稱成立，則稱f *為最大流。為最大流。.11最

8、大流模型：最大流模型：)(maxfVs.t: VvijVvjijjvvfvvf),(),(,),(0ijjicvvf ),(Vvvji sivvfV ),(Vvvvvitsi , , 0tvvfV ),(.12例例7.1分組交換技術(shù)在計(jì)算機(jī)網(wǎng)絡(luò)中發(fā)揮著重要作用，信分組交換技術(shù)在計(jì)算機(jī)網(wǎng)絡(luò)中發(fā)揮著重要作用，信息從源節(jié)點(diǎn)到目的節(jié)點(diǎn)不再需要一條固定的路徑，而是息從源節(jié)點(diǎn)到目的節(jié)點(diǎn)不再需要一條固定的路徑，而是將其分割為幾組，通過不同的路徑傳輸?shù)侥康墓?jié)點(diǎn)，目將其分割為幾組，通過不同的路徑傳輸?shù)侥康墓?jié)點(diǎn)，目的節(jié)點(diǎn)再重新組合還原文件。現(xiàn)考察如圖所示的網(wǎng)絡(luò)，的節(jié)點(diǎn)再重新組合還原文件?，F(xiàn)考察如圖所示的網(wǎng)絡(luò)，圖中

9、兩節(jié)點(diǎn)間的數(shù)字表示兩交換機(jī)間可用的帶寬，此時(shí)圖中兩節(jié)點(diǎn)間的數(shù)字表示兩交換機(jī)間可用的帶寬，此時(shí)從節(jié)點(diǎn)從節(jié)點(diǎn)1到節(jié)點(diǎn)到節(jié)點(diǎn)9的最大帶寬為多少？的最大帶寬為多少？v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.4.13設(shè)設(shè)fij為從為從vi到到vj的實(shí)際流量，得一個(gè)的實(shí)際流量，得一個(gè)9階方陣：階方陣：F=( fij)記容量矩陣為記容量矩陣為C =0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00

10、 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0 v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.4.14)(maxfV VujiVuijjjff 9 ),(9 , 1 , 01 ),(ifViifV,0CF .ts.15sets: node/1.9/;arc(node,node):c,f;EndsetsOBJmax=flow;for(node(i)|i

11、#ne#1#and#i#ne#9:sum(node(j):f(i,j)=sum(node(j):f(j,i);sum(node(j): f(1,j)=flow;sum(node(j): f(j,9)=flow;for(arc:bnd(0,f,c);)(maxfV VujiVuijjjff 9 ),(9 , 1 , 01 ),(ifViifV,0CF .ts.16data:c=0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0

12、3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0;enddata.17該程序運(yùn)行結(jié)果：該程序運(yùn)行結(jié)果：最大流：最大流：14.2F(1,2)=2.5, F(1,4)=5.6,F(1,5)=6.1,F(2,3)=3.4,F(2,6)=1.5,F(3,8)=3.4,F(4,5)=3.3,F(4,7)=2.3,F(5,2)=2.4,F(5,6)=7,F(6,8)=4,F(6,9)=4.5,F(7,9)=2.3,F(8,9)=7.4,v2v5v1v3v82.5v9v4v7v67.13.46.15.62

13、.43.63.87.44.95.77.25.34.53.86.77.4.180 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0 x=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9; y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9

14、,9; z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;Matlab中求最大流的命令：中求最大流的命令： graphmaxflow(f,a,b).19clc,clearx=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9;y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9;z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;f=sparse(x,y,z)flow,

15、flowmat=graphmaxflow(f,1,9)name1(1:9,1)=v; name2=int2str(1:9);name=cellstr(strcat(name1,name2); view(biograph(flowmat,name,ShowWeights,on).20三、三、旅行售貨員問題（旅行售貨員問題（TSPTSP問題）問題） 一個(gè)旅行商，從城市一個(gè)旅行商，從城市1出發(fā)，要遍訪城市出發(fā)，要遍訪城市1,2,3,n各一次，最后返回城市各一次，最后返回城市1。若從城市。若從城市i到到j(luò)的旅費(fèi)為的旅費(fèi)為cij， 問他應(yīng)按怎樣的次序訪問這些城市，能使得總旅費(fèi)問他應(yīng)按怎樣的次序訪問這些城

16、市，能使得總旅費(fèi)最少？最少？ 用圖論語言描述：在賦權(quán)圖中，尋找一條經(jīng)過所有用圖論語言描述：在賦權(quán)圖中，尋找一條經(jīng)過所有節(jié)點(diǎn)，并回到原點(diǎn)的最短路。節(jié)點(diǎn)，并回到原點(diǎn)的最短路。 包含圖包含圖G的每個(gè)頂點(diǎn)的路稱為哈密頓路；閉的哈密的每個(gè)頂點(diǎn)的路稱為哈密頓路；閉的哈密頓路稱為哈密頓圈。頓路稱為哈密頓圈。 到目前為止，到目前為止，TSP問題還沒有有效解決方法，現(xiàn)有問題還沒有有效解決方法，現(xiàn)有的方法都是尋找近似最優(yōu)的哈密頓圈，常用方法有邊的方法都是尋找近似最優(yōu)的哈密頓圈，常用方法有邊替換法、遺傳算法、模擬退火法、蟻群算法等。替換法、遺傳算法、模擬退火法、蟻群算法等。.21引入引入0-1變量：變量：xij=1

17、，由第，由第i城市進(jìn)入第城市進(jìn)入第j城市，且城市，且i j0，其它，其它 目標(biāo)函數(shù)：目標(biāo)函數(shù)： niniijijxcz11min對規(guī)模不大的對規(guī)模不大的TSP問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：, 11 niijx j=1,2,3,n, 11 njijx i=1,2,3,n.22123456到此得到了一個(gè)模型，它是一個(gè)指派問題的整數(shù)規(guī)到此得到了一個(gè)模型，它是一個(gè)指派問題的整數(shù)規(guī)劃模型。但以上兩個(gè)條件對于劃模型。但以上兩個(gè)條件對于TSPTSP來說并不充分，來說并不充分，僅僅是必要條件。僅僅是必要條件。例如：例如：以上兩個(gè)條件都滿足，但它顯然不是以上兩個(gè)條件都滿足，但它顯然

18、不是TSPTSP的解，的解，它存在兩個(gè)子巡回。它存在兩個(gè)子巡回。則可以避免產(chǎn)生子巡回。則可以避免產(chǎn)生子巡回。若在原模型上添加變量若在原模型上添加變量ui ，并附加下面形式的約束條件：并附加下面形式的約束條件：，1 nnxuuijji. 12 nji, 20 nui.23目標(biāo)函數(shù)：目標(biāo)函數(shù)： niniijijxcz11min s.t：, 11 niijx, 11 njijx, 1 nnxuuijji,2nji , 20 nui i=2,3,n, 1 , 0 ijx i,j=1,2,3,n j=1,2,3,n i=1,2,3,nTSP問題的數(shù)學(xué)規(guī)劃模型：問題的數(shù)學(xué)規(guī)劃模型：.24例例7.2 (TS

19、P問題問題) 已知已知9個(gè)城市間的旅行費(fèi)用（見表）個(gè)城市間的旅行費(fèi)用（見表）問他應(yīng)按怎樣的次序訪問這些城市，能使得總旅費(fèi)最問他應(yīng)按怎樣的次序訪問這些城市，能使得總旅費(fèi)最少？少？ 0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.3, 5.9, 3.1, 0, 4.8, 8.1, 9.3, 8.7, 6.4, 4.5, 7.2, 5.2, 4.8, 0, 7.7, 9.5, 4.9, 5.3, 6.6, 6.8, 4.3, 8.1, 7.7, 0, 7.3, 11.2, 10.8,9.7, 8.8, 5.2, 9.3, 9.5, 7.3, 0, 10.5, 11.3,7.9,

20、 9.4, 6.5, 8.8, 4.9, 11.2,10.5, 0, 6.1, 5.8, 7.5, 8.8, 6.4, 5.3, 10.8,11.3, 6.1, 0, 6.6, 4.9, 7.3, 4.5, 6.6, 9.7, 7.9, 5.8, 6.6, 0, 5.8, 5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;城市編號(hào)城市編號(hào) 1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9.25 9191miniiijijxcz s.t：, 191 iijx, 191 jijx, 89 ijjixuu, 70 iu, 1 , 0 ijx ,

21、ji ),92( ji, ji i,j=1,2,3,nsets: city /1.9/:u; link(city,city):c,x; endsets OBJmin=sum(link:c*x); for(city(j):sum(city(i)|i#ne#j:x(i,j)=1);for(city(i):sum(city(j)|j#ne#i:x(i,j)=1); for(city(i)|i#gt#1:for(city(j)|j#gt#1#and#i#ne#j: u(i)-u(j)+9*x(i,j)=8); for(city(i)|i#gt#1:u(I)=0);for(link:bin(x);.26

22、data: c=0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.3, 5.9, 3.1, 0, 4.8, 8.1, 9.3, 8.7, 6.4, 4.5, 7.2, 5.2, 4.8, 0, 7.7, 9.5, 4.9, 5.3, 6.6, 6.8, 4.3, 8.1, 7.7, 0, 7.3, 11.2, 10.8,9.7, 8.8, 5.2, 9.3, 9.5, 7.3, 0, 10.5, 11.3,7.9, 9.4, 6.5, 8.8, 4.9, 11.2,10.5, 0, 6.1, 5.8, 7.5, 8.8, 6.4, 5.3, 10.8,11.3, 6.1,

23、0, 6.6, 4.9, 7.3, 4.5, 6.6, 9.7, 7.9, 5.8, 6.6, 0, 5.8, 5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;enddata.27Objective value: 49.10000X( 1, 4) 1.000000X( 2, 1) 1.000000 X( 3, 2) 1.000000X( 4, 5) 1.000000 X( 5, 8) 1.000000 X( 6, 3) 1.000000 X( 7, 6) 1.000000 X( 8, 9) 1.000000 X( 9, 7) 1.000000 按如下次序：按

24、如下次序： 1,4,5,8,9,7,6,3,2,1 訪問這些城市時(shí)總訪問這些城市時(shí)總費(fèi)用最小，最小費(fèi)費(fèi)用最小，最小費(fèi)用：用：49.1.28 ei與與vi-1和和vi關(guān)聯(lián)，稱關(guān)聯(lián)，稱 為圖為圖G的的四、最短路四、最短路問題問題道路與軌道：在圖道路與軌道：在圖G(V,E)中，設(shè)中，設(shè)ttveevevP2110 一條道路，一條道路，k為路長，為路長，v0為道路為道路P的起點(diǎn)的起點(diǎn)vt為終點(diǎn)，為終點(diǎn)，各邊相異的道路稱為行跡，各邊相異的道路稱為行跡，頂點(diǎn)不同且邊也不同的道路稱為軌道（路徑）。頂點(diǎn)不同且邊也不同的道路稱為軌道（路徑）。 最短路問題：對賦權(quán)圖最短路問題：對賦權(quán)圖G(V,E,W)，在連接指定，

25、在連接指定起點(diǎn)起點(diǎn)v0與終點(diǎn)與終點(diǎn)vt的所有軌道的所有軌道P中，尋找一條權(quán)數(shù)之和中，尋找一條權(quán)數(shù)之和最小的軌道。最小的軌道。),(),(GEeGVvii .29數(shù)學(xué)模型：數(shù)學(xué)模型： 設(shè)圖設(shè)圖G(V,E,W), 頂點(diǎn)頂點(diǎn)v0,vtV, 邊邊 e E ，w(e)為邊為邊e的權(quán)數(shù)，的權(quán)數(shù)，P(v0,vt)是起點(diǎn)為是起點(diǎn)為v0終點(diǎn)為終點(diǎn)為vt為任意一條軌道，為任意一條軌道，所有這些軌道的全體記為：所有這些軌道的全體記為：S(P)W(P)為軌道為軌道P(v0,vt)上各邊的權(quán)數(shù)之和，上各邊的權(quán)數(shù)之和，)(min),()(0*PWvvPWPSPt 最短路問題需要求出：最短路問題需要求出：（1）權(quán)數(shù)之和最小

26、的軌道（）權(quán)數(shù)之和最小的軌道（2）該軌道的權(quán)數(shù)之和）該軌道的權(quán)數(shù)之和求解此問題的方法有：求解此問題的方法有：Dijkstra算法、算法、floyd算法，遺算法，遺傳算法、模擬退火、蟻群算法等。傳算法、模擬退火、蟻群算法等。.30Dijkstra算法：（算法具體內(nèi)容略）算法：（算法具體內(nèi)容略） 是用來求指定兩點(diǎn)是用來求指定兩點(diǎn)A與與B之間的最短路的，之間的最短路的， 在在matlab中使用命令中使用命令graphshortestpath實(shí)現(xiàn)。實(shí)現(xiàn)。調(diào)用格式：調(diào)用格式：dist,path=graphshortestpath(DG,A,B) dist： A與與B之間的最短路的長度之間的最短路的長度

27、path： A與與B之間的最短路的路徑之間的最短路的路徑 DG：權(quán)數(shù)鄰接矩陣：權(quán)數(shù)鄰接矩陣由權(quán)數(shù)鄰接矩陣畫圖的命令：由權(quán)數(shù)鄰接矩陣畫圖的命令： view(biograph(DG,ShowWeights,on).31例例7.3 某地某地10個(gè)點(diǎn)個(gè)點(diǎn)v1,v2,v10間的道路連接情況為：間的道路連接情況為：相鄰點(diǎn)相鄰點(diǎn) 距離距離 相鄰點(diǎn)相鄰點(diǎn) 距離距離 相鄰點(diǎn)相鄰點(diǎn) 距離距離 相鄰點(diǎn)相鄰點(diǎn) 距離距離12: 4.2， 13: 5.6， 14: 6.5 23: 3.5， 25: 6.5， 27: 15.2 34: 3.8， 35: 5.4， 36: 7.645: 5.1 ， 46: 5.1， 47:

28、8.8， 48: 12.356: 4.7 ， 57: 5.2， 59: 7.667: 6.3， 68: 3.9， 69: 5.278: 6.9， 79: 3.5， 710: 6.389: 6.8， 810: 5.9，910: 5.8 求由求由v1到到v10間的最短路。間的最短路。.32clc,clearx=1:8,1:8,1:7,9,4,10;y=2:9,3,5,5:10,4,7,6,7,9,9,10,10,8,10; w=4.2,3.5,3.8,5.1,4.7,6.3,6.9,6.8,5.6,6.5,5.4,5.1,5.2,3.9,3.5,5.9,6.5,15.2,7.6,8.8,7.6,5

29、.2,6.3,5.8,12.3,0;相鄰點(diǎn)相鄰點(diǎn) 距離距離 相鄰點(diǎn)相鄰點(diǎn) 距離距離 相鄰點(diǎn)相鄰點(diǎn) 距離距離 相鄰點(diǎn)相鄰點(diǎn) 距離距離12: 4.2， 13: 5.6， 14: 6.5 23: 3.5， 25: 6.5， 27: 15.2 34: 3.8， 35: 5.4， 36: 7.645: 5.1 ， 46: 5.1， 47: 8.8， 48: 12.356: 4.7 ， 57: 5.2， 59: 7.667: 6.3， 68: 3.9， 69: 5.278: 6.9， 79: 3.5， 710: 6.389: 6.8， 810: 5.9，910: 5.8 .33W=sparse(x,y,w

30、);B=W+W;dist,path=graphshortestpath(B,1,10)ids=v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;h=view(biograph(W,ids,ShowArrows,off,ShowWeights,on)set(h.Nodes(path),Color,1,0.5,0.5)edges=getedgesbynodeid(h,get(h.Nodes(path),ID);set(edges,LineColor,0,1,0)set(edges,LineWidth,2) .34 4.2 5.6 6.5 3.5 6.5 15.2 3.8 5.4 7.6

31、 5.1 5.1 8.8 12.3 4.7 5.2 7.6 6.3 3.9 5.2 6.9 3.5 6.3 6.8 5.9 5.8 v1v2v3v4v5v6v7v8v9v10dist = 21.4000path = 1 4 6 8 10.35floyd算法：算法：設(shè)圖設(shè)圖G(V,E,W)的權(quán)鄰接矩陣為：的權(quán)鄰接矩陣為：其中其中 當(dāng)當(dāng)vi與與vj之間沒有邊相連時(shí)，取之間沒有邊相連時(shí)，取 當(dāng)當(dāng)vi與與vj之間有邊時(shí)，取之間有邊時(shí)，取 wij 為該邊的權(quán)。為該邊的權(quán)。對于無向圖對于無向圖G，鄰接矩陣，鄰接矩陣D0是對稱矩陣。是對稱矩陣。 nnijdD )()0(0)0(ijd )0(ijd，ijij

32、wd )0(.36(3)遞推產(chǎn)生一個(gè)矩陣序列遞推產(chǎn)生一個(gè)矩陣序列D0, D1, Dn(4) 為最短路距離矩陣，為最短路距離矩陣，floyd算法的步驟：算法的步驟：（求有（求有n個(gè)節(jié)點(diǎn)的圖的最短路距離矩陣個(gè)節(jié)點(diǎn)的圖的最短路距離矩陣Dn的步驟）的步驟）(1)初值初值k=0，nnijdD )()0(0( )(1)(1)(1)min,)kkkkijijikkjddddnnnijndD )()()(nijd為為vi到到vj的最短路的距離。的最短路的距離。(2)計(jì)算計(jì)算.37建立最短路徑矩陣建立最短路徑矩陣R的步驟：的步驟：（1） ,)()0()0(nnijrR jrij )0( , )2()1()(ki

33、jkijrkr(1)(1)(1)kkkijikkjddd(1)(1)(1)kkkijikkjddd(3)遞推產(chǎn)生一個(gè)矩陣序列遞推產(chǎn)生一個(gè)矩陣序列R0,R1,Rn(4)矩陣矩陣R=Rn為最短路徑矩陣為最短路徑矩陣.38查找最短路路徑的方法：查找最短路路徑的方法：若若 則則 是是點(diǎn)點(diǎn)vi與到點(diǎn)與到點(diǎn)vj最短路徑的途中點(diǎn)，最短路徑的途中點(diǎn)，1)(arnij 1av(1) 向起點(diǎn)向起點(diǎn)vi與追溯：與追溯：，1)(arnij ，2)(1arnia ， 3)(2arnia ( )kniakra 得：得：12,aaaivvvvk(2) 向終點(diǎn)向終點(diǎn)vj與追溯：與追溯：，1)(arnij ，1)(1brnja

34、 ,2)(1，brnjb ，jrnjbm )(得：得：jbbbavvvvvm,211(3)點(diǎn)點(diǎn)vi與到點(diǎn)與到點(diǎn)vj最短路路徑：最短路路徑：jbbbaaaivvvvvvvvmk,2112.39例例7.4 求右圖中加權(quán)圖的求右圖中加權(quán)圖的任意兩點(diǎn)間的最短距離任意兩點(diǎn)間的最短距離與最短路徑與最短路徑. 12356465854367669 )0(D,654321654321654321654321654321654321 )0( R0, 4, 5, , 6, 64, 0, , , 35, , 0, 8, 5, , 8, 0, 6, 96, , 5, 6, 0, 76, 3, , 9, 7, 0.40

35、)1(D )1(R )0(D0, 4, 5, , 6, 64, 0, , , 35, , 0, 8, 5, , 8, 0, 6, 96, , 5, 6, 0, 76, 3, , 9, 7, 0,min)1()1()1()( kkjkikkijkijdddd(1) k=1: 0, 4, 5, , 6, 64, 0, 9, ,10, 35, 9, 0, 8, 5, 11, 8, 0, 6, 96, 10, 5, 6, 0, 76, 3, 11, 9, 7, 0 1 2 3 4 5 6 1 2 1 4 1 6 1 1 3 4 5 1 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5

36、 6(0)R 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6.41 )1(D0, 4, 5, , 6, 64, 0, 9, ,10, 35, 9, 0, 8, 5, 11, 8, 0, 6, 96, 10, 5, 6, 0, 76, 3, 11, 9, 7, 0,min)1()1()1()( kkjkikkijkijdddd(2) k=2: 得得: ,)1()2()1()2(RRDD )1(R 1 2 3 4 5 6 1 2 1 4 1 6 1 1 3 4 5 1 1 2 3 4 5 6 1 1 3

37、 4 5 6 1 2 1 4 5 6.42(2)R 1 2 3 4 5 6 1 2 1 4 1 6 1 1 3 4 5 1 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 )2(D0, 4, 5, , 6, 64, 0, 9, ,10, 35, 9, 0, 8, 5, 11, 8, 0, 6, 96, 10, 5, 6, 0, 76, 3, 11, 9, 7, 0,min)1()1()1()( kkjkikkijkijdddd(3) k=3: )3(D 0 4 5 13 6 6 4 0 9 17 10 3 5 9 0 8 5 11 13 17 8 0 6 9 6 10

38、5 6 0 7 6 3 11 9 7 0 )3(R 1 2 3 3 5 6 1 2 1 3 1 6 1 1 3 4 5 1 3 3 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6.43,min)1()1()1()( kkjkikkijkijdddd(4) k=4: 得得: ,)3(4)()3()4(RRDD )3(R 1 2 3 3 5 6 1 2 1 3 1 6 1 1 3 4 5 1 3 3 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 )3(D 0 4 5 13 6 6 4 0 9 17 10 3 5 9 0 8 5 11 13 17 8 0 6 9 6

39、 10 5 6 0 7 6 3 11 9 7 0.44(4)R 1 2 3 3 5 6 1 2 1 3 1 6 1 1 3 4 5 1 3 3 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6(4)D 0 4 5 13 6 6 4 0 9 17 10 3 5 9 0 8 5 11 13 17 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,min)1()1()1()( kkjkikkijkijdddd(5) k=5: )5(D 0 4 5 12 6 6 4 0 9 16 10 3 5 9 0 8 5 11 12 16 8 0 6 9 6 10 5 6 0 7

40、6 3 11 9 7 0 )5(R 1 2 3 5 5 6 1 2 1 5 1 6 1 1 3 4 5 1 5 5 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6.45 )5(D 0 4 5 12 6 6 4 0 9 16 10 3 5 9 0 8 5 11 12 16 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0 )5(R 1 2 3 5 5 6 1 2 1 5 1 6 1 1 3 4 5 1 5 5 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,min)1()1()1()( kkjkikkijkijdddd(6) k=6: )6(D

41、0 4 5 12 6 6 4 0 9 12 10 3 5 9 0 8 5 11 12 12 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0 )6(R 1 2 3 5 5 6 1 2 1 6 1 6 1 1 3 4 5 1 5 6 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6.46 )6(R 1 2 3 5 5 6 1 2 1 6 1 6 1 1 3 4 5 1 5 6 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6 )6(D 0 4 5 12 6 6 4 0 9 12 10 3 5 9 0 8 5 11 12 12 8 0 6 9 6 10

42、 5 6 0 7 6 3 11 9 7 012356465854367669故從故從v4到到v2的最短路：的最短路： ,12)6(24 d, 6)6(24 r途中點(diǎn)途中點(diǎn):v6 , 6)6(46 r從從v6向前追溯：向前追溯： 得得: v4 v6 .47 )6(D 0 4 5 12 6 6 4 0 9 12 10 3 5 9 0 8 5 11 12 12 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0 )6(R 1 2 3 5 5 6 1 2 1 6 1 6 1 1 3 4 5 1 5 6 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 612356465854

43、367669得得: v4 v6 從從v6向后追溯：向后追溯： , 2)6(62 r得得: v4 v6 v2.48floyd算法的程序?qū)崿F(xiàn)方法：算法的程序?qū)崿F(xiàn)方法：(1)輸入帶權(quán)的鄰接矩陣：輸入帶權(quán)的鄰接矩陣：nnjiwW ),(2)賦初值：對所有的賦初值：對所有的i與與j，d(i,j) w(i,j), r(i,j)j, k 1(3)更新更新d(i,j)與與r(i,j)：對所有的：對所有的i與與j，若，若d(i,k)+d(k,j)d(i,j) ,則則d(i,j) d(i,k)+d(k,j), r(i,j)k (4)若若k=n停止；否則停止；否則kk+1 轉(zhuǎn)轉(zhuǎn)(3).49例例7.5 出租車的最短行

44、駛路線問題出租車的最短行駛路線問題某地的出租車公司為了更好地服務(wù)，向顧客承諾某地的出租車公司為了更好地服務(wù)，向顧客承諾“出出租車走最短的行駛路線，方便快捷。租車走最短的行駛路線，方便快捷?！背丝蜕宪嚭蟾娉丝蜕宪嚭蟾嬷緳C(jī)目的地，出租車電腦就可以計(jì)算出到達(dá)目的地知司機(jī)目的地，出租車電腦就可以計(jì)算出到達(dá)目的地的最短行駛路線，下圖給出該地的交通路線示意圖，的最短行駛路線，下圖給出該地的交通路線示意圖，要求：要求：(1)編寫用編寫用floyd算法求算法求50個(gè)節(jié)點(diǎn)中任意兩個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)中任意兩個(gè)節(jié)點(diǎn)間的最短路徑間的最短路徑matlab函數(shù)。函數(shù)。(2)調(diào)用所編寫的函數(shù)，求出從標(biāo)號(hào)為調(diào)用所編寫的函數(shù)，求出

45、從標(biāo)號(hào)為22的地點(diǎn)到標(biāo)號(hào)的地點(diǎn)到標(biāo)號(hào)為為44的地點(diǎn)的最短行駛路線。的地點(diǎn)的最短行駛路線。.50150 7 .51function d,path=floydg(a,sp,ep)n=size(a,1);D=a;R=zeros(n);for j=1:n R(:,j)=j;endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=k; end end endend解解(1).52c0=R(sp,ep);L1=c0;c=c0;while R(sp,c)=c c=R(sp,c);L1=c,L1;

46、endb=c0;L2=;while R(b,ep)=ep b=R(b,ep); L2=L2,b;endd=D(sp,ep);path=sp,L1,L2,ep;end.53(2) 輸入帶權(quán)的鄰接矩陣：輸入帶權(quán)的鄰接矩陣：D命令窗口：命令窗口：d,path=floydg(D,22,44)d = 2410path = Columns 1 through 12 22 24 28 31 33 38 41 42 43 47 45 44 .54五、最小生成樹五、最小生成樹問題問題1v樹：樹： 連通且不含圈的無向圖稱為連通且不含圈的無向圖稱為樹樹常用常用T表示表示.樹中的邊稱為樹中的邊稱為樹枝樹枝. 樹中度為

47、樹中度為1的頂點(diǎn)稱為的頂點(diǎn)稱為樹葉樹葉. 2v3v4v5v支撐樹：支撐樹： 設(shè)圖設(shè)圖G(V,E)，若，若T是樹，是樹，且且稱樹稱樹T是圖是圖G的支撐（生成）樹。的支撐（生成）樹。 ( )( ), ( )( )E TE G V TV G ，最小生成樹：賦權(quán)連通圖最小生成樹：賦權(quán)連通圖G的所有支撐樹中，其各邊的所有支撐樹中，其各邊權(quán)之和最小的支撐樹，稱為連通圖權(quán)之和最小的支撐樹，稱為連通圖G的最小生成樹。的最小生成樹。解決最小生成樹的常用方法：克魯斯卡爾算法、普利解決最小生成樹的常用方法：克魯斯卡爾算法、普利姆算法。姆算法。.55普利姆（普利姆（Prim）算法：）算法： 設(shè)置兩個(gè)集合設(shè)置兩個(gè)集合P

48、和和Q，其中，其中P、Q分別用于存放最分別用于存放最小生成樹的頂點(diǎn)和邊，小生成樹的頂點(diǎn)和邊，P的初值為的初值為P=v1，Q的初值為的初值為Q=。 普利姆算法的基本思想：從所有普利姆算法的基本思想：從所有的邊中，選取一條具有最小權(quán)值的邊的邊中，選取一條具有最小權(quán)值的邊uv，將頂點(diǎn)，將頂點(diǎn)v加加入到集合入到集合P中，將邊中，將邊uv加入到集合加入到集合Q中，不斷重復(fù)下去，中，不斷重復(fù)下去，直到直到P= =V中止。中止。PVvPu ,.56普利姆（普利姆（Prim）算法：）算法： 設(shè)置兩個(gè)集合設(shè)置兩個(gè)集合T和和Q，其中，其中T、Q分別用于存放最分別用于存放最小生成樹的頂點(diǎn)和邊，小生成樹的頂點(diǎn)和邊，T的初值為的初值為T=v1，Q的初值為的初值為Q=。普利姆算法的基本思想：普利姆算法的基本思想：從所有