1、1,圖與網(wǎng)絡(luò)分析Graph Lsr+drp，則對(duì)p點(diǎn)標(biāo)號(hào)，并將Lsp的值標(biāo)注在p點(diǎn)旁的小方框內(nèi)； 重復(fù)第3步，一直到t點(diǎn)得到標(biāo)號(hào)為止。,43,Dijkstra算法舉例,例3 求下圖中從v1到v7的最短路,圖 6-10,44,解題-1,（1）從點(diǎn)v1出發(fā)，對(duì)v1標(biāo)號(hào)，將L11=0標(biāo)注在v1旁的小方框內(nèi)。令 ，其余點(diǎn)屬于 。,V,45,(2)同v1相鄰的未標(biāo)號(hào)點(diǎn)有v2、v3。L1r=mind12,d13=min5,2=2=L13,即對(duì)點(diǎn)v3標(biāo)號(hào)，將L13的值標(biāo)注在v3旁的小方框內(nèi)。將v1,v3加粗，并令,解題-2,，,46,(3)同標(biāo)號(hào)點(diǎn)v1、v3相鄰的點(diǎn)有v2、v4、v6，故有 對(duì)v2點(diǎn)標(biāo)號(hào)，將

2、L12的值標(biāo)注在v2點(diǎn)旁的小方框內(nèi)，將v1,v2加粗，并令，,解題-3,，,(c),47,解題-4,(4)同標(biāo)號(hào)點(diǎn)v1、v2、v3相鄰的點(diǎn)有v5、v4、v6，有 故對(duì)點(diǎn)v6標(biāo)號(hào)，將L16的值標(biāo)注在v6點(diǎn)旁的小方框內(nèi)，將v3, v6加粗，并令，,48,解題-5,(5)同標(biāo)號(hào)點(diǎn)v1、v2、v3、v6相鄰的點(diǎn)有v4、v5、v7，有 故對(duì)點(diǎn)v4和v5同時(shí)標(biāo)號(hào)，將L14=L15=7的值分別標(biāo)注在v4和v5點(diǎn)旁的小方框內(nèi)，將v2,v4及v6,v5加粗，并令，,，,49,解題-6,同各標(biāo)號(hào)點(diǎn)相鄰的未標(biāo)號(hào)點(diǎn)只有v7，因有 故在點(diǎn)v7旁小方框內(nèi)標(biāo)注L17=10，加粗v6,v7 。圖(f)中的粗線表明從點(diǎn)v1到網(wǎng)

3、絡(luò)中其它各點(diǎn)的最短路，各點(diǎn)旁方框中的數(shù)字是從v1點(diǎn)到各點(diǎn)的最短距離。,10,50,矩陣算法,Dijkstra算法提供了從網(wǎng)絡(luò)圖中某一點(diǎn)到其它點(diǎn)的最短距離。 但實(shí)際問題中往往要求網(wǎng)絡(luò)任意兩點(diǎn)之間的最短距離，如果仍采用Dijkstra算法對(duì)各點(diǎn)分別計(jì)算，就顯得很麻煩。 求網(wǎng)絡(luò)各點(diǎn)間最短距離矩陣計(jì)算法。,51,矩陣算法舉例,在圖6-10中用矩陣計(jì)算法求各點(diǎn)之間的最短距離,圖 6-10,52,解題-1,定義dij為圖中兩相鄰點(diǎn)的距離，令,=,53,解題-2,上面矩陣表明從i點(diǎn)到j(luò)點(diǎn)的直接最短距離。但從i到j(luò)的最短路不一定是ij，可能是ilj，ilkj，或ilkj。 先考慮i與j之間有一個(gè)中間點(diǎn)的情況，

4、如圖6-10中v1v2的最短距離應(yīng)為mind11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72，也即mind1r+dr2。,54,解題-3,為此可以構(gòu)造一個(gè)新的矩陣D(1)，令D(1)中每個(gè)元素 則矩陣D(1)給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)和包括經(jīng)一個(gè)中間點(diǎn)時(shí)的最短距離,55,解題-4,再構(gòu)造矩陣D(2)。令 則D(2)給出網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)，及包括經(jīng)過一至三個(gè)中間點(diǎn)時(shí)的最短距離。,56,解題-5,再構(gòu)造矩陣D(3)。令 則D(3)給出網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)，及包括經(jīng)過一至四個(gè)中間點(diǎn)時(shí)的最短距離。 計(jì)算可得：D(2)= D

5、(3) D(3)各個(gè)元素值即為各點(diǎn)間最短距離,57,一般地有 矩陣D(k)給出網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)，經(jīng)過一個(gè)、兩個(gè)到（2k-1）個(gè)中間點(diǎn)到達(dá)時(shí)比較得到的最短距離。 設(shè)網(wǎng)絡(luò)圖有p個(gè)點(diǎn)，則一般計(jì)算到不超過D(k)，k的值按式 計(jì)算 即 如果計(jì)算中出現(xiàn)D(m+1)=D(m)時(shí)，計(jì)算即可結(jié)束，矩陣中D(m)的各個(gè)元素值即為各點(diǎn)間最短距離。 本例中， 所以最多計(jì)算到D(3)，,58,例5,假定圖6-10中v1、v2、v3、v4、v5、v6、v7為七個(gè)村子，決定要聯(lián)合辦一所小學(xué)。 已知各村的小學(xué)生人數(shù)分別為v1 -30， v2 -40， v3 -25， v4 -20， v5 -50， v6 -60，

6、 v7 -60， 則小學(xué)應(yīng)建在哪一個(gè)村子，使小學(xué)生上學(xué)走的總路程為最短？,59,解題,將上例中計(jì)算得到的D（3）的第一行乘v1村的小學(xué)生人數(shù)，則乘積數(shù)字為假定小學(xué)建于各個(gè)村時(shí)， v1村小學(xué)生上學(xué)單程所走路程。 將D（3）第二行數(shù)字乘v2村小學(xué)生人數(shù)，得小學(xué)建于各個(gè)村子時(shí)， v2村小學(xué)生上學(xué)所走路程。 依此類推可計(jì)算得到下表。,60,決策方案：小學(xué)應(yīng)建在v6村,小學(xué)建于vi村時(shí)，7個(gè)村子的學(xué)生累計(jì)的一次單程上學(xué)路程。,61,應(yīng)用舉例設(shè)備更新問題,某企業(yè)使用一臺(tái)設(shè)備，在每年年初，企業(yè)領(lǐng)導(dǎo)部門需要決定 是購(gòu)置新的還是繼續(xù)使用舊的； 若購(gòu)置新設(shè)備需支付一定的購(gòu)置費(fèi)用，若繼續(xù)使用舊的，須支付一定的維修費(fèi)

7、用。 問題是：如何制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得總的支出費(fèi)用最少。,62,63,用點(diǎn)vi表示“第i年年初購(gòu)進(jìn)一臺(tái)設(shè)備”；用弧（vi，vj）表示在第i年年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初。則問題成為最短路徑問題。,16,16,17,17,18,22,30,41,59,22,30,41,23,31,23,64,中國(guó)郵路問題,第四節(jié),65,問題提出,一個(gè)郵遞員從郵局出發(fā)，走遍他負(fù)責(zé)投遞的每一條街道，然后再返回郵局，問應(yīng)選擇什么樣的路線，使走的路程為最短。 因這個(gè)問題最早由中國(guó)數(shù)學(xué)工作者提出（1962年管梅谷提出），故稱中國(guó)郵路問題。,66,哥尼斯堡七橋問題,一個(gè)散步者能否走過七座橋，且每次只走

8、過一次，最后回到出發(fā)點(diǎn)。,普雷格爾河,67,歐拉“一筆畫問題”,68,歐拉圖,歐拉回路： 連通圖G中，若存在一條回路，經(jīng)過每邊一次且僅一次，稱這條回路為歐拉回路。 歐拉圖：具有歐拉回路的圖。 可以證明，連通圖G是歐拉圖的充分必要條件是圖中的點(diǎn)全為偶點(diǎn)。 某圖如能一筆畫出，此圖必為歐拉鏈或歐拉圈 能否一筆畫：連通圖中只有小于等于2個(gè)的奇點(diǎn)。 基于歐拉圖和歐拉回路的概念，結(jié)合例子討論郵遞員的最短投遞路線問題。,69,例6,設(shè)某郵遞員負(fù)責(zé)投遞的街道如圖6-12所示，要求找出該郵遞員的最短投遞路線。 如果投遞路線圖中沒有奇點(diǎn)，可以走到?jīng)]有重復(fù)路線的最短路徑。 奇點(diǎn)幾個(gè)？,70,解題-1,若圖6-12是

9、歐拉圖，則圖中的歐拉回路就是郵遞員的最短投遞路線。 否則將圖轉(zhuǎn)化成歐拉圖， 轉(zhuǎn)化方法：將圖中奇點(diǎn)兩兩相連，變成偶點(diǎn)，則包括連線在內(nèi)的圖構(gòu)成歐拉圖，而連線的長(zhǎng)度就是郵遞員要在街道上重復(fù)走的路。,71,解題-2,郵遞員重復(fù)走的路最短，就是要使奇點(diǎn)兩兩之間的連線最短，為此奇點(diǎn)間的連線應(yīng)符合下列條件： (a)每條邊上最多重復(fù)一次； (b)在圖G的每個(gè)回路上，有重復(fù)的邊的長(zhǎng)度不超過回路總長(zhǎng)的一半。,72,圖 6-13,解題-3,圖6-12不是歐拉圖，圖上有8個(gè)奇點(diǎn)(用號(hào)標(biāo)示)，說明郵遞員必須要在某些區(qū)段重復(fù)走，才能走遍所有負(fù)責(zé)投遞的街道。 將奇點(diǎn)兩兩連結(jié)(用虛線表示，圖6-13)，則所有奇點(diǎn)都成了偶點(diǎn)。 因此包括虛線在內(nèi)的線路郵遞員可走遍而做到不重復(fù)。如圖所示為其一。,73,解題-4,為使郵遞員重復(fù)走的路程也即虛線的長(zhǎng)度為最短，可根據(jù)上述條件(a)和(b)進(jìn)行調(diào)整。 (a)每條邊上最多重復(fù)一次； (b)在圖G的每個(gè)回路上，有重復(fù)的邊的長(zhǎng)度不超過回路總長(zhǎng)的一半。,圖 6-13,74,解題-4,在回路v4,v5,v11,v10,v4中，虛線長(zhǎng)度超過回路長(zhǎng)度一半，故改將v4與v5連結(jié)，v11與v12連結(jié)。 又在回路v2,v3,v9,v6,v2中，同樣虛線長(zhǎng)超過回路長(zhǎng)度一半，故可將虛線標(biāo)到回路的另