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

1、SPFA算法求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm。 SPFA算法是西南交通大學(xué)段凡丁于1994年發(fā)表的. 從名字我們就可以看出，這種算法在效率上一定有過(guò)人之處。 很多時(shí)候，給定的圖存在負(fù)權(quán)邊，這時(shí)類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過(guò)高，SPFA算法便派上用場(chǎng)了。 簡(jiǎn)潔起見，我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判颍耘袛嗍欠翊嬖谪?fù)權(quán)回路，但這不是我們討論的重點(diǎn)。 我們用數(shù)組d記錄每個(gè)結(jié)點(diǎn)的最短路徑估計(jì)值，而且用鄰接表來(lái)存儲(chǔ)圖G。

2、我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對(duì)離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來(lái)進(jìn)行松弛操作，直至隊(duì)列空為止。 定理: 只要最短路徑存在，上述SPFA算法必定能求出最小值。 證明：每次將點(diǎn)放入隊(duì)尾，都是經(jīng)過(guò)松弛操作達(dá)到的。（松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在信息學(xué)中我們叫它三角不等式。所謂對(duì)i,j進(jìn)行松弛，就是判定是否dj>di+wi,j，如果該式成立則將dj減小到di+wi,

3、j，否則不動(dòng)。）換言之，每次的優(yōu)化將會(huì)有某個(gè)點(diǎn)v的最短路徑估計(jì)值dv變小。所以算法的執(zhí)行會(huì)使d越來(lái)越小。由于我們假定圖中不存在負(fù)權(quán)回路，所以每個(gè)結(jié)點(diǎn)都有最短路徑值。因此，算法不會(huì)無(wú)限執(zhí)行下去，隨著d值的逐漸變小，直到到達(dá)最短路徑值時(shí)，算法結(jié)束，這時(shí)的最短路徑估計(jì)值就是對(duì)應(yīng)結(jié)點(diǎn)的最短路徑值。（證畢） 期望的時(shí)間復(fù)雜度O(ke)， 其中k為所有頂點(diǎn)進(jìn)隊(duì)的平均次數(shù)，可以證明k一般小于等于2。 實(shí)現(xiàn)方法：建立一個(gè)隊(duì)列，初始時(shí)隊(duì)列里只有起始點(diǎn)，在建立一個(gè)表格記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值，該點(diǎn)到他本身的路徑賦為0）。然后執(zhí)行松弛操作，用隊(duì)列里有的點(diǎn)去刷新起始點(diǎn)到所有點(diǎn)的最短路，

4、如果刷新成功且被刷新點(diǎn)不在隊(duì)列中則把該點(diǎn)加入到隊(duì)列最后。重復(fù)執(zhí)行直到隊(duì)列為空 判斷有無(wú)負(fù)環(huán)：如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)N次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖） 在一幅圖中，我們僅僅知道結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短路徑長(zhǎng)度是73，有時(shí)候意義不大。這附圖如果是地圖的模型的話，在算出最短路徑長(zhǎng)度后，我們總要說(shuō)明“怎么走”才算真正解決了問題。如何在計(jì)算過(guò)程中記錄下來(lái)最短路徑是怎么走的，并在最后將它輸出呢？Path數(shù)組，Pathi表示從S到i的最短路徑中，結(jié)點(diǎn)i之前的結(jié)點(diǎn)的編號(hào)。注意，是“之前”，不是“之后”。最短路徑算法的核心思想成為“松弛”，原理是三角形不等式，方法是上文已經(jīng)提及的。我們只需要在借助結(jié)

5、點(diǎn)u對(duì)結(jié)點(diǎn)v進(jìn)行松弛的同時(shí)，標(biāo)記下Pathv = u，記錄的工作就完成了。 SPFA算法采用圖的存儲(chǔ)結(jié)構(gòu)是鄰接表，方法是動(dòng)態(tài)優(yōu)化逼近法。算法中設(shè)立了一個(gè)先進(jìn)先出的隊(duì)列Queue用來(lái)保存待優(yōu)化的頂點(diǎn)，優(yōu)化時(shí)從此隊(duì)列里順序取出一個(gè)點(diǎn)w，并且用w點(diǎn)的當(dāng)前路徑DW去優(yōu)化調(diào)整其它各點(diǎn)的路徑值Dj，若有調(diào)整，即Dj的值改小了，就將J點(diǎn)放入Queue隊(duì)列以待繼續(xù)進(jìn)一步優(yōu)化。反復(fù)從Queue隊(duì)列里取出點(diǎn)來(lái)對(duì)當(dāng)前最短路徑進(jìn)行優(yōu)化，直至隊(duì)空不需要再優(yōu)化為止，此時(shí)D數(shù)組里就保存了從源點(diǎn)到各點(diǎn)的最短路徑值 。 下面舉一個(gè)實(shí)例來(lái)說(shuō)明SFFA算法是怎樣進(jìn)行的： 設(shè)有一個(gè)有向圖GV，E，其中，VV0,V1,V2,

6、V3,V4，E<V0,V1>,<V0,V4>,<V1,V2>,<V1,V4>,<V2,V3>,<V3,V4>,<V4,V2>2,10,3,7,4,5,6，見下圖： 算法執(zhí)行時(shí)各步的Queue隊(duì)的值和D數(shù)組的值由下表所示。表一 實(shí)例圖SPFA算法執(zhí)行的步驟及結(jié)果初始第一步第二步第三步第四步第五步queueDqueueDqueueDqueueDqueueDqueueDV00V10V40V20V300V42V22222555599109999算法執(zhí)行到第五步后，隊(duì)Queue空，算法結(jié)束。源點(diǎn)V0到V1的最短路徑為2，

7、到V2的最短路徑為5，到V3的最短路徑為9，到V4的最短路徑為9，結(jié)果顯然是正確的。SPFA 在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之后，過(guò)了一段時(shí)間可能本身被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。標(biāo)準(zhǔn)SPFA過(guò)程(以求某個(gè)結(jié)點(diǎn)t到某個(gè)結(jié)點(diǎn)s的最短路為例，稍加修改即為單源最短路) Pascal語(yǔ)言代碼const maxp=10000; 最大結(jié)點(diǎn)數(shù) var 變量定義 p,c,s,t:longint; p,結(jié)點(diǎn)數(shù);c,邊數(shù);s:起點(diǎn);t:終點(diǎn) a,b:arr

8、ay1.maxp,0.maxp of longint; ax,y存x,y之間邊的權(quán);bx,c存與x相連的第c個(gè)邊的另一個(gè)結(jié)點(diǎn)y d:array1.maxp of integer; 隊(duì)列 v:array1.maxp of boolean; 是否入隊(duì)的標(biāo)記 dist:array1.maxp of longint; 到起點(diǎn)的最短路 head,tail:longint; 隊(duì)首/隊(duì)尾指針 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:一條邊的兩個(gè)結(jié)點(diǎn);z:

9、這條邊的權(quán)值 inc(bx,0); bx,bx,0 := y; ax,y := z; bx,0：以x為一個(gè)結(jié)點(diǎn)的邊的條數(shù) inc(by,0); by,by,0 := x; ay,x := z; end; readln(s,t); 讀入起點(diǎn)與終點(diǎn) 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:=tru

10、e;d1:=s;隊(duì)列的初始狀態(tài),s為起點(diǎn) head:=1;tail:= 1; while head<=tail do 隊(duì)列不空 begin now:=dhead; 取隊(duì)首元素 for i:=1 to bnow,0 do if distbnow,i>distnow+anow,bnow,i then begin distbnow,i:= distnow+anow,bnow,i; 修改最短路 if not vbnow,i then 擴(kuò)展結(jié)點(diǎn)入隊(duì) begin inc(tail); dtail := bnow,i; vbnow,i := true; end; end; vnow := fal

11、se; 釋放結(jié)點(diǎn)，一定要釋放掉，因?yàn)檫@節(jié)點(diǎn)有可能下次用來(lái)松弛其它節(jié)點(diǎn)inc(head); 出隊(duì) end; end; procedure print; begin writeln(distt); end; begin init; spfa(s); print; end. 前向星優(yōu)化星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對(duì)每個(gè)節(jié)點(diǎn)，它也是記錄從該節(jié)點(diǎn)出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個(gè)單一的數(shù)組表示。也就是說(shuō)，在該數(shù)組中首先存放從節(jié)點(diǎn)1出發(fā)的所有弧，然后接著存放從節(jié)點(diǎn)2出發(fā)的所有孤，依此類推，最后存放從節(jié)點(diǎn)出發(fā)的所有孤。對(duì)每條弧，要依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)

12、值等有關(guān)信息。這實(shí)際上相當(dāng)于對(duì)所有弧給出了一個(gè)順序和編號(hào)，只是從同一節(jié)點(diǎn)出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始地址（即弧的編號(hào)）。在這種表示法中，可以快速檢索從每個(gè)節(jié)點(diǎn)出發(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。此時(shí)該網(wǎng)絡(luò)圖可以用前向星形表示法表示如下： 節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為）節(jié)點(diǎn)號(hào)123456

13、起始地址134679記錄弧信息的數(shù)組弧編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367在數(shù)組中，其元素個(gè)數(shù)比圖的節(jié)點(diǎn)數(shù)多1（即），且一定有，。對(duì)于節(jié)點(diǎn)，其對(duì)應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為，如果，則節(jié)點(diǎn)沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實(shí)際上相當(dāng)于有序存放的“弧表”。只是在前向星形表示法中，弧被編號(hào)后有序存放，并增加一個(gè)數(shù)組（）記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始編號(hào)。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; f

14、n+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; 通常用在點(diǎn)的數(shù)目太多，或兩點(diǎn)之間有多條弧的時(shí)候。一般在別的數(shù)據(jù)結(jié)構(gòu)不能使用的時(shí)候才考慮用前向星。除了不能直接用起點(diǎn)終點(diǎn)定位以外，前向星幾乎是完美的。 前向星最常用的是來(lái)優(yōu)化spfa最基本的前項(xiàng)性優(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:longin

15、t); var i,j,x,y:longint; begin i:=l; j:=r; x:=a(l+r) shr 1; repeat while ai<x do inc(i); while aj>x do dec(j); if not(i>j) 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 i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); en

16、d; 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+ei<dbi then begin dbi:=dk+ei; if not visbi then begin t:=t mod 10000 +1; qt:=b

17、i; 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)做出全威斯康辛州最甜的

18、黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道N（1<=N<=500）只奶牛會(huì)過(guò)來(lái)舔它，這樣就能做出能賣好價(jià)錢的超甜黃油。當(dāng)然，他將付出額外的費(fèi)用在奶牛上。 農(nóng)夫John很狡猾。像以前的巴甫洛夫，他知道他可以訓(xùn)練這些奶牛，讓它們?cè)诼牭解徛晻r(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。 農(nóng)夫John知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng)（他將把糖放在那） 格式 PROGRAM NAME : butter INPUT FORMAT : (file butter.in)

19、第一行: 三個(gè)數(shù)：奶牛數(shù)N，牧場(chǎng)數(shù)P（2<=P<=800），牧場(chǎng)間道路數(shù)C(1<=C<=1450) 第二行到第N+1行: 1到N頭奶牛所在的牧場(chǎng)號(hào) 第N+2行到第N+C+1行： 每行有三個(gè)數(shù)：相連的牧場(chǎng)A、B，兩牧場(chǎng)間距離D（1<=D<=255），當(dāng)然,連接是雙向的 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;&

20、#160;   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

21、;    ans:longint;procedure init;    var      i,j,x,y,z:longint;     begin      assign(f1,'butter.in');reset(f1);      assign(f2,'butter.out');rewrite(f2);  

22、60;    readln(f1,N,P,C);      fillchar(count,sizeof(count),0);       for i:=1 to n do begin        read(f1,x);        inc(countx);      

23、;                                             end;      

24、;                                              for i:=1 to p do   

25、;     for j:=1 to p do          ai,j:=maxlongint;            for i:=1 to c do begin         read(f1,x,y,z);        

26、                                        inc(bx,0);bx,bx,0:=y;ax,y:=z;       

27、0;         inc(by,0);by,by,0:=x;ay,x:=z;            end;       end; procedure spfa(s:longint);    var      i,j,now,sum:longint;    

28、0;  begin      fillchar(d,sizeof(d),0);      fillchar(v,sizeof(v),false);      for i:=1 to p do disti:=maxlongint;      dists:=0;vs:=true;d1:=s;      head:=1;tail:=1;

29、60;     while head<=tail do begin        now:=dhead;        for i:=1 to bnow,0 do                        &#

30、160;         if distbnow,i>distnow+anow,bnow,i then begin          distbnow,i:=distnow+anow,bnow,i;                   if not vbnow,i then

31、 begin                                 inc(tail);                     

32、               dtail:=bnow,i;           vbnow,i:=true;                                end;