最短路問題(整理版)

最短路問題(sHort-patHpro6Lem)若網(wǎng)絡(luò)中的每條邊都有一個權(quán)值值(長度、成本、時間等)，則找出兩節(jié)點(通常是源節(jié)點與結(jié)束點)之間總權(quán)和最小的路徑就是最短路問題。最短路問題是網(wǎng)絡(luò)理論解決的典型問題之一，可用來解決管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等實際問題。最短路問題我們通常歸屬為三類：單源最短路徑問題(確定起點或確定終點的最短路徑問題)、確定起點終點的最短路徑問題(兩節(jié)點之間的最短路徑)1、Dijkstra算法：用鄰接矩陣a表示帶權(quán)有向圖，d為從v0出發(fā)到圖上其余各頂點可能達到的最短路徑長度值，以v0為起點做一次dijkstra,便可以求出從結(jié)點v0到其他結(jié)點的最短路徑長度代碼：proceduredijkstra(v0：longint)；//v0為起點做一次dijkstrabegin//a數(shù)組是鄰接矩陣，a[i,j]表示i到j(luò)的距離，無邊就為maxlongintfori:=1tondod[i]:=a[vO,i];//初始化d數(shù)組(用于記錄從v0到結(jié)點i的最短路徑)，fillchar(visit,sizeof(visit),false);//每個結(jié)點都未被連接到路徑里visit[v0]:=true;//已經(jīng)連接v0結(jié)點fori:=1ton-1do//剩下n_l個節(jié)點未加入路徑里；beginmin:二maxlongint;//初始化minforj:=1tondo//找從v0開始到目前為止，哪個結(jié)點作為下一個連接起點(*可優(yōu)化)if(notvisit[j])and(min>d[j])then//結(jié)點k要未被連接進去且最小beginmin:=d[j];k:=j;end;visit[k]:二true;//連接進去forj:=1tondo//刷新數(shù)組d,通過k來更新到達未連接進去的節(jié)點最小值，if(notvisit[j])and(d[j]>d[k]+a[k,j])thend[j]:=a[k,j]+d[k];end;writeln(d[n]);//結(jié)點v0到結(jié)點n的最短路。思考：在實現(xiàn)步驟時，效率較低需要0(n),使總復(fù)雜度達到0(12)。對此可以考慮用堆這種數(shù)據(jù)結(jié)構(gòu)進行優(yōu)化，使此步驟復(fù)雜度降為0(log(n))(總復(fù)雜度降為0(nlog(n))。實現(xiàn)：1.將與源點相連的點加入堆(小根堆)，并調(diào)整堆。選出堆頂元素u(即代價最小的元素)，從堆中刪除，并對堆進行調(diào)整。處理與u相鄰(即下一個)未被訪問過的，滿足三角不等式的頂點:若該點在堆里，更新距離，并調(diào)整該元素在堆中的位置。:若該點不在堆里，加入堆，更新堆。若取到的u為終點，結(jié)束算法；否則重復(fù)步驟2、3。**優(yōu)化代碼：(DIJKSTRA+HEAP)programSSSP;｛singlesourceshortestpath｝｛假設(shè)一個圖的最大節(jié)點數(shù)為1000，所有運算在integer范圍內(nèi)｝｛程序目標：給定有向圖的鄰接表，求出節(jié)點1到節(jié)點n的最短路徑長度｝constmaxn=1000;｛最大節(jié)點數(shù)｝varn:integer;｛節(jié)點個數(shù)｝list:array[1..maxn,1..maxn]ofinteger;｛4^接矩陣，表示邊的長度｝count:integer;｛堆內(nèi)元素個數(shù)計數(shù)器｝heap:array[l..maxn]ofinteger;｛heap[i]表示堆內(nèi)的第i的元素的節(jié)點編號｝pos:array[l..maxn]ofinteger;｛表示編號為i的元素在堆內(nèi)的位置｝key:array[l..maxn]ofinteger;｛表示節(jié)點1到節(jié)點i的最短距離｝exist:array[l..maxn]ofboolean;｛表示節(jié)點i是否存在于堆中｝i,j,now:integer;procedureswap(vari,j:integer);｛-交換整數(shù)i和j｝//省略procedureheapify(p:integer);｛向下調(diào)整堆的過程｝varbest:integer;beginbest:=p;//下面兩個if是分別判斷根和左、右孩子最短距離的大小if(p*2<=count)and(key[heap[p*2]]<key[heap[best]])thenbest:=p*2;if(p*2+1<=count)and(key[heap[p*2+1]]<key[heap[best]])thenbest:=p*2+1;ifbest〈〉pthen//若根有所變動，即跟比左右孩子都大(最短距離)beginswap(pos[heap[p]],pos[heap[best]]);//互換節(jié)點heap[p]、heap[best]在堆的位置swap(heap[p],heap[best]);//互換堆中元素p、bestheapify(best);//繼續(xù)調(diào)整互換后的元素bestend;end;proceduremodify(id,new_key:integer);｛判斷new_key與key[id]大小，并修改key[id]大?。齰arp:integer;beginif(new_key〈key[id])thenbegin//修改key[id]:=new_key;//更新最短距離p:=pos[id];//結(jié)點id在堆中的位置while(p>1)and(key[heap[p]]<key[heap[pdiv2]｛父｝])do//向上調(diào)整beginswap(pos[heap[p]],pos[heap[pdiv2]]);swap(heap[p],heap[pdiv2]);p:=pdiv2;//更上一層end;end;end;procedureextract(扌由出)(varid,dis:integer);｛讀取堆中最小元素的節(jié)點編號和節(jié)點1到該節(jié)點的距離｝beginid:=heap[1];//堆頂dis:=key[id];dec(count);//出堆if(count〉0)then//堆里還有元素beginswap(pos[heap[1]],pos[heap[count+1]]);//堆頂?shù)脑睾偷赾ount+1個元素換位置swap(heap[l],heap[count+1]);//把堆頂?shù)脑厝拥絚ount后面去，heapify(l);//此時堆頂不一定是最小的~扔到下面去，把最小的搞上來。end;end;beginreadln(n);init；//讀入鄰接矩陣，沒有連線的為maxint；省略fori:=1tondo｛初始化｝beginexist[i]:二true;//所有元素入堆pos[i]:=i;heap[i]:=i;key[i]:=maxint;end;count:=n;key[1]:=0;｛dijkstra算法的主要操作｝while(count>0)dobeginextract(i,now);exist[i]:=false;ifnow二maxintthenbreak;//無路可走了，overforj:=1tondoif(exist[j])thenmodify(j,now+list[i,j]);end;｛輸出｝ifkey[n]=maxintthenwriteln('NotConnected!')節(jié)點1和節(jié)點n不連通｝elsewriteln(key[n]);｛連通｝end.SPFA+(前向星、循環(huán)隊列、鄰接表、鏈表)2、SPFA算法(ShortestPathFasterAlgorithm)：spfa算法是西南交通大學(xué)段凡丁于1994年發(fā)表的.簡介：給定的圖存在負權(quán)邊時，dijkstra等便無用武之地，spfa算法便派上用場了。若有向加權(quán)圖G不存在負權(quán)回路，即最短路徑一定存在，用數(shù)組d記錄每個結(jié)點的最短路徑估計值，用鄰接表來存儲圖G。采取方法是動態(tài)逼近法：設(shè)立一個隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，且用到達u點當前的最短路徑估計值d[u]對點u所指向的結(jié)點v進行松弛操作，若v點的最短路徑估計值有所調(diào)整，且v點不在當前的隊列中，就將v點放入隊尾(已在隊列里就不用放到隊尾)。這樣不斷從隊列中取出結(jié)點來進行松弛操作，直至隊列空為止。若某點入隊的次數(shù)超過n次，則存在負環(huán)，spfa無法處理這樣的圖。定理:只要最短路徑存在，spfa算法必定能求出最小值。證明：松弛操作原理：“三角形兩邊之和大于第三邊”，在信息學(xué)中稱三角不等式。每次將點放入隊尾，都是經(jīng)松弛操作達到的。所謂對i,j進行松弛，即if(d[j]>d[i]+w[i,j])thend[j]:=d[i]+w[i,j]，每次優(yōu)化都可能將某個點v的最短路徑估計值d[v]變小，d數(shù)組將會越來越小。由于圖中不存在負權(quán)回路，所以每個結(jié)點都有最短路徑值，算法不會無限執(zhí)行下去，隨著d值的逐漸變小，到最短路徑值時，算法結(jié)束，這時的最短路徑估計值就是對應(yīng)結(jié)點的最短路徑值。

時間復(fù)雜度：O(ke),k為所有頂點進隊的平均次數(shù)，可以證明k一般小于等于2。*實現(xiàn)方法：建立一個隊列，初始時隊列里只有起始點，用d數(shù)組記錄起始點到所有點的最短路徑(該表格的初始值要賦為極大值，該點到他本身的路徑賦為0)。然后執(zhí)行松弛操作，用隊列里有的點去刷新起始點到所有點的最短路，如果刷新成功且被刷新點不在隊列中則把該點加入到隊列最后。重復(fù)執(zhí)行直到隊列為空求路徑方案：若這幅圖是地圖的模型，除了算出最短路徑長度，還要知道路徑方案。設(shè)path數(shù)組，path[i]表示從起點到i的最短路徑中，結(jié)點i之前一個結(jié)點的編號，我們只需在結(jié)點u對結(jié)點v進行松弛時，標記下path[v]=u即可。spfa算法采用鄰接表來存儲圖，方法是動態(tài)優(yōu)化逼近法。算法中用隊列queue用來保存待優(yōu)化的結(jié)點，優(yōu)化時從隊首取出一個點w,并且用w點的當前路徑d[w]去調(diào)整相連各點的路徑值d[j]，若有調(diào)整，即d[j]的值改小，就將j點放入queue隊列以待進一步優(yōu)化。重復(fù)執(zhí)行，直至隊空。此時d數(shù)組便保存了從起點到各點的最短路徑值。實例：設(shè)有向圖g=｛v，e}，e={<v0,v1>,<v0,v4>,<v1,v2>,<v1,v4>,<v2,v3>,<v3,v4>,<v4,v2>}={2,10,3,7,4,5,6}，v={v0,vl,v2,v3,v4}，見上圖:算法執(zhí)行時各步的queue隊的值和d數(shù)組的值由下表所示。初婦第一步第二步第三步第四步第五步queueDqueueDqueueDqueueDqueueDqueueDVO0VI0￥40V20V300□c：-V42V22222cc-cc-5555□c?20丈?2099co109999分析：源點v0到v1、v2、v3、v4的最短路徑分別為2、5、9、9，結(jié)果顯然是正確的。spfa在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊就不可能重新入隊，但是spfa中一個點可能在出隊之后再次被一個點改進而入隊，再次用來改進其它的點，這樣反復(fù)迭代下去。標準spfa代碼：(以求結(jié)點t到結(jié)點s的最短路為例，稍加修改即為單源最短路)constmaxp=10000;｛最大結(jié)點數(shù)｝varp,c,s,t:longint;｛p結(jié)點數(shù);c邊數(shù)；s起點；t終點｝a,b:array[1..maxp,0..maxp]oflongint;｛a[x,y]:x,y之間邊的權(quán);b[x,c]:與x相連的第c個邊的另一個結(jié)點y｝d:array[1..maxp]ofinteger;｛隊列｝v:array[1..maxp]ofboolean;｛是否在隊的標記｝dist:array[1..maxp]oflongint;｛到起點的最短路｝head,tail:longint;｛隊首/隊尾指針｝procedureinit;vari,x,y,z:longint;beginread(p,c);fori:=1tocdobeginreadln(x,y,z);｛x,y:—條邊的兩個結(jié)點；z:這條邊的權(quán)值｝inc(b[x,O]);b[x,b[x,O]]:=y;a[x,y]:=z;｛b[x,O]：以x為一個結(jié)點的邊的條數(shù)｝inc(b[y,0]);b[y,b[y,0]]:=x;a[y,x]:=z;end;readln(s,t);｛讀入起點與終點｝end;procedurespfa(s:longint);｛spfa｝vari,j,now,sum:longint;beginfillchar(d,sizeof(d),0);fillchar(v,sizeof(v),false);forj:=1topdodist[j]:=maxlongint;dist[s]:=0;v[s]:=true;d[l]:=s;｛隊列的初始狀態(tài),s為起點｝head:=1;tail:=1;whilehead<=taildo｛隊列不空｝beginnow:=d[head];｛取隊首元素｝fori:=1tob[now,0]doifdist[b[now,i]]>dist[now]+a[now,b[now,i]]thenbegindist[b[now,i]]:=dist[now]+a[now,b[now,i]];｛修改最短路｝ifnotv[b[now,i]]then｛擴展結(jié)點入隊｝begininc(tail);d[tail]:=b[now,i];v[b[now,i]]:=true;end;end;v[now]:=false;｛釋放結(jié)點，此節(jié)點有可能下次用來松弛其它節(jié)點｝inc(head);｛出隊｝end;writeln(dist[t]);end;begininit;spfa(s);end.**SPFA+前向星優(yōu)化前向星：星形(star)表示法的思想與鄰接表表示法有一定的相似之處。對每個節(jié)點，也是記錄從該節(jié)點出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數(shù)組表示，而是在該數(shù)組中首先存放從節(jié)點1出發(fā)的所有弧，然后接著存放從節(jié)點2出發(fā)的所有孤，依此類推，最后存放從節(jié)點n出發(fā)的所有孤。對每條弧，要依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。這實際上相當于對所有弧給出了一個順序和編號，只是從同一節(jié)點出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個節(jié)點出發(fā)的所有弧，我們一般還用一個數(shù)組記錄每個節(jié)點出發(fā)的弧的起始地址(即弧的編號)。在這種表示法中，可以快速檢索從每個節(jié)點出發(fā)的所有弧，這種星形表示法稱為前向星形(forwardstar)表示法。例弧(1,2))(1,3))(2,4))(3,2))(4,3))(4,5))(5,3)和(5,4)上的權(quán)分別為8、9、6、4、0、3、6、7。此時該網(wǎng)絡(luò)圖可以用前向星形表示法表示如下：節(jié)點對應(yīng)的出弧的起始地址編號數(shù)組(記為point)和記錄弧信息的數(shù)組：；節(jié)點號i1—34561[起始地址point[i]134579Jpoint[n+1]=m+1。對于節(jié)點i，其對應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為[point[i],point[i+1]T],如果point[i]=point[i+1]，則節(jié)點i沒有出弧。在前向星形表示法中，弧被編號后有序存放，并增加一個數(shù)組(point)記錄每個節(jié)點出發(fā)的弧的起始編號。當點數(shù)多或兩點間有多條弧時，一般的數(shù)據(jù)結(jié)構(gòu)不能用時才考慮用前向星，前向星的缺點:不能用起點直接終點定位,如果程序必須要定位的話,我們也不能示弱,最好不要用樸素的方法定位，這樣很花時間的，用二分的思想進行查找前向星的用途：最常用的是來優(yōu)化spfa，最基本的前向星優(yōu)化的spfa(有向圖)代碼：typerec=recordx,y,v:longint;end;vara:array[1..1000]ofrec;vis:array[1..2000]ofboolean;//是否在隊列里q,d,f:array[1..2001]oflongint;n,m,i,s,t,k,head,tail:longint;//s、t分別為起、終點procedureqsort(l,r:longint);//按起點排序procedurespfa(s:longint);beginfillchar(vis,sizeof(vis),false);fori:=1tondod[i]:=maxlongint;//初始化d[s]:=0;//記錄s到其他點的最短路徑值head:=0;tail:=1;q[1]:=s;vis[s]:=true;//s起點入隊repeatinc(head);k:=q[head];fori:=f[k]tof[k+1]-1do//枚舉起點為結(jié)點q[head]的所有邊ifd[k]+a[i].v<d[a[i].y]thenbegind[a[i].y]:=d[k]+a[i].v;ifnotvis[a[i].y]thenbegininc(tail);q[tail]:=a[i].y;vis[a[i].y]:=true;end;end;vis[k]:=false;untilhead=tail;end;beginreadln(n,m);fori:=1tomdoreadln(a[i].x,a[i].y,a[i].v);//初始化前向星qsort(1,m);fori:=1tomdoiff[a[i].x]=0thenf[a[i].x]:=i;f[n+1]:=m+1;fori:=ndownto1doiff[i]=0thenf[i]:=f[i+1];readln(s,t);spfa(s);writeln(d[t]);end.spfa+前向星例題：1、 Vijos的P1082叢林探險便可以用前向星+SPFA快速解決2、 sweetbutter香甜的黃油描述：農(nóng)夫john發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道n(1〈二n〈=500)只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。農(nóng)夫john很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。農(nóng)夫john知道每只奶牛都在各自喜歡的牧場(一個牧場不一定只有一頭牛)。給出各頭牛在的牧場和牧場間的路線，找出使所有牛到達的路程和最短的牧場(他將把糖放在那)inputformat:(filebutter.in)第一行：三個數(shù)：奶牛數(shù)n,牧場數(shù)p(2〈二p〈=800),牧場間道路數(shù)c(1〈二c〈=1450)第二行到第n+1行：1到n頭奶牛所在的牧場號第n+2行到第n+c+1行：每行有三個數(shù)：相連的