圖的最短路徑及應(yīng)用.ppt

圖的最短路徑及應(yīng)用,最小生成樹 最短路徑算法 深入應(yīng)用 wzl 2013-10-29,圖的最小生成樹,圖的最小生成樹主要兩種方法：頂點(diǎn)遍歷 （1） prim算法 圖的存儲(chǔ)矩陣、深搜算法、集合運(yùn)算 （2）kruskal算法 邊集數(shù)組存儲(chǔ)、貪心算法、集合運(yùn)算,prim算法的要點(diǎn)是： （1）設(shè)有n個(gè)頂點(diǎn)的連通網(wǎng)： G=（V，E），T=（U，TE）是G的最小生成樹 其中U是頂點(diǎn)集 TE是T的邊集 U、TE開始值為空,（2）算法如下： Procedure Prim(GA,CT); begin for I:=1 to n-1 do 給CT賦初值，對(duì)應(yīng)第0次的LW值 CTI.from :=1 ; ctI.end: =I+1 ; ctI.w:=GA1, i+1 ; for k:=1 to n-1 do 進(jìn)行n-1次循環(huán)，求出最小生成樹的第K條邊 min:=maxint ; m:=k ; for j:=k to n-1 do if ctj.w k then ctk 與ctm 的交換 將最短邊調(diào)到第K單元 , j:=ctk.end; 將新的并入T中頂點(diǎn)給J for I:=k+1 to n-1 do 修改LW中的有關(guān)邊 d:=ctI.end ; w:=GAj, d ; IF WCTI.W then CTi. w:=w; CTi.from:=j ; End;,Kruskal 算法 （ 貪心算法 ）,(1) 建立邊集記錄數(shù)組：起點(diǎn)、終點(diǎn)、邊的權(quán) (2) 按權(quán)的大小排序 (3) 每次選擇最短邊，且不構(gòu)成回路，直到所有頂點(diǎn)都在這棵樹上。 關(guān)鍵判斷回路：用集合方法并查集 頂點(diǎn)查找、頂點(diǎn)集合并集構(gòu)成邊的兩個(gè)頂點(diǎn)分別在不同的頂點(diǎn)集合中合并操作,算法： Procedure kruskal ( GE,C ) ; begin for i:=1 to n do si:= i ; 初始化頂點(diǎn)集合 i:=1 ; j:=1 i 表示邊數(shù)，j 表示數(shù)組GE的下標(biāo) while i m2 then 生成樹的一條邊 ,being ci:=j ; 保存選取的第i條邊 ,j 是GE數(shù)組的下標(biāo) i:=i+1 ; sm1:=sm1+sm2 ; sm2:= ; end; (3) j:=j+1 ; end ; 運(yùn)行該程序后，C數(shù)組的值為： 1 2 3 4 5 所以最小生成樹由GE數(shù)組中的1，2，3，5，7 邊組成。,圖的最短路徑,(1) 深搜算法：遞歸算法思想回溯不輸出過程 (2) 寬搜算法：隊(duì)列算法判重 輸出路徑 (3) Dijktra 算法：單源最短路徑 從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑調(diào)整路徑 可以輸出路徑，又稱標(biāo)號(hào)法 (4) floyed 算法 ： 任意兩個(gè)頂點(diǎn)之間的最短路徑調(diào)整路徑,(5) 啟發(fā)式搜索 在寬度優(yōu)先搜索算法的基礎(chǔ)上，每次并不是把所有可展開的結(jié)點(diǎn)展開，而是利用一個(gè)自己確定的估價(jià)函數(shù)對(duì)所有沒展開的結(jié)點(diǎn)進(jìn)行估價(jià)，從而找出最應(yīng)該被展開的結(jié)點(diǎn)（也就是說我們要找的答案最有可能是從該結(jié)點(diǎn)展開），而把該結(jié)點(diǎn)展開，直到找到目標(biāo)結(jié)點(diǎn)為止。 估價(jià)函數(shù)比較難確定,(6) 等代價(jià)搜索法 等代價(jià)搜索法也是在寬度優(yōu)先搜索的基礎(chǔ)上進(jìn)行了部分優(yōu)化的一種算法，它與啟發(fā)式搜索的相似之處都是每次只展開某一個(gè)結(jié)點(diǎn)（不是展開所有結(jié)點(diǎn)），不同之處在于：它不需要去另找專門的估價(jià)函數(shù)，而是以該結(jié)點(diǎn)到起點(diǎn)的距離作為估價(jià)值，也就是說，等代價(jià)搜索法是啟發(fā)式搜索的一種簡化版本。 (7) 遞推法 該算法的中心思想是：任意兩點(diǎn)i,j間的最短距離（記為Dij）會(huì)等于從i點(diǎn)出發(fā)到達(dá)j點(diǎn)的以任一點(diǎn)為中轉(zhuǎn)點(diǎn)的所有可能的方案中，距離最短的一個(gè)。即： Dij = min Dij , Dik+Dkj ，1=k=n。,類似動(dòng)態(tài)規(guī)劃的表達(dá)式，用二維數(shù)組存放任意兩點(diǎn)間的最短距離，利用上述公式不斷地對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行處理，直到各數(shù)據(jù)不再變化為止，這時(shí)即可得到A到E的最短路徑。 Di表示起點(diǎn)到i的最短路長度，g是鄰接矩陣，s表示起點(diǎn)； 1、Di:=gs,i (1Dk+gk,j then begin Dj:= Dk+gk,j; c:=true; end; Until not c；,該算法過程：不斷地求一個(gè)數(shù)字最短距離矩陣中的數(shù)據(jù)的值，而當(dāng)所有數(shù)據(jù)都已經(jīng)不能再變化時(shí)，就已經(jīng)達(dá)到了目標(biāo)的平衡狀態(tài)，這時(shí)最短距離矩陣中的值就是對(duì)應(yīng)的兩點(diǎn)間的最短距離。 （8）動(dòng)態(tài)規(guī)劃 某些最短路徑問題也可以用動(dòng)態(tài)規(guī)劃來解決，通常這類最短路徑問題所對(duì)應(yīng)的圖必須是有向無回路圖。 動(dòng)態(tài)規(guī)劃算法與遞歸算法不同之處在于它們的算法表達(dá)式： 遞歸：類似f(n)=x1*f(n-1)+x2*f(n-2)確定關(guān)系表達(dá)式； 動(dòng)態(tài)規(guī)劃：f(n)=min(f(n-1)+x1,f(n-2)+x2)，即無法找到確定關(guān)系的表達(dá)式，只能找到一個(gè)不確定關(guān)系的表達(dá)式，f(n)的值是動(dòng)態(tài)的，隨著f(n-1),f(n-2)等值的改變而確定跟誰相關(guān)。,（9）標(biāo)號(hào)法 標(biāo)號(hào)法是一種非常直觀的求最短路徑的算法，可以用一個(gè)數(shù)軸簡單地表示這種算法： 以A點(diǎn)為0點(diǎn)，展開與其相鄰的點(diǎn)，并在數(shù)軸中標(biāo)出。, 因?yàn)镃點(diǎn)離起點(diǎn)A最近，因此可以斷定C點(diǎn)一定是由A直接到C點(diǎn)這條路徑是最短的（因?yàn)锳、C兩點(diǎn)間沒有其它的點(diǎn)，所以C點(diǎn)可以確定是由A點(diǎn)直接到達(dá)為最短路徑）。因而就可以以已確定的C點(diǎn)為當(dāng)前展開點(diǎn)，展開與C點(diǎn)想連的所有點(diǎn)A、B、D、E。, 由數(shù)軸可見，A與A點(diǎn)相比，A點(diǎn)離原點(diǎn)近，因而保留A點(diǎn)，刪除A點(diǎn)，相應(yīng)的，B、B點(diǎn)保留B點(diǎn)，D、D保留D，E、E保留E，得到下圖：, 此時(shí)再以離原點(diǎn)最近的未展開的點(diǎn)B聯(lián)接的所有點(diǎn)，處理后，再展開離原點(diǎn)最近未展開的D點(diǎn)，最終結(jié)果： 結(jié)論：點(diǎn)C、B、D、E就是點(diǎn)A到它們的最短路徑（注意：這些路徑并不是經(jīng)過了所有點(diǎn)，而且到每一個(gè)點(diǎn)的那條路徑不一定相同）。因而A到E的最短距離就是13。經(jīng)過了哪幾個(gè)點(diǎn)，在過程中加以記錄即可。,標(biāo)號(hào)法是一種求圖的最短路徑的不用重復(fù)回溯搜索的高效率算法。算法思想 在圖G中，頂點(diǎn)Vi到Vj的非負(fù)長度為Map(i, j)，求從起點(diǎn)Vs到終點(diǎn)Ve的最短距離。 設(shè)：x數(shù)據(jù)為擴(kuò)展的隊(duì)列；Sum(j)表示頂點(diǎn)Vs到Vj的最短距離，F(xiàn)A(j)表示頂點(diǎn)Vj前趨結(jié)點(diǎn)，算法過程： （1）隊(duì)列初始化,Vs進(jìn)入隊(duì)列L, X1:=s, sum1=0； （2）取隊(duì)首結(jié)點(diǎn)VK，若VK是目標(biāo)結(jié)點(diǎn)Ve，則輸出結(jié)果（最短路徑值及路徑）程序結(jié)束；否則繼續(xù)（3）；,（3）由VK擴(kuò)展出結(jié)點(diǎn)VJ（結(jié)點(diǎn)VK與VJ相連），計(jì)算代價(jià)值 若Sum(k)+mapk,jsum(j) 則替換結(jié)點(diǎn)J的代價(jià)，換代價(jià)值由小到大插入隊(duì)列，并記錄其父結(jié)點(diǎn)：sum(j):=sum(k)+mapk,j, faj:=k，結(jié)點(diǎn)J入隊(duì)列繼續(xù)（2），否則直接轉(zhuǎn)（2）。 注意： 1.只有兩個(gè)頂點(diǎn)間距離為非負(fù)時(shí)，才可用標(biāo)號(hào)法。 2.只有隊(duì)列的首結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)時(shí)，才可停止計(jì)算。否則得出的不一定是最優(yōu)解。 標(biāo)號(hào)法算法偽代碼如下：,fillchar(x,sizeof(x),0); for I:=1 to n do begin sumI:=maps,I; faI:=s; end; x1:=s; sums:=0; f:=1; r:=1; fas:=0; repeat temp:=xf; if temp=Ve then print ; halt; for j:=1 to n do if (sumtemp+maptemp,j0 ) then begin sumj:=sumtemp+maptemp,j; r:=r+1; faj:=f; end; f:=f+1; until f r,例題1、特快專遞 加國是個(gè)小國，僅有n個(gè)城市( 1n40)。奧維爾負(fù)責(zé)這個(gè)國家的特快專遞，他有一輛汽車沿途他要到各個(gè)城市去送ems信件，各城市之間的路程s ( 0s1000) 是已知的，且A城市到B城市與B城市到A城市的路程大多不同。為了提高效率，他從快遞公司出發(fā)到每個(gè)城市一次，然后返回快遞公司所在城市，假設(shè)快遞公司所在的城市為1，他不知道選擇什么樣的路線才能使所走的路程最短。請(qǐng)你幫助他選擇一條最短的路。,輸入：城市數(shù)n 和各城市之間的路程（均是整數(shù)） 輸出：最短的路徑 樣例：salesman.in 3 0 2 1 1 0 2 2 1 0 salesman.out 3,算法： 求最短路徑算法，所要注意的問題： 他需要返回到初始的城市,Program salesma; Var g:array140,140 of integer; a:array140 of integer; v:array140 of boolean; n,i,j,q:integer; s,t,min:longint; Procedure try(p:integer); var i:integer; begin if q=n+1 then begin if s+gp,1min then min:=s+gp,1; exit; end;,for i:=2 to n do if not(vi) then begin inc(s,gp,i);vi:=true;inc(q); if smin then try(i); dec(s,gp,i); vi:=false;dec(q); end; end; Procedure work; var i,j,k,p,l:integer; v:array140 of boolean;,begin fillchar(v,sizeof(v),false); l:=1; min:=0; for i:=2 to n do begin k:=2; while vk do inc(k); p:=k; for j:=p+1 to n do if not(vj) and (gl,jgl,k) then k:=j; inc(min,gl,k); l:=k;vl:=true; end; inc(min,gl,1); end;,begin assign(input,salesma.in);reset(input); assign(output,salesma.out);rewrite(output); read(n); for i:=1 to n do for j:=1 to n do read(gi,j); s:=0; q:=2;work; try(1); writeln(min); close(input);close(output); end.,方法2 Program ksd; var a:array150,150 of longint; n,i,j,min:longint; f:array150 of boolean; Procedure go(i,s,sum:longint); var ii:longint; begin if s=n then begin if sum+ai,1=min then exit;,For ii := 1 to n do if fii=false then begin fii:=true; go(ii,s+1,sum+ai,ii); fii:=false; end; end; begin assign(input,salesma.in); assign(output,salesma.out); reset(input); rewrite(output); readln(n); for i := 1 to n do for j := 1 to n do read(ai,j); min:=maxlongint; f1:=true; go(1,1,0); writeln(min); close(input); close(output); end.,例題2、深度優(yōu)先遍歷算法優(yōu)化 輸入n (1=n=2,000,000,000),輸出該數(shù)據(jù)的所有形式不同的因式分解。 樣例： 12=12 12=6*2 12=4*3 12=3*4 12=3*2*2 12=2*6 12=2*3*2 12=2*2*3,算法1：減少數(shù)據(jù)范圍或運(yùn)算次數(shù) 利用遞歸算法： 窮舉2N之間的所有整數(shù)，若該數(shù)是N的約數(shù)，則遞歸對(duì)該數(shù)進(jìn)行分解，直到變?yōu)? 程序段代碼： procedure solve ( n:integer ) ; var i:integer ; begin if n=1 then inc(total) else for i:=2 to n do if n mod i=0 then solve(n div i) end;,算法2： 改進(jìn)方法：首先將n的所有因子數(shù)按從小到大的順序，存儲(chǔ)在一個(gè)數(shù)組內(nèi)。 這樣在每一層遞歸時(shí)只要窮舉當(dāng)前待分解的數(shù)就可以了，由于該數(shù)是N的因子，所以它的因子也是N的因子。,Procedure solve(k:longint); var i, j, temp:longint; begin if k=0 then inc(total) else for i:=k downto 1 do if fk mod fi=0 then if fk=fi then inc(total) else begin temp:=fk div fi; j:=k-1; while tempfj do dec(j); solve(j) end end;,begin read(n); s:=0; i:=2; while i*i=n do begin if n mod i=0 then begin inc(s); fs:=i; f-s:=n div i end; i:=i+1 end;,if (i-1)*(i-1)n then j:=-s else j:=-s+1; for i:=j to -1 do begin inc(s); fs:=fi； end; inc(s); fs:=n; total:=0; solve(s); writeln(total); end.,例題3、n個(gè)士兵排列問題 有n個(gè)士兵（1n26），編號(hào)依次為A、B、C， 隊(duì)列訓(xùn)練時(shí)，指揮官要把一些士兵從高到矮依次排成一行。但現(xiàn)在指揮官不能直接獲得每個(gè)人的身高信息，只能獲得“p1比p2高”這樣的比較結(jié)果（p1，p2A，Z），記為p1p2。 根據(jù)這些關(guān)系，求出排隊(duì)方案。 例：AB，BD，F(xiàn)D （沒有循環(huán)，可以用拓?fù)渑判颍?方案：AFBD、FABD、ABFD,拓?fù)渑判驊?yīng)用,Program tppv; n個(gè)士兵排隊(duì) const maxn=100; var map:array1maxn,1maxn of byte; into:array1maxn of byte; n,i,j,k:byte; Procedure init; var i,j:integer; begin readln(n); fillchar(map,sizeof(map),0); fillchar(into,sizeof(into),0);,while not(seekeof(fp) do begin readln(fp,i,j); mapi,j=1 ; inc(intoj); end; close(fp); end;,begin init; for i:=1 to n do begin j:=1; while (j0) do inc(j); write(j, ); intoj:=255; for k:=1 to n do if mapj,k=1 then dec(intok); end; end.,例題4、雇傭計(jì)劃： 一個(gè)工廠管理員需要確定每個(gè)月需要的工人，他知道每個(gè)月需要的最少工人數(shù)。當(dāng)他雇傭或解雇一個(gè)工人時(shí)，需要一些額外支出。一旦一個(gè)工人被雇用，即使他不工作，他也將得到工資，同時(shí)該管理員知道雇傭一個(gè)工人的費(fèi)用、解雇一個(gè)工人的費(fèi)用和一個(gè)工人的工資。他正在考慮為了把項(xiàng)目的費(fèi)用控制在最低，他將每月雇傭或解雇多少人。 輸入：三行，第一行為月數(shù)，第二行含有雇傭一個(gè)工人費(fèi)用、一個(gè)工人工資、解雇一個(gè)工人費(fèi)用（=100），第三行含n個(gè)數(shù)，分別表示每個(gè)月最少需要的工人數(shù)（=1000），每個(gè)數(shù)據(jù)之間有一個(gè)空格隔開。 輸出：一行，表示項(xiàng)目的最小總費(fèi)用。,樣例： 3 4 5 6 10 9 11 輸出 ： 199 問題分析： （1）根據(jù)題意需要逐月計(jì)算現(xiàn)有工人工作、雇傭工人的雇傭費(fèi)或解雇工人的費(fèi)用 （2）確定雇傭方案：當(dāng)人數(shù)不足情況下 設(shè)第I個(gè)月所需要最少人數(shù)為minI大于現(xiàn)有人數(shù)now，則需要雇傭工人，其人數(shù)minI-now，費(fèi)用： cost=cost+h*(minI-now), now=minI 雇傭金,Cost=cost+now*s 本月費(fèi)用總支出 （3）人數(shù)多余情況： 當(dāng)nowminI則需解雇一些人，解雇多少是問題根本： 本例題中，第1個(gè)月10人：cost=cost+4*10+5*10=90 第2個(gè)月解雇1人 cost=cost+f(now-min2)+d*min2=141 第3個(gè)月需11人 cost=cost+h*(min3-now)+d*min3=204 這不是最佳方案，此時(shí)可以采取第2個(gè)月不解雇的策略： 4*10+5*10+5*10+（4*1+5*11）=199 。 采取貪心策略： 盡可能少的解雇工人，并且在工資支出合理的前提下，盡可能使現(xiàn)有工人數(shù)維持在一個(gè)最長時(shí)間內(nèi)，以減少雇傭和解雇的額外支出。,實(shí)現(xiàn)方法： 在minIminn間按最少需要人數(shù)遞增的順序，將月份排列成y1,y2,。 program p3_5 (input,output); Var n,a,b,c,i,j,max,min:integer; s: extended; g: array0100 of integer; begin readln(n); readln(a,b,c);,for i:=1 to n do read(gi); max:=(a+c) div b+1; for i:=1 to n do begin if gi=gi-1 then s:=s+gi*b+(gi-gi-1)*a; if gimin) and (j=n) then min:=gj; if mingi then,begin s:=s+(gi-min)*c; gi:=min; gi+1:=gi; end else begin gi:=gi-1; if gi+1gi then gi+1:=gi; end; s:=s+gi*b; end; end; writeln(s:0:0); end.,例5：Car的旅行路線 ，問題描述： 暑假到了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市中兩個(gè)機(jī)場之間有一條筆直的高速鐵路，第I個(gè)城市中高速鐵路了的單位里程價(jià)格為Ti，任意兩個(gè)不同城市的機(jī)場之間均有航線，所有航線單位里程的價(jià)格均為t。,機(jī)場 高速鐵路 飛機(jī)航線 注意：圖中并沒有 標(biāo)出所有的鐵路與航線。,那么Car應(yīng)如何安排到城市B的路線才能盡可能的節(jié)省花費(fèi)呢?她發(fā)現(xiàn)這并不是一個(gè)簡單的問題，于是她來向你請(qǐng)教。 找出一條從城市A到B的旅游路線，出發(fā)和到達(dá)城市中的機(jī)場可以任意選取，要求總的花費(fèi)最少。輸出最小費(fèi)用，小數(shù)點(diǎn)后保留2位。) 輸入格式 第一行為一正整數(shù)n(0=n=10)，表示有n組測試數(shù)據(jù)。 每組的第一行有四個(gè)正整數(shù)s，t，A，B。 S(0S=100)表示城市的個(gè)數(shù)，t表示飛機(jī)單位里程的價(jià)格，A，B分別為城市A，B的序號(hào)，(1=A，B=S)。,接下來有S行，其中第I行均有7個(gè)正整數(shù)xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當(dāng)中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第I個(gè)城市中任意三個(gè)機(jī)場的坐標(biāo)，Ti為第I個(gè)城市高速鐵路單位里程的價(jià)格。 輸出格式： 共有n行，每行一個(gè)數(shù)據(jù)對(duì)應(yīng)測試數(shù)據(jù)。 樣例 輸入 1 3 10 1 3 1 1 1 3 3 1 30 2 5 7 4 5 2 1 8 6 8 8 11 6 3 輸出： 47.55,分析：簡單的幾何計(jì)算和最短路徑相結(jié)合的問題 單源最短路徑 dijkstra 首先對(duì)于每個(gè)城市根據(jù)給出的三個(gè)機(jī)場的坐標(biāo)計(jì)算出第四個(gè)機(jī)場的坐標(biāo)，以城市A的四個(gè)機(jī)場分別作為起始結(jié)點(diǎn)，以城市B的四個(gè)機(jī)場分別作為目標(biāo)結(jié)點(diǎn)，用標(biāo)號(hào)法計(jì)算出所有最小代值值，從中找出最小代價(jià)即為問題的解。,判斷垂直的公式（斜率互為負(fù)倒數(shù)）,Program car; Var n,s,t,a,b,m,u:byte;fn:string; tr:array1100of word; x,y:array1100,14of word; Function dist(c1,p1,c2,p2:byte):extended; Var d1,d2:extended; 兩點(diǎn)之間距離 Begin d1:=xc1,p1; d1:=d1-xc2,p2; d2:=yc1,p1; d2:=d2-yc2,p2; dist:=sqrt(sqr(d1)+sqr(d2); End;,Function Dijkstra ( c: byte ):extended; Var use:array1100,14of 01; way: array0100,14 of extended; i, j,mc,mp,lc,lp:byte; Begin fillchar(use,sizeof(use),0); For i:=1 to 4 Do way0,i:=1e38; For i:=1 to s Do For j:=1 to 4 Do wayi,j:=dist(a, c, i, j)*t; For i:=1 to 4 Do usea,i:=1; mc:=0; mp:=1; lc:=0; lp:=1; For i:=1 to s Do For j:=1 to 4 Do If (usei,j=0) And (wayi,jwaymc,mp) Then Begin mc:=i; mp:=j; End; usemc,mp:=1;,While (no