數(shù)據(jù)結(jié)構(gòu)-最短路一

第五章最短路吉林大學(xué)計(jì)算機(jī)學(xué)院谷方明fmgu2002@問題背景最短路是實(shí)際應(yīng)用中最常遇到的任務(wù)。旅游：長(zhǎng)春杭州，路程、時(shí)間、費(fèi)用最短路問題：在給定的圖中，從某頂點(diǎn)出發(fā)，找從該點(diǎn)到其它頂點(diǎn)cost最小的路徑。路徑的cost指該路徑邊的權(quán)值累加和。最短路問題分類兩個(gè)頂點(diǎn)間的最短路：從一個(gè)指定的頂點(diǎn)到達(dá)另一指定頂點(diǎn)的最短路問題。單源最短路(SingleSourceShortestPath,SSSP)：從一個(gè)指定的頂點(diǎn)到其它所有頂點(diǎn)的最短路徑問題。任意頂點(diǎn)間的最短路：所有頂點(diǎn)間的最短路；13258102045301202341.無權(quán)圖的單源最短路無權(quán)——相當(dāng)于所有邊的權(quán)值都為1.源點(diǎn)到各頂點(diǎn)的路徑長(zhǎng)度：所經(jīng)歷的邊的數(shù)目思想：從源點(diǎn)開始由近及遠(yuǎn)依次求各頂點(diǎn)的最短路徑設(shè)Di為源點(diǎn)S到頂點(diǎn)i的最短路徑長(zhǎng)度①訪問初始頂點(diǎn)S，即令DS=0。②從S出發(fā)，找最短路徑為1的頂點(diǎn)，即S的所有鄰接頂點(diǎn)w，令Dw=DS+1③從上步訪問的頂點(diǎn)w出發(fā)，找最短路徑為2的頂點(diǎn)，即w未被訪問的鄰接頂點(diǎn)v，令Dv=Dw+1④繼續(xù)上述過程，直至處理完所有頂點(diǎn)。1V12V63V51V32V43V20SV0算法思想上述過程中，訪問頂點(diǎn)的次序與對(duì)圖進(jìn)行廣度優(yōu)先遍歷的次序是一致的;1V12V63V51V32V43V20SV0算法實(shí)現(xiàn)圖采用鄰接表存儲(chǔ)；用隊(duì)列保存待處理頂點(diǎn)；使用數(shù)組dist[]存儲(chǔ)最短路徑值。源點(diǎn)初始化為0，其它初始為-1.當(dāng)dist[i]從-1變?yōu)榉秦?fù)時(shí)，表示從源點(diǎn)到i的最短路徑已求完為找到最短路徑，可用path[]存儲(chǔ)從源點(diǎn)到頂點(diǎn)i的最短路上i之前的頂點(diǎn)。算法描述算法ShortestPath(v)/*計(jì)算從頂點(diǎn)v到其他各頂點(diǎn)的最短路徑*/S1[初始化]CREATQuene(Q)./*創(chuàng)建一個(gè)隊(duì)列*/for(i=1;i<=n;i++){ path[i]=-1;dist[i]=-1.}dist[v]=0; Q.inset(v)；

S2[求從頂點(diǎn)v到其他各頂點(diǎn)的最短路徑]while(！Q.empty()){

u=Q.delete(); /*隊(duì)頭頂點(diǎn)u出隊(duì)*/for(p=

Head[u].adjacent;p;p=p->link){

k=p->VerAdj;if(dist[k]==-1){

Q.insert(k);//u未訪問的鄰接頂點(diǎn)入隊(duì)dist[k]=dist[u]+1;path[k]=u;

} }}?算法分析鄰接表：在最短路徑的計(jì)算中，一個(gè)頂點(diǎn)入隊(duì)出隊(duì)各一次，時(shí)間復(fù)雜性為O(n)；而對(duì)每個(gè)頂點(diǎn)，都要對(duì)它的邊鏈表進(jìn)行遍歷，其遍歷鄰接表的開銷為O(e)，于是整個(gè)算法的時(shí)間復(fù)雜性為O(n+e)。鄰接矩陣：O(n2)2.非負(fù)權(quán)圖的單源最短路給定一個(gè)帶權(quán)圖G與源點(diǎn)v，求從v到G中其它頂點(diǎn)的最短路徑。要求各邊的權(quán)值為非負(fù)實(shí)數(shù)。無權(quán)最短路算法？v0v1v2283分析方法一：枚舉從源點(diǎn)出發(fā)的所有路徑及其長(zhǎng)度，從中找出最短路徑。重復(fù)搜索，效率低。方法二：初始時(shí)只看到一個(gè)源點(diǎn)。對(duì)頂點(diǎn)按廣度優(yōu)先擴(kuò)展。隨著圖的擴(kuò)展，發(fā)現(xiàn)更短路徑時(shí)，圖中頂點(diǎn)的的最短路徑被更新（relax，松弛操作）。擴(kuò)展時(shí)按照頂點(diǎn)編號(hào)的順序效率低。1325405041020Dijkstra算法思想按路徑長(zhǎng)度非遞減的次序，逐步產(chǎn)生最短路徑。使用數(shù)組dist，dist[i]表示當(dāng)前找到的源點(diǎn)v0到vi的最短路徑長(zhǎng)度。把圖中所有頂點(diǎn)分成兩組，第一組：已求完最短路徑的頂點(diǎn)；第二組：未求完最短路徑的頂點(diǎn)。按最短路徑長(zhǎng)度遞增的順序逐個(gè)把第二組的頂點(diǎn)加到第一組。初始時(shí)：S={}，dist[0]=0，dist[i]=+

設(shè)S是已求得最短路徑的頂點(diǎn)集合，則：下一條最短路徑必然是從源點(diǎn)v0出發(fā)，中間只經(jīng)過S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx(vxV-S)的路徑中的一條。每次求最短路徑，就是在V-S中找具有最小dist值的頂點(diǎn)vk，將vk加入集合S，然后對(duì)viV-S，修改dist[i]值。經(jīng)第一次操作，S={v0}，若v0到vi有邊，則dist[i]更新為邊上的權(quán)值；v0到vi無邊，則dist[i]仍為+

。S

V-SDijkstra算法①設(shè)S為初始頂點(diǎn),Ds=0且

i≠S，有Di=＋∞②在未訪問頂點(diǎn)中選擇Dv最小的頂點(diǎn)v，訪問v，令S[v]=1。③依次考察v的鄰接頂點(diǎn)w，若

Dv+weight(<v,w>)<Dw

，則改變Dw的值，使Dw=

Dv+weight(<v,w>)。④重復(fù)②③，直至所有頂點(diǎn)被訪問。01234024310∧5134∧3038∧225410∧02024412∧例1325810204530120234spathdist0000003421∞∞∞

0∞1325810204530120234spathdist0000003421∞∞3

030v0v0013302343∞∞325813300234302811spathdist000000342128113

030v0v0v1v11325810204530120234312041581323423111325810204530120234spathdist000000342115113

023v0v3V3V1120415813234231131325810204530120234spathdist000000342115113

023v0v3V3V1120415813234231131325810204530120234spathdist000000342115113

023v0v3V3V1定理5.4Dijkstra算法可以按照非遞減次序依次得到各頂點(diǎn)的最小路徑長(zhǎng)度。證明：歸納法算法得到的路徑值是各頂點(diǎn)的最小路徑長(zhǎng)度。算法得到的路徑值是按非遞減次序得到的。svud>0v0v1v243-2Dijkstra算法描述算法DShortestPath(v)/*計(jì)算v到其他各頂點(diǎn)的最短路徑*/D1[初始化]

for(i=1;i<=n;i++){ path[i]=-1;dist[i]=max;s[i]=0;//數(shù)組s[i]記錄i是否已計(jì)算完}dist[v]=0;D2[求從v到其他各頂點(diǎn)的最短路徑]for(j=1;j<n;j++){ldist=max;//循環(huán):確定即將被訪問的頂點(diǎn)u

for(i=1;i<=n;i++) if(dist[i]<ldist&&s[i]==0) {ldist=dist[i];u=i;}s[u]=1. for(p=Head[u].adjacent;p;p=p->link){ k=p->VerAdj;

if(dist[u]+cost(p)<dist[k])//松弛{dist[k]dist[u]+cost(p);path[k]=u;}}}算法分析時(shí)間復(fù)雜性：在Dijkstra算法中，循環(huán)掃描被訪問頂點(diǎn)的邊鏈表，時(shí)間復(fù)雜性為O(du)（du為頂點(diǎn)u的鄰接頂點(diǎn)個(gè)數(shù)）；循環(huán)掃描頂點(diǎn)表求最小dist，時(shí)間復(fù)雜性為O(n)；循環(huán)體要被執(zhí)行n次，因此整個(gè)算法的時(shí)間復(fù)雜性為與存儲(chǔ)方式無關(guān)；與邊數(shù)無關(guān)3.每對(duì)頂點(diǎn)間的最短路徑已知一個(gè)帶權(quán)有向圖，對(duì)每一對(duì)頂點(diǎn)vi

vj，求vi

與vj間的最短路徑和最短路徑長(zhǎng)度。如果是正權(quán)圖，可依次把每個(gè)頂點(diǎn)作為源點(diǎn)，執(zhí)行n次Dijkstra算法。Floyd算法設(shè)圖是用鄰接矩陣存儲(chǔ)的權(quán)圖。求頂點(diǎn)到頂點(diǎn)的最短路徑的基本思想是：如果，則說明至存在弧，將該弧設(shè)為當(dāng)前最短路徑，但該路徑未必是最終最短路徑，我們需要進(jìn)行n次試探。設(shè)頂點(diǎn)集，，…，.第一步：考察是否存在路徑，其經(jīng)由頂點(diǎn)所構(gòu)成的集合是的子集S0（即弧<Vi,V0>和<V0,Vj>是否存在）。若存在，比較該路徑與當(dāng)前最短路徑的長(zhǎng)度值，取值較小的路徑作為新的當(dāng)前最短路徑，它是Vi至Vj的經(jīng)由頂點(diǎn)序列號(hào)小于1的最短路徑。第二步：考察是否存在路徑，其經(jīng)由頂點(diǎn)所構(gòu)成的集合是S1的子集，但不是S0的子集。若存在，比較該路徑與當(dāng)前最短路徑的長(zhǎng)度值，取值較小的路徑作為新的當(dāng)前最短路徑，它是Vi至Vj的經(jīng)由頂點(diǎn)序列號(hào)小于2的最短路徑?！趎步：考察是否存在路徑，其經(jīng)由頂點(diǎn)所構(gòu)成的集合是Sn-1的子集，但不是Sn-2的子集。若存在，比較該路徑與當(dāng)前最短路徑的長(zhǎng)度值，取值較小的路徑作為新的當(dāng)前最短路徑，它是Vi至Vj的經(jīng)由頂點(diǎn)序列號(hào)小于的最短路徑。算法實(shí)現(xiàn)設(shè)鄰接矩陣存儲(chǔ)圖，edge[n][n]為圖的鄰接矩陣；定義一個(gè)n階方陣序列：A(-1),A(0),…,A(n-1).定義初始矩陣A(-1)[i][j]=Edge[i][j]；1求A(0),即從vi到vj經(jīng)由頂點(diǎn)可以是{v0}的最短路徑；2求A(1),即從vi到vj經(jīng)由頂點(diǎn)可以是{v0,v1}的最短路徑；

…n求A(n-1),即從vi到vj經(jīng)由頂點(diǎn)可以是{v0,

v1,…,vn-1}的最短路徑長(zhǎng)度；其中A(k)[i][j]=min{A(k-1)[i][j]，

A(k-1)[i][k]+A(k-1)[k][j]},k=0,1,…,n-1Path(1)Path(0)Path(1)Path(2)Path(3)01230123012301230123010101010101110111031111111111111121112131222122010201120112011311311131113122312031A(1)A(0)A(1)A(2)A(3)01230123012301230123001401401103011030193109209209212092110822350834073406340634063606060910609106023013685941201409235086010230123從A(3)知，頂點(diǎn)1到0的最短路徑長(zhǎng)度為a[1][0]=11，其最短路徑：path[1][0]=2，表示頂點(diǎn)2頂點(diǎn)0；

path[1][2]=3，表示頂點(diǎn)3頂點(diǎn)2；path[1][3]=1，表示頂點(diǎn)1頂點(diǎn)3；從頂點(diǎn)1到頂點(diǎn)0最短路徑為：<1,3>，<3,2>，<2,0>（見Path(3)中第1行，第0、2、3列)

算法描述算法Floyd()/*求每對(duì)頂點(diǎn)間的最短路徑，其中edge[n][n]表示有n個(gè)頂點(diǎn)的圖的鄰接矩陣；A[i][j]表示頂點(diǎn)Vi至Vj的最短路徑長(zhǎng)度；path[i][j]表示相應(yīng)路徑上頂點(diǎn)j的前一個(gè)頂點(diǎn)的序號(hào)*/F1[