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

1、SPFA 算法求單源最短路的SPFA 算法的全稱是：ShortestPathFaster Algorithm 。SPFA 算法是西南交通大學(xué)段凡丁于1994 年發(fā)表的 .從名字我們就可以看出，這種算法在效率上一定有過人之處。很多時(shí)候，給定的圖存在負(fù)權(quán)邊，這時(shí)類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，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ì)值，而且用鄰接表來存

2、儲(chǔ)圖G。我們采取的方法是動(dòng)態(tài)逼近法：設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來保存待優(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)來進(jìn)行松弛操作，直至隊(duì)列空為止。定理 : 只要最短路徑存在，上述SPFA 算法必定能求出最小值。證明：每次將點(diǎn)放入隊(duì)尾，都是經(jīng)過松弛操作達(dá)到的。（松弛操作的原理是著名的定理： “三角形兩邊之和大于第三邊，”在信息學(xué)中我們叫它三角不等式。 所謂對(duì) i,j 進(jìn)行松弛，就是判定是否 dj>di +wi,j ，

3、如果該式成立則將 dj 減小到 di+wi,j ，否則不動(dòng)。）換言之，每次的優(yōu)化將會(huì)有某個(gè)點(diǎn)v 的最短路徑估計(jì)值dv 變小。所以算法的執(zhí)行會(huì)使 d 越來越小。由于我們假定圖中不存在負(fù)權(quán)回路，所以每個(gè)結(jié)點(diǎn)都有最短路徑值。因此，算法不會(huì)無限執(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）。

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

5、徑算法的核心思想成為“松弛”，原理是三角形不等式，方法是上文已經(jīng)提及的。我們只需要在借助結(jié)點(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 用來保存待優(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)來對(duì)當(dāng)前最短路徑進(jìn)行優(yōu)化，直至隊(duì)空不需要再優(yōu)化為止，此時(shí) D 數(shù)組里就保存了從源點(diǎn)到各

6、點(diǎn)的最短路徑值 。下面舉一個(gè)實(shí)例來說明 SFFA 算法是怎樣進(jìn)行的：設(shè)有一個(gè)有向圖GV ，E，其中， VV0,V1,V2,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é)果初始第一步第二步第三步第四步第五步queDqueDqueDqueDqueDque DueueueueueueV00V10V4

7、0V20V300V42V22222555599109999算法執(zhí)行到第五步后，隊(duì)Queue空，算法結(jié)束。源點(diǎn)V0 到 V1 的最短路徑為 2，到 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)過其它的點(diǎn)之后，過了一段時(shí)間可能本身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。標(biāo)準(zhǔn) SPFA 過程(以求某個(gè)結(jié)點(diǎn)t 到某個(gè)結(jié)點(diǎn)s 的最短路為例，稍加修改即為單源最短路 )Pas

8、cal語(yǔ)言代碼constmaxp=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:array1.maxp,0.maxpof longint;ax,y 存 x,y 之間邊的權(quán) ;bx,c 存與 x 相連的第c 個(gè)邊的另一個(gè)結(jié)點(diǎn)yd:array1.maxpofinteger;隊(duì)列 v:array1.maxpofboolean;是否入隊(duì)的標(biāo)記dist:array1.maxpoflongint;到起點(diǎn)的最短路head,tail:longint;隊(duì)首 / 隊(duì)尾指針procedureinit;vari,x,y,z:l

9、ongint;beginread(p,c);for i := 1 to c dobeginreadln(x,y,z);x,y:一條邊的兩個(gè)結(jié)點(diǎn);z: 這條邊的權(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;procedurespfa(s:longint);SPFAvar i,j,now,sum:longint;beginfillchar(d,sizeof(d),0);fillchar(v,sizeof(v),f

10、alse);for j := 1 to p do distj:=maxlongint;dists:=0;vs:=true;d1:=s;隊(duì)列的初始狀態(tài),s 為起點(diǎn) head:=1;tail:=1;whilehead<=taildo隊(duì)列不空beginnow:=dhead;取隊(duì)首元素 for i:=1to bnow,0doif distbnow,i>distnow+anow,bnow,ibeginthendistbnow,i:=distnow+anow,bnow,i;修改最短路if notvbnow,ithen擴(kuò)展結(jié)點(diǎn)入隊(duì)begininc(tail);dtail:= bnow,i;vbn

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

12、的所有孤。對(duì)每條弧，要依次存放其起點(diǎn)、終點(diǎn)、 權(quán)的數(shù)值等有關(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ò)圖可以用前向星形表示法

13、表示如下：節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為point ）節(jié)點(diǎn)號(hào) i123456起始地址 point (i )134679記錄弧信息的數(shù)組弧編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367在數(shù)組point 中，其元素個(gè)數(shù)比圖的節(jié)點(diǎn)數(shù)多1（即 n 1 ），且一定有point (1)1，point (n1)m1 。對(duì)于節(jié)點(diǎn)i ，其對(duì)應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為 point (i ), point (i1)1 ，如果point (i )point (i1) ，則節(jié)點(diǎn)i 沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實(shí)際上相當(dāng)于有序存放的“弧

14、表”。只是在前向星形表示法中，弧被編號(hào)后有序存放，并增加一個(gè)數(shù)組（point ）記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始編號(hào)。for i:=1 to m doreadln(ai,bi,ei);qsort(1,m);for i:=1 to m doif fai=0 then fai:=i;fn+1:=m+1;for i:=n downto 1 doif fi=0 then fi:=fi+1;通常用在點(diǎn)的數(shù)目太多， 或兩點(diǎn)之間有多條弧的時(shí)候。一般在別的數(shù)據(jù)結(jié)構(gòu)不能使用的時(shí)候才考慮用前向星。除了不能直接用起點(diǎn)終點(diǎn)定位以外，前向星幾乎是完美的。前向星最常用的是來優(yōu)化spfa最基本的前項(xiàng)性優(yōu)化的spfa( 有向圖 )

15、vara,b,e:array1.1000oflongint;vis:array1.2000of boolean;q,d,f:array1.2001of longint;n,m,i,s,t:longint;procedureqsort(l,r:longint);var i,j,x,y:longint;begini:=l;j:=r;x:=a(l+r)shr1;repeatwhileai<xdo inc(i);whileaj>xdo dec(j);if not(i>j)thenbeginy:=ai;ai:=aj;aj:=y;y:=bi;bi:=bj;bj:=y;y:=ei;ei:=

16、ej;ej:=y;inc(i);dec(j);end;untili>j;if i<rthenqsort(i,r);if l<jthenqsort(l,j);end;procedurespfa(s:longint);var i,k,l,t:longint;beginfillchar(vis,sizeof(vis),0);for i:=1to n do di:=maxlongint;ds:=0;l:=0;t:=1;q1:=s;viss:=true;repeatl:=lmod10000+1;k:=ql;for i:=fkto fk+1-1doif dk+ei<dbithenb

17、egindbi:=dk+ei;if notvisbithenbegint:=tmod10000+1;qt:=bi;visbi:=true;end;end;visk:=false;untill=t;end;Beginreadln(n,m);for i:=1to m doreadln(ai,bi,ei);qsort(1,m);fori:=1tomdoif fai=0thenfai:=i;fn+1:=m+1;fori:=ndownto1 doif fi=0thenfi:=fi+1;readln(s,t);spfa(s);writeln(dt);end.例題 1 ：SweetButter香甜的黃油描述

18、農(nóng)夫 John 發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道 N（1<=N<=500）只奶牛會(huì)過來舔它，這樣就能做出能賣好價(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 : butterINPUT FORM

19、AT :(file butter.in)第一行 : 三個(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)一行 輸出奶牛必須行走的最小的距離和SAMPLEINPUT3 4 52341 2 11 3 52 3 72 4 33 4 5program butter;varf1,f

20、2: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;vari,j,x,y,z:longint;beginassign(f1,'butter.in');reset(f1);assign(f2,'butter.out');

21、rewrite(f2);readln(f1,N,P,C);fillchar(count,sizeof(count),0);for i:=1 to n do beginread(f1,x);inc(countx);end;for i:=1 to p dofor j:=1 to p doai,j:=maxlongint;for i:=1 to c do beginread(f1,x,y,z);inc(bx,0);bx,bx,0:=y;ax,y:=z;inc(by,0);by,by,0:=x;ay,x:=z;end;end;procedure spfa(s:longint);vari,j,now,s

22、um:longint;beginfillchar(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;while head<=tail do beginnow:=dhead;for i:=1 to bnow,0doifdistbnow,i>distnow+anow,bnow,i then begindistbnow,i:=distnow+anow,bnow,i;if not vbnow,i thenb

23、egininc(tail);dtail:=bnow,i;vbnow,i:=true;end;end;vnow:=false;inc(head);end;sum:=0;for i:=1 to p doif counti<>0 theninc(sum,counti*disti);if ans>sum then ans:=sum;end;procedure main;vari:longint;beginans:=maxlongint;for i:=1 to p do spfa(i);end;begininit;main;writeln(f2,ans);close(f2);end.贈(zèng)

24、送以下學(xué)習(xí)資料和倍差倍問題學(xué)習(xí)目標(biāo)通過和倍、差倍問題的學(xué)習(xí)，除了掌握這類問題的解決方法以外，其重點(diǎn)要學(xué)習(xí)畫線段圖。二、基礎(chǔ)知識(shí)1. 和倍問題是已知兩個(gè)數(shù)的和及它們之間的倍數(shù)關(guān)系而求這兩個(gè)數(shù)各是多少的應(yīng)用題。基本的數(shù)量關(guān)系： 和÷ ( 倍數(shù) +1)=較小數(shù) ( 即 1 倍數(shù)、標(biāo)準(zhǔn)數(shù) )2. 差倍問題是已知兩個(gè)數(shù)的差及它們之間的倍數(shù)關(guān)系而求這兩個(gè)數(shù)各是多少的應(yīng)用題?；竟剑?差÷ ( 倍數(shù)的差 ) 標(biāo)準(zhǔn)數(shù) ( 一倍數(shù) )例題解析一、和倍問題例 1：某班為“希望工程”捐款，兩組少先隊(duì)員共交廢報(bào)紙 240 千克，第一組交的廢報(bào)紙是第二組的 3 倍，問兩組各交廢報(bào)紙多少千克？小結(jié)：

25、解答基本的和倍問題，先確定其中一個(gè)數(shù)作為標(biāo)準(zhǔn)數(shù) (1 倍數(shù) ) ，再找出兩數(shù)的和，及其相對(duì)應(yīng)的倍數(shù)關(guān)系， 這樣就可以求出標(biāo)準(zhǔn)數(shù)， 也就可求出另一個(gè)數(shù)(較大數(shù))?；镜臄?shù)量關(guān)系： 和÷ ( 倍數(shù) +1)=較小數(shù) ( 即 1 倍數(shù)、標(biāo)準(zhǔn)數(shù) )練一練： NBA球星姚明到底有多高？現(xiàn)在已知小明和姚明的身高和是 339 厘米，姚明的身高大約是小明身高的 2 倍。你能夠算出來嗎？例 2：哥哥原有 108 元，弟弟有 60 元，如果現(xiàn)在想把哥哥的錢調(diào)整到弟弟的 5 倍，弟弟應(yīng)給哥哥多少錢？練一練：妹妹有課外書 20 本，姐姐有課外書 25 本，姐姐給妹妹多少本后，妹妹課外書是姐姐的 2 倍？例 3

26、：二個(gè)同學(xué)共做了 23 道題。如果乙同學(xué)再多做 1 題，將是甲同學(xué)做的 2 倍，二個(gè)同學(xué)各做了幾題？例 4：熊貓水果店運(yùn)來水果 380 千克，其中蘋果比梨的 3 倍還少 40 千克，水果店運(yùn)來蘋果和梨各多少千克 ?練一練： 果園里種桃樹和梨樹共 340 棵 , 其中桃樹的棵數(shù)比梨樹的 3 倍多 20 棵，梨樹種了多少棵？例 5：三捆電線共長(zhǎng) 273 米，其中第二根的長(zhǎng)度是第一根長(zhǎng)度的 2 倍，第三根的長(zhǎng)度是第二根長(zhǎng)度的 2 倍。三根電線各多少米？練一練： 甲、乙、丙三數(shù)的和是78，甲數(shù)比乙數(shù)的2 倍多 4，乙數(shù)比丙數(shù)的3倍少 2。求這三個(gè)數(shù)。例 6：某小學(xué)有學(xué)生 975 人 . 全校男生人數(shù)是六年級(jí)學(xué)生人數(shù)的 4 倍少 23 人，全校女生人數(shù)是六年級(jí)學(xué)生人數(shù)的 3 倍多 11 人. 問全校有男、女生各多少人？二、差倍問題例 1：某小學(xué)參觀科普展覽，第一天參觀的人數(shù)比第二天多 200 人。已知第一天參觀的人數(shù)是第二天的 3 倍，兩天參觀的各是多少人？練一練：已知甲、乙兩個(gè)數(shù)的商是 4，而這兩個(gè)數(shù)的差是 30，那么這兩個(gè)數(shù)中較小的一個(gè)是多少？例 2：甲、乙兩車間原來人數(shù)相等，因工作需要，從甲車間調(diào)24 人到乙車間. 這時(shí)乙車間人數(shù)是甲車間的4 倍. 甲、乙兩個(gè)車間原