spfa講義+前向星優(yōu)化.doc

SPFA算法求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm。 SPFA算法是西南交通大學(xué)段凡丁于1994年發(fā)表的. 從名字我們就可以看出，這種算法在效率上一定有過人之處。 很多時候，給定的圖存在負權(quán)邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，SPFA算法便派上用場了。 簡潔起見，我們約定有向加權(quán)圖G不存在負權(quán)回路，即最短路徑一定存在。當然，我們可以在執(zhí)行該算法前做一次拓撲排序，以判斷是否存在負權(quán)回路，但這不是我們討論的重點。 我們用數(shù)組d記錄每個結(jié)點的最短路徑估計值，而且用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設(shè)立一個先進先出的隊列用來保存待優(yōu)化的結(jié)點，優(yōu)化時每次取出隊首結(jié)點u，并且用u點當前的最短路徑估計值對離開u點所指向的結(jié)點v進行松弛操作，如果v點的最短路徑估計值有所調(diào)整，且v點不在當前的隊列中，就將v點放入隊尾。這樣不斷從隊列中取出結(jié)點來進行松弛操作，直至隊列空為止。 定理: 只要最短路徑存在，上述SPFA算法必定能求出最小值。 證明：每次將點放入隊尾，都是經(jīng)過松弛操作達到的。（松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在信息學(xué)中我們叫它三角不等式。所謂對i,j進行松弛，就是判定是否djdi+wi,j，如果該式成立則將dj減小到di+wi,j，否則不動。）換言之，每次的優(yōu)化將會有某個點v的最短路徑估計值dv變小。所以算法的執(zhí)行會使d越來越小。由于我們假定圖中不存在負權(quán)回路，所以每個結(jié)點都有最短路徑值。因此，算法不會無限執(zhí)行下去，隨著d值的逐漸變小，直到到達最短路徑值時，算法結(jié)束，這時的最短路徑估計值就是對應(yīng)結(jié)點的最短路徑值。（證畢） 期望的時間復(fù)雜度O(ke)， 其中k為所有頂點進隊的平均次數(shù)，可以證明k一般小于等于2。 實現(xiàn)方法：建立一個隊列，初始時隊列里只有起始點，在建立一個表格記錄起始點到所有點的最短路徑（該表格的初始值要賦為極大值，該點到他本身的路徑賦為0）。然后執(zhí)行松弛操作，用隊列里有的點去刷新起始點到所有點的最短路，如果刷新成功且被刷新點不在隊列中則把該點加入到隊列最后。重復(fù)執(zhí)行直到隊列為空 判斷有無負環(huán)：如果某個點進入隊列的次數(shù)超過N次則存在負環(huán)（SPFA無法處理帶負環(huán)的圖） 在一幅圖中，我們僅僅知道結(jié)點A到結(jié)點E的最短路徑長度是73，有時候意義不大。這附圖如果是地圖的模型的話，在算出最短路徑長度后，我們總要說明“怎么走”才算真正解決了問題。如何在計算過程中記錄下來最短路徑是怎么走的，并在最后將它輸出呢？Path數(shù)組，Pathi表示從S到i的最短路徑中，結(jié)點i之前的結(jié)點的編號。注意，是“之前”，不是“之后”。最短路徑算法的核心思想成為“松弛”，原理是三角形不等式，方法是上文已經(jīng)提及的。我們只需要在借助結(jié)點u對結(jié)點v進行松弛的同時，標記下Pathv = u，記錄的工作就完成了。SPFA算法采用圖的存儲結(jié)構(gòu)是鄰接表，方法是動態(tài)優(yōu)化逼近法。算法中設(shè)立了一個先進先出的隊列Queue用來保存待優(yōu)化的頂點，優(yōu)化時從此隊列里順序取出一個點w，并且用w點的當前路徑DW去優(yōu)化調(diào)整其它各點的路徑值Dj，若有調(diào)整，即Dj的值改小了，就將J點放入Queue隊列以待繼續(xù)進一步優(yōu)化。反復(fù)從Queue隊列里取出點來對當前最短路徑進行優(yōu)化，直至隊空不需要再優(yōu)化為止，此時D數(shù)組里就保存了從源點到各點的最短路徑值 。 下面舉一個實例來說明SFFA算法是怎樣進行的： 設(shè)有一個有向圖GV，E，其中，VV0,V1,V2,V3,V4，E,2,10,3,7,4,5,6，見下圖： 算法執(zhí)行時各步的Queue隊的值和D數(shù)組的值由下表所示。表一 實例圖SPFA算法執(zhí)行的步驟及結(jié)果初始第一步第二步第三步第四步第五步queueDqueueDqueueDqueueDqueueDqueueDV00V10V40V20V300V42V22222555599109999算法執(zhí)行到第五步后，隊Queue空，算法結(jié)束。源點V0到V1的最短路徑為2，到V2的最短路徑為5，到V3的最短路徑為9，到V4的最短路徑為9，結(jié)果顯然是正確的。SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復(fù)迭代下去。標準SPFA過程(以求某個結(jié)點t到某個結(jié)點s的最短路為例，稍加修改即為單源最短路) Pascal語言代碼const maxp=10000; 最大結(jié)點數(shù) var 變量定義 p,c,s,t:longint; p,結(jié)點數(shù);c,邊數(shù);s:起點;t:終點 a,b:array1.maxp,0.maxp of longint; ax,y存x,y之間邊的權(quán);bx,c存與x相連的第c個邊的另一個結(jié)點y d:array1.maxp of integer; 隊列 v:array1.maxp of boolean; 是否入隊的標記 dist:array1.maxp of longint; 到起點的最短路 head,tail:longint; 隊首/隊尾指針 procedure init; var i,x,y,z:longint; begin read(p,c); for i := 1 to c do begin readln(x,y,z); x,y:一條邊的兩個結(jié)點;z:這條邊的權(quán)值 inc(bx,0); bx,bx,0 := y; ax,y := z; bx,0：以x為一個結(jié)點的邊的條數(shù) inc(by,0); by,by,0 := x; ay,x := z; end; readln(s,t); 讀入起點與終點 end; procedure spfa(s:longint); SPFA var i,j,now,sum:longint; begin fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),false); for j := 1 to p do distj:=maxlongint; dists:=0; vs:=true;d1:=s;隊列的初始狀態(tài),s為起點 head:=1;tail:= 1; while headdistnow+anow,bnow,i then begin distbnow,i:= distnow+anow,bnow,i; 修改最短路 if not vbnow,i then 擴展結(jié)點入隊 begin inc(tail); dtail := bnow,i; vbnow,i := true; end; end; vnow := false; 釋放結(jié)點，一定要釋放掉，因為這節(jié)點有可能下次用來松弛其它節(jié)點inc(head); 出隊 end; end; procedure print; begin writeln(distt); end; begin init; spfa(s); print; end. 前向星優(yōu)化星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節(jié)點，它也是記錄從該節(jié)點出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數(shù)組表示。也就是說，在該數(shù)組中首先存放從節(jié)點1出發(fā)的所有弧，然后接著存放從節(jié)點2出發(fā)的所有孤，依此類推，最后存放從節(jié)點出發(fā)的所有孤。對每條弧，要依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。這實際上相當于對所有弧給出了一個順序和編號，只是從同一節(jié)點出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個節(jié)點出發(fā)的所有弧，我們一般還用一個數(shù)組記錄每個節(jié)點出發(fā)的弧的起始地址（即弧的編號）。在這種表示法中，可以快速檢索從每個節(jié)點出發(fā)的所有弧，這種星形表示法稱為前向星形（forward star）表示法。例如，在例7所示的圖中，仍然假設(shè)?。?,2），（l,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ù)組（記為）節(jié)點號123456起始地址134679記錄弧信息的數(shù)組弧編號12345678起點11234455終點23423534權(quán)89640367在數(shù)組中，其元素個數(shù)比圖的節(jié)點數(shù)多1（即），且一定有，。對于節(jié)點，其對應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為，如果，則節(jié)點沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實際上相當于有序存放的“弧表”。只是在前向星形表示法中，弧被編號后有序存放，并增加一個數(shù)組（）記錄每個節(jié)點出發(fā)的弧的起始編號。for i:=1 to m do readln(ai,bi,ei); qsort(1,m); for i:=1 to m do if fai=0 then fai:=i; fn+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; 通常用在點的數(shù)目太多，或兩點之間有多條弧的時候。一般在別的數(shù)據(jù)結(jié)構(gòu)不能使用的時候才考慮用前向星。除了不能直接用起點終點定位以外，前向星幾乎是完美的。 前向星最常用的是來優(yōu)化spfa最基本的前項性優(yōu)化的spfa(有向圖)var a,b,e:array1.1000 of longint; vis:array1.2000 of boolean; q,d,f:array1.2001 of longint; n,m,i,s,t:longint; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a(l+r) shr 1; repeat while aix do dec(j); if not(ij) then begin y:=ai; ai:=aj; aj:=y; y:=bi; bi:=bj; bj:=y; y:=ei; ei:=ej; ej:=y; inc(i); dec(j); end; until ij; if ir then qsort(i,r); if lj then qsort(l,j); end; procedure spfa(s:longint); var i,k,l,t:longint; begin fillchar(vis,sizeof(vis),0); for i:=1 to n do di:=maxlongint; ds:=0; l:=0; t:=1; q1:=s; viss:=true; repeat l:=l mod 10000 +1; k:=ql; for i:=fk to fk+1-1 do if dk+eidbi then begin dbi:=dk+ei; if not visbi then begin t:=t mod 10000 +1; qt:=bi; visbi:=true; end; end; visk:=false; until l=t; end; Begin readln(n,m); for i:=1 to m do readln(ai,bi,ei); qsort(1,m); for i:=1 to m do if fai=0 then fai:=i; fn+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; readln(s,t); spfa(s); writeln(dt); end. 例題1：Sweet Butter 香甜的黃油 描述 農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道N（1=N=500）只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。當然，他將付出額外的費用在奶牛上。 農(nóng)夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。 農(nóng)夫John知道每只奶牛都在各自喜歡的牧場（一個牧場不一定只有一頭牛）。給出各頭牛在的牧場和牧場間的路線，找出使所有牛到達的路程和最短的牧場（他將把糖放在那） 格式 PROGRAM NAME : butter INPUT FORMAT : (file butter.in) 第一行: 三個數(shù)：奶牛數(shù)N，牧場數(shù)P（2=P=800），牧場間道路數(shù)C(1=C=1450) 第二行到第N+1行: 1到N頭奶牛所在的牧場號 第N+2行到第N+C+1行： 每行有三個數(shù)：相連的牧場A、B，兩牧場間距離D（1=D=255），當然,連接是雙向的 OUTPUT FORMAT : (file butter.out) 一行 輸出奶牛必須行走的最小的距離和 SAMPLE INPUT 3 4 52341 2 11 3 52 3 72 4 33 4 5program butter;var f1,f2:text; n,p,c:longint; count:array1.800of longint; a,b:array1.800,0.800of longint; d:array1.20000 of integer; v:array1.800 of boolean; dist:array1.800 of longint; head,tail:longint; ans:longint;procedure init; var i,j,x,y,z:longint; begin assign(f1,butter.in);reset(f1); assign(f2,butter.out);rewrite(f2); readln(f1,N,P,C); fillchar(count,sizeof(count),0); for i:=1 to n do begin read(f1,x); inc(countx); end; for i:=1 to p do for j:=1 to p do ai,j:=maxlongint; for i:=1 to c do begin read(f1,x,y,z); inc(bx,0)