圖的最短路徑課件

1、1圖的最短路徑1圖的最短路徑2最 短 路 徑一、最短路徑 從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)最短路徑長(zhǎng)度，稱為最短路徑。2最 短 路 徑3 從源點(diǎn)Vi到終點(diǎn)Vj的每條路徑上的權(quán)（它等于該路徑上所經(jīng)邊上的權(quán)值之和，稱為該路徑的帶權(quán)路徑長(zhǎng)度）可能不同，我們把權(quán)值最小的那條路徑稱為最短路徑。 例如：圖中V1到V5共有三條路徑： (v1,v5),(v1,v2,v3,v5),(v1,v2,v4,v5),其帶權(quán)路徑長(zhǎng)度分別為30，23和38，其最短路徑為23。3 從源點(diǎn)Vi到終點(diǎn)Vj的每條路徑上的權(quán)（它等于該路4二、從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑 1、算法的基本思想：廣度優(yōu)先遍歷方法。 最短路徑是指由n個(gè)頂點(diǎn)e條邊

2、組成的圖G，從某個(gè)頂點(diǎn)Vi出發(fā)，到另一個(gè)頂點(diǎn)Vj的最短路徑。它可能是直達(dá)路徑也可能是經(jīng)過K個(gè)點(diǎn)所形成的最短路徑。4二、從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑5例題1 如圖所示6個(gè)城市之間道路聯(lián)系圖，編一個(gè)程序由計(jì)算機(jī)找到從C1城市到C6城市之間長(zhǎng)度盡可能短的一條路徑以及路徑總長(zhǎng)度。5例題1 如圖所示6個(gè)城市之間道路聯(lián)系圖，編一個(gè)程序由計(jì)算6用廣度優(yōu)先的遍歷方法求解最短路徑：（1）用鄰接矩陣存儲(chǔ)圖的結(jié)構(gòu)（2）用廣度優(yōu)先的隊(duì)列存儲(chǔ)訪問的頂點(diǎn)：（3）記錄訪問過的城市是一種搜索算法，以便找到最短的路徑6用廣度優(yōu)先的遍歷方法求解最短路徑：7頂點(diǎn)123456104800024034603830220404204

3、950624046000940問題求解的基本方法：廣度優(yōu)先算法（1）存儲(chǔ)該圖中頂點(diǎn)之間的關(guān)系和路徑長(zhǎng)度（2）從起點(diǎn)開始搜索，將訪問點(diǎn)入隊(duì)，并記錄已經(jīng)被訪問過的城市。在搜索中注意本問題中，最先找到的路徑未必是最短路徑，只是走過城市最少的路徑。7頂點(diǎn)1234561048000240346038302208（3）判斷當(dāng)前的路徑是否是最短路徑（4）輸出最短路徑的長(zhǎng)度及所訪問的過程程序說明如下：program short ; const m=6;max=32767 ; link:array1.m,1.m of integer=(0,4,8,0,0,0), (4,0,3,4,6,0), (8,3,0,2,

4、2,0), (0,4,2,0,4,9), (0,6,2,4,0,4), (0,0,0,9,4,0); 8（3）判斷當(dāng)前的路徑是否是最短路徑9type fg=set of 1.m ; var city,pnt:array1.100 of byte ; flag : array1.100 of fg ; flags:fg ; i,k,n,r,f:integer ; path :array1.10 of 1.m ; min,step:integer;procedure work ; var n,i,y,cost :integer ; s:array1.10 of 1.m ; begin y:=f ;

5、 9type fg=set of 1.m ;10 n:=0 ; cost:=0 ; while y0 do begin inc(n);sn:=y;y:=pnty ; end; for i:=n-1 downto 1 do cost:=cost+linkcitysi+1,citysi; if cost,pathi); writeln; writeln(min=,min); end; 11end;12begin min:=max ; flag1:=1 ; city1:=1 ; n:=0 ;pnt1:=0 ; r:=1 ;f:=0; repeat inc(f); k:=cityf; if km th

6、en begin flags:=flagf ; for j:= 2 to m do if (not( j in flags ) and (linkk,j0 ) then begin inc(r); cityr:=j; flagr:=flags+j; pntr:=f ; 12begin13 if f=m then work ; end; end;until f =r ； print ; readln ; end.13 if f=m then work 14Dijktra 算法：荻（杰）克斯特拉 （1） 從源點(diǎn)Vi到其余每個(gè)頂點(diǎn)的最短路徑的升序依次求出從源點(diǎn)到各頂點(diǎn)最短路徑長(zhǎng)度。 （2）每次求出從

7、源點(diǎn)Vi到一個(gè)終點(diǎn)Vj的最短路徑后，要以Vj作為新考慮的中間點(diǎn)，用Vi到Vj的最短路徑長(zhǎng)度和Vi到其它尚未求出最短路徑的那些終點(diǎn)的當(dāng)前最短路徑長(zhǎng)度進(jìn)行比較、修改，使它成為當(dāng)前新的最短路徑長(zhǎng)度，當(dāng)進(jìn)行n-2次后算法結(jié)束。14Dijktra 算法：荻（杰）克斯特拉15如圖所示：（1）設(shè)置一個(gè)集合數(shù)組S，作用是標(biāo)記已經(jīng)求得最短路徑的終點(diǎn)號(hào)，初始值只有一個(gè)源點(diǎn)，每找到一個(gè)最短路徑的終點(diǎn)，將該終點(diǎn)并入S集合中，以便作為新的中間點(diǎn)。若選取為1否則為0（2）設(shè)置數(shù)組dist，該數(shù)組的第j個(gè)元素distj用來保存從源點(diǎn)Vi到Vj的目前最短邊的路徑長(zhǎng)度。15如圖所示：16（3）設(shè)置path為集合數(shù)組，存放最短路

8、徑經(jīng)過的頂點(diǎn)集合。對(duì)于前面圖的結(jié)構(gòu)，假設(shè)從V1出發(fā)到各個(gè)頂點(diǎn)的最短路徑，其開始數(shù)組S，DIST，PATH的值如下： 100000330V1V1，V2V1，V5 S DISTPATH 1 2 3 4 516（3）設(shè)置path為集合數(shù)組，存放最短路徑經(jīng)過的頂點(diǎn)集合17 第一次遍歷： 1 2 3 4 51100003281130V1V1,V2V1,V2,V3V1,V2,V4V1,V5S DISTPATH17 第一次遍歷：1100003281130V1V1,V2V18 第二次遍歷： 1 2 3 4 51101003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5S

9、 DISTPATH18 第二次遍歷：1101003151123V1V1,V2V19 第三次遍歷： 1 2 3 4 51111003151123V1V1,V2V1,V2,v4,V3V1,V2,V4V1,v2,V4,v5S DISTPATH19 第三次遍歷：1111003151123V1V1,V2V20經(jīng)過以上遍歷，我們得到從V1點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度以及最短路徑所經(jīng)過的頂點(diǎn)序號(hào)。算法的具體描述：Procedure dijkstra (GA,dist , path , i) ; 從源點(diǎn)vi點(diǎn)開始 being (1) for j:=1 to n do 初始化 begin if j i then

10、sj:=0 else sj:=1 ; distj:= GAI,j ; if distjmax then path j:= i+j else pathj:= ; end;20經(jīng)過以上遍歷，我們得到從V1點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度以21 for k:=1 to n-2 do 計(jì)算到各頂點(diǎn)的最短路徑 begin (a) w:=max ; m:=I; for j:=1 to n do 求出第K個(gè)終點(diǎn)Vm if (sj=0 ) and (distjw) then m:=j; w:=distj (b) if mi then sm:=1 else exit 若條件成立，把Vm并入到S集合中 ，否則剩余終點(diǎn)路

11、最短徑長(zhǎng)度均為max 21 for k:=1 to n-2 do 22 (c) for j:=1 to n do 調(diào)整路徑 if (sj=0) and (distm+GAm,j distj ) then begin distj:=distm+GAm,j ; pathj:=pathm+j ; end ; end ; 算法的時(shí)間復(fù)雜性：O（n2 ） 若要輸出所經(jīng)過的頂點(diǎn)，怎么辦？將Path數(shù)組定義為字符數(shù)組22 (c) for j:=1 to n 23三、每對(duì)頂點(diǎn)之間的最短路徑算法：1、用狄杰斯特拉算法2、floyed 算法 （ 弗洛伊德）23三、每對(duì)頂點(diǎn)之間的最短路徑算法：242425Proce

12、dure floyed ( GA, A, P) ; BEGIN (1) for i:=1 to n do 給路徑長(zhǎng)egin度A和路徑P賦初值 for j:=1 to n do bejin A I,j :=GAI,J ; if AI,Jmax then pI,j:= i+j else pI,j:= end;25Procedure floyed ( GA, A26(2) For k:=1 to n do for i:=1 to n do for j:=1 to n do begin if ( ik ) and ( jk) and ( ij) then if AI,k +Ak,j 0 then be

13、gin gI,l := 1; g l,i := 1 ； end; 33begin34if r 0 then begin gI,r := 1; gr,i := 1 end end; for k := 1 to n do for i := 1 to n do If i k then for j := 1 to n do if (i j) and (k j) and (gI,k + gk,j 0 then begin35 min := maxlongint; for i := 1 to n do begin s:=0; for j := 1 to n do inc(s, gI,j * wj); if

14、 s min then min := s end; writeln(min);end.35 min := maxlongint;36例題 2、 產(chǎn)生數(shù)（2002年復(fù)賽）問題描述給出一個(gè)整數(shù)n(n1030)和k個(gè)變換規(guī)則（k=15）。規(guī)則：1個(gè)數(shù)字可以變換成另一個(gè)數(shù)字規(guī)則的右部不能為零。例如：n=234，有規(guī)則（k=2）：2 53 636例題 2、 產(chǎn)生數(shù)（2002年復(fù)賽）37上面的整數(shù)234經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）：234534264564共4種不同的產(chǎn)生數(shù) 問題：給出一個(gè)整數(shù)n和k個(gè)規(guī)則求出：經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個(gè)不同的整數(shù)。僅要求輸出個(gè)數(shù)。37上面的

15、整數(shù)234經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）38輸入：鍵盤輸入，格式為：n kx1 y1x2 y2xn yn輸出：屏幕輸出，格式為：一個(gè)整數(shù)（滿足條件的個(gè)數(shù)）。樣例：輸入： 輸出：234 2 42 53 638輸入：鍵盤輸入，格式為：39問題分析：（1）數(shù)據(jù)的輸入：長(zhǎng)為30位的數(shù)只能以字符串的形式輸入，經(jīng)過轉(zhuǎn)換存入30位的整型數(shù)組中。（2） 每一位數(shù)需要逐個(gè)查找和比較、轉(zhuǎn)換，處理時(shí)用一個(gè)隊(duì)列q，開始時(shí)隊(duì)列q中只有n。（3）算法流程：front:=1;隊(duì)頭指針 rear:=1; 隊(duì)尾指針while rear=front do begin q出隊(duì)y; rear:=rear+1; 39問題分析

16、：40 根據(jù)規(guī)則，擴(kuò)展y，生成新數(shù)xi 逐個(gè)檢查xi，如果xi不在隊(duì)列q中，則xi入隊(duì)， 否則不入隊(duì)；end; 輸出front值，即為所求的個(gè)數(shù)。 數(shù)據(jù)結(jié)構(gòu)：str:string; 輸入開始的數(shù) y, y1: array1.30 of 0.9; 工作單元 q: array1.1000,1.30 of 0.9; 隊(duì)列，設(shè)長(zhǎng)度1000 front, rear : integer; 存入和取出指針 p : array1.20,1.2 of 0.9 ; 存儲(chǔ)變換規(guī)則，即pi,1pi,240 根據(jù)規(guī)則，擴(kuò)展y，生成新數(shù)xi 41program c02_3; var i,i0,j,j0,k,front,r

17、ear,lg,p1,p2: longint; q:array1.1000,1.30 of 0.9; p: array1.20,1.2 of 0.9; y,y1: array1.30 of 0.9; str: string30; b:boolean; begin readln(str); 41program c02_3;42 readln(k); for i:=1 to k do readln(pi,1,pi,2); lg:=length(str); for i:=1 to 1000 do for j:=1 to 30 do qi,j:=0; j:=1; for i:=lg downto 1 d

18、o 獲取變換前的整數(shù) begin q1,j:=ord(stri)-48; 48=ord(0) j:=j+1; end; front:=1; rear:=1;42 readln(k);43while rear=front do begin for i:=1 to 30 do yi:=qrear,i; 出隊(duì)列 rear:=rear+1; for i0:=1 to k do begin p1:=pi0,1; p2:=pi0,2; 取第i0種規(guī)則 for j0:=1 to 30 do if p1=yj0 then 可以轉(zhuǎn)換 begin for j:=1 to 30 do if jj0 then y1j

19、:=yj 43while rear=front do44else y1j:=p2; y1為轉(zhuǎn)換后的結(jié)果 b:=true; i:=1; 判斷y1在隊(duì)列中是否已存在 while b and (i=front) do begin b:=false; for j:=1 to 30 do if qi,jy1j then b:=true; if b then i:=i+1; end; 結(jié)束判重 44else 45 if b then begin front:=front+1; 入隊(duì)列 for j:=1 to 30 do qfront,j:=y1j; end； End； end; end; writeln(

20、front); end. 問題所在：超出數(shù)據(jù)所規(guī)定的范圍45 if b then begin46輸入：n=11 k=2規(guī)則： （1） 1 2 （2） 2 3 寬搜過程：46輸入：n=11 k=247隊(duì)列序號(hào)qrear出隊(duì)情況原始數(shù)據(jù)轉(zhuǎn)換規(guī)則轉(zhuǎn)換后數(shù)據(jù)入隊(duì)情況front11111221211122123121212342232112224531233156134121222732231368235222332793323238631123271312238322333992323331033程序結(jié)束47隊(duì)列qrear出隊(duì)情況原始轉(zhuǎn)換轉(zhuǎn)換后入隊(duì)情況front148 從本題運(yùn)行過程中發(fā)現(xiàn)，僅11且2

21、個(gè)規(guī)則就產(chǎn)生了9個(gè)不同的數(shù)據(jù)，如果再增加34，45，89等規(guī)則共產(chǎn)生81個(gè)不同數(shù)(12,13.) ，根據(jù)題意n1030，則最多能產(chǎn)生的數(shù)據(jù)總量9*1029。超出內(nèi)存空間，益出。 思考：能否用數(shù)學(xué)遞推公式方法 或用dijkstra 最短路徑或floyd算法數(shù)學(xué)公式：數(shù)據(jù)變換規(guī)則數(shù)*數(shù)據(jù)變換規(guī)則數(shù)， 若數(shù)據(jù)轉(zhuǎn)換是傳遞關(guān)系則： 11，2（1-2，2-3）則3*3=9 1+2，1+248 從本題運(yùn)行過程中發(fā)現(xiàn)，僅11且2個(gè)規(guī)則就產(chǎn)生了949如果n是3位數(shù)，個(gè)位數(shù)的可變總數(shù)為a1，十位數(shù)的可變總數(shù)為a2，百位數(shù)的可變總數(shù)為a3，則共產(chǎn)生a1*a2*a3個(gè)不同的數(shù)據(jù)。用ai表示整數(shù)n第i位上的數(shù)通過不限次

22、轉(zhuǎn)換可得的數(shù)字總個(gè)數(shù)（包括本身），假定n共有s位，根據(jù)乘法原理，n共能轉(zhuǎn)換為a1*a2*a3*as個(gè)不同整數(shù)。又因?yàn)閚的各個(gè)數(shù)位肯定在09之間，可先計(jì)算出09分別能轉(zhuǎn)換為多少個(gè)不同的數(shù)字，分別存儲(chǔ)到數(shù)組f0f9中，如果n的第i位數(shù)值為p，則aI=fp，這樣做可以節(jié)約不少時(shí)間，相信這一點(diǎn)大家不難理解。找到遞推關(guān)系，用高精度計(jì)算方法完成。問題關(guān)鍵在于如何求出遞推總數(shù)49如果n是3位數(shù)，個(gè)位數(shù)的可變總數(shù)為a1，十位數(shù)的可變總數(shù)50用圖來表示這種關(guān)系：1、建立一個(gè)有向圖G，初始化gi, j=False 表示從I到j(luò)不存在通路2、如果數(shù)字i能直接轉(zhuǎn)換為數(shù)字j， 那么gi, j=True3、如何通過有向圖

23、，獲取fi的值呢？可以用圖的遍歷方法：深度、寬度 用floyd算法：50用圖來表示這種關(guān)系：51由于本題的關(guān)鍵在于兩結(jié)點(diǎn)是否可達(dá)，可以采用類似Floyd的有向圖的傳遞閉包算法，該算法實(shí)現(xiàn)簡(jiǎn)單 ，在解決這類問題時(shí)比Floyd效率更高。只需將floyd算法中的算術(shù)運(yùn)算符操作+用相應(yīng)的邏輯運(yùn)算符and和or代替就可以了，直接在g數(shù)組上進(jìn)行操作，對(duì)g數(shù)組重新定義為：gi,j=false 表示i到j(luò)不可達(dá)gi,j=true 表示i可轉(zhuǎn)換為j則有：如果 gi,k=true 且 gk,j=ture ，則 gi,j=true;其算法如下：for k :=0 to 9 dofor i := 0 to 9 do

24、for j := 0 to 9 do gi, j = gi, j or (gi, k and gk, j)51由于本題的關(guān)鍵在于兩結(jié)點(diǎn)是否可達(dá)，可以采用類似Floyd52procedure init; 初始化var code:integer; begin assign(f1,input.txt); reset(f1); readln(f1,s); n:=1; while sn do begin an:=ord(sn)-ord(0); n:=n+1; end; 52procedure init; 53 j:=n; n:=n-1; while sj= do j:=j+1; val(copy(s,j,2), k, code); fillchar(g , sizeof(g), fals