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

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

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

u=Q.delete(); /*隊頭頂點u出隊*/for(p=

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

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

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

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

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

。S

V-SDijkstra算法①設S為初始頂點,Ds=0且

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

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

，則改變Dw的值，使Dw=

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

0∞1325810204530120234spathdist0000003421∞∞3

030v0v0013302343∞∞325813300234302811spathdist000000342128113

030v0v0v1v11325810204530120234312041581323423111325810204530120234spathdist000000342115113

023v0v3V3V1120415813234231131325810204530120234spathdist000000342115113

023v0v3V3V1120415813234231131325810204530120234spathdist000000342115113

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

for(i=1;i<=n;i++){ path[i]=-1;dist[i]=max;s[i]=0;//數(shù)組s[i]記錄i是否已計算完}dist[v]=0;D2[求從v到其他各頂點的最短路徑]for(j=1;j<n;j++){ldist=max;//循環(huá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;}}}算法分析時間復雜性：在Dijkstra算法中，循環(huán)掃描被訪問頂點的邊鏈表，時間復雜性為O(du)（du為頂點u的鄰接頂點個數(shù)）；循環(huán)掃描頂點表求最小dist，時間復雜性為O(n)；循環(huán)體要被執(zhí)行n次，因此整個算法的時間復雜性為與存儲方式無關(guān)；與邊數(shù)無關(guān)3.每對頂點間的最短路徑已知一個帶權(quán)有向圖，對每一對頂點vi

vj，求vi

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

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

v1,…,vn-1}的最短路徑長度；其中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)知，頂點1到0的最短路徑長度為a[1][0]=11，其最短路徑：path[1][0]=2，表示頂點2頂點0；

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

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