路由選擇算法改進(jìn)

1、Bellman-Ford算法及其優(yōu)化一、引言Bellman-Ford算法與另一個(gè)非常著名的Dijkstra算法一樣，用于求解單源 點(diǎn)最短路徑問題。Bellman-ford算法除了可求解邊權(quán)均非負(fù)的問題外，還可以解 決存在負(fù)權(quán)邊的問題（意義是什么，好好思考），而Dijkstra算法只能處理邊權(quán) 非負(fù)的問題，因此 Bellman-Ford算法的適用面要廣泛一些。但是，原始的 Bellman-Ford算法時(shí)間復(fù)雜度為O（VE），比Dijkstra算法的時(shí)間復(fù)雜度高，所 以常常被眾多的大學(xué)算法教科書所忽略，就連經(jīng)典的算法導(dǎo)論也只介紹了基 本的Bellman-Ford算法，在國(guó)內(nèi)常見的基本信息學(xué)奧賽教材

2、中也均未提及，因 此該算法的知名度與被掌握度都不如 Dijkstra算法。事實(shí)上，有多種形式的 Bellman-Ford算法的優(yōu)化實(shí)現(xiàn)。這些優(yōu)化實(shí)現(xiàn)在時(shí)間效率上得到相當(dāng)提升，例如 近一兩年被熱捧的SPFA（ Shortest-Path Faster Algoithm 更快的最短路徑算法） 算法的時(shí)間效率甚至由于Dijkstra算法，因此成為信息學(xué)奧賽選于經(jīng)常討論的話 題。然而，限于資料匱乏，有關(guān)Bellman-Ford算法的諸多問題常常困擾奧賽選 手。如：該算法值得掌握么？怎樣用編程語(yǔ)言具體實(shí)現(xiàn)？有哪些優(yōu)化？與SPFA 算法有關(guān)系么？本文試圖對(duì)Bellman-Ford算法做一個(gè)比較全面的介紹。

3、二、國(guó)內(nèi)外的研究現(xiàn)狀1、Dijkstra算法是典型最短路算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短 路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra 算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。2、Floyd算法適用于APSP（All Pairs Shortest Paths），是一種動(dòng)態(tài)規(guī)劃算法，稠密 圖效果最佳，邊權(quán)可正可負(fù)。此算法簡(jiǎn)單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對(duì)于稠 密圖，效率要高于執(zhí)行IVI次Dijkstra算法。優(yōu)點(diǎn)：容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡(jiǎn)單 缺點(diǎn)：時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。三、B

4、ellman-Ford算法思想Bellman-Ford算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點(diǎn)最短路徑 問題。對(duì)于給定的帶權(quán)(有向或無向)圖G= (V,E),其源點(diǎn)為s,加權(quán)函數(shù)w 是 邊集E的映射。對(duì)圖G運(yùn)行Bellman-Ford算法的結(jié)果是一個(gè)布爾值，表明 圖中是否存在著一個(gè)從源點(diǎn)s可達(dá)的負(fù)權(quán)回路。若不存在這樣的回路，算法將給 出從源點(diǎn)s到圖G的任意頂點(diǎn)v的最短路徑dv。Bellman-Ford算法流程分為三個(gè)階段：初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值dv -+s, ds 。； 迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V 中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼

5、近其最短距離；(運(yùn)行IvI-1次)檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如 果存在未收斂的頂點(diǎn)，則算法返回false，表明問題無解；否則算法返回true，并 且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在dv中。算法描述如下：Bellman-Ford(G,w,s) : boolean 圖 G，邊集函數(shù) w，s 為源點(diǎn)for each vertex v E V (G) do 初始化 1 階段dv +sds -0; /1階段結(jié)束for i=1 to lvl-1 do /2階段開始，雙重循環(huán)。for each edge (u,v) EE(G) do 邊集數(shù)組要用到，窮舉每條邊。If dv d

6、u+ w(u,v) then 松弛判斷dv=du+w(u,v) 松弛操作2階段結(jié)束for each edge (u,v) EE(G) doIf dv du+ w(u,v) thenExit falseExit true下面給出描述性證明：首先指出，圖的任意一條最短路徑既不能包含負(fù)權(quán)回路，也不會(huì)包含正權(quán)回 路，因此它最多包含lvl-1條邊。其次，從源點(diǎn)s可達(dá)的所有頂點(diǎn)如果存在最短路徑，則這些最短路徑構(gòu)成 一個(gè)以s為根的最短路徑樹。Bellman-Ford算法的迭代松弛操作，實(shí)際上就是按 頂點(diǎn)距離s的層次，逐層生成這棵最短路徑樹的過程。在對(duì)每條邊進(jìn)行1遍松弛的時(shí)候，生成了從s出發(fā)，層次至多為1的那

7、些樹 枝。也就是說，找到了與s至多有1條邊相聯(lián)的那些頂點(diǎn)的最短路徑；對(duì)每條邊 進(jìn)行第2遍松弛的時(shí)候，生成了第2層次的樹枝，就是說找到了經(jīng)過2條邊相連 的那些頂點(diǎn)的最短路徑.。因?yàn)樽疃搪窂阶疃嘀话琹vl-1條邊，所以，只需 要循環(huán)lvl-1次。每實(shí)施一次松弛操作，最短路徑樹上就會(huì)有一層頂點(diǎn)達(dá)到其最短距離，此后 這層頂點(diǎn)的最短距離值就會(huì)一直保持不變，不再受后續(xù)松弛操作的影響。(但是， 每次還要判斷松弛，這里浪費(fèi)了大量的時(shí)間，怎么優(yōu)化？單純的優(yōu)化是否可行？) 如果沒有負(fù)權(quán)回路，由于最短路徑樹的高度最多只能是lvl-1，所以最多經(jīng)過 lvl-1遍松弛操作后，所有從s可達(dá)的頂點(diǎn)必將求出最短距離。如果d

8、v仍保持 +皿則表明從s到v不可達(dá)。如果有負(fù)權(quán)回路，那么第lvl-1遍松弛操作仍然會(huì)成功，這時(shí)，負(fù)權(quán)回路上 的頂點(diǎn)不會(huì)收斂。例如對(duì)于上圖，邊上方框中的數(shù)字代表權(quán)值，頂點(diǎn)A,B,C之間存在負(fù)權(quán)回路。 S是源點(diǎn)，頂點(diǎn)中數(shù)字表示運(yùn)行Bellman-Ford算法后各點(diǎn)的最短距離估計(jì)值。此時(shí)da的值為1，大于dc+w(c,a)的值-2，由此da可以松弛為-2，然后 db又可以松弛為-5,dc又可以松弛為-7.下一個(gè)周期，da又可以更新為更小的 值，這個(gè)過程永遠(yuǎn)不會(huì)終止。因此，在迭代求解最短路徑階段結(jié)束后，可以通過 檢驗(yàn)邊集E的每條邊(u,v)是否滿足關(guān)系式dv du+ w(u,v)來判斷是否存在負(fù) 權(quán)回

9、路。Bellman-Ford算法能在一般情況下(存在負(fù)權(quán)邊的情況)下，解決單源最短 路徑問題。對(duì)于給定的帶權(quán)有向圖G = (V, E)，其源點(diǎn)為s，加權(quán)函數(shù)為w： E 一 R，對(duì)該圖運(yùn)行Bellman-Ford算法后可以返回一個(gè)布爾值，表明圖中是否存在 著一個(gè)從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路。若存在這樣的回路，問題無解；否則，算法 產(chǎn)生最短路徑及其權(quán)值。Bellman-Ford算法運(yùn)用松弛技術(shù)，對(duì)每個(gè)頂點(diǎn)v，逐步減小從源s到v的 最短路徑的權(quán)的估計(jì)值dv直至其可達(dá)到實(shí)際最短路徑的權(quán)S(s, v)。算法返 回布爾值True，當(dāng)且僅當(dāng)圖中不包含從源點(diǎn)可達(dá)的負(fù)權(quán)回路。偽代碼：BELLMAN-FORD(G w

10、, s)INITIALIZE-SINGLE-SOURCE(G, s)for i，1 to |VG| -do for each edge (u, v) e EGdo RELAX(u, v, w)for each edge (u, v) e EGdo if dv du + w(u, v)then return FALSEreturn TRUE第1行初始化每個(gè)頂點(diǎn)的d和n值后，算法對(duì)圖中的邊進(jìn)行了 |V| - 1 遍操作。每一遍都是第24行for循環(huán)的一次迭代，有點(diǎn)類似于預(yù)處理。下邊 是的圖示是算法對(duì)邊進(jìn)行四遍操作，每一遍過后的狀態(tài)。在|V- 1|遍操作過后， 第58行對(duì)負(fù)權(quán)回路進(jìn)行檢查，并返回適當(dāng)

11、的布爾值。圖示：源點(diǎn)是頂點(diǎn)s。d值被標(biāo)記在頂點(diǎn)內(nèi)，陰影覆蓋的邊指示了前趨值：如果 邊（u, v）被陰影覆蓋，則nv = u。在這個(gè)特定例子中，每一趟按照如下的順 序?qū)呥M(jìn)行松弛：（t，x），（t，y），（t，z），（x，t），（y，x），（y，z），（z，x），（z， s），（s，t），（s，y）。a）示出了對(duì)邊進(jìn)行第一趟操作前的情況。b）e）示出了每一 趟連續(xù)對(duì)邊操作后的情況。e）中d和n值是最終結(jié)果。這個(gè)例子中，返回值 是 True。理解最短路算法，最基礎(chǔ)，最簡(jiǎn)單，最經(jīng)典的要數(shù)這個(gè)題目：HDU 2544最 短路，用Bellon-Ford算法實(shí)現(xiàn)：（必然有最短路，所以不必判斷布爾值）0 #i

12、nclude#include0 #include#include0 #includeusing namespacestd;0const int NV =101;struct Edge 0int u, v, w;graNV * NV;0 int disNV;void BellmanFord(int n, int m) 0 memset(dis, 0 x7f, sizeof(dis);dis1 = 0;0 for (int i = 1; i n; i+) for (int j = 0; j m; j+) 0 if (disgraj.u + graj.w disgraj.v) 1 disgraj.v

13、 = disgraj.u + graj.w; 01 if (disgraj.v + graj.w 1 disgraj.u) 1 disgraj.u = disgraj.v + graj.w;2131int main() 1 int n, m;while (scanf(%d %d, &n, &m), n I m)1for (int i = 0; i m; i+) 1 int u, v, w;scanf(%d %d %d”, &u, &v, &w);1 grai.u = u, grai.v = v, grai.w =8901234567890123456789w;BellmanFord(n, m)

14、;printf(%dn, disn);2 return 0;22222222333333333314243Bellman-Ford雖然很簡(jiǎn)單，但是復(fù)雜度太高，達(dá)到了 O(VE)，從上邊圖示中 可以看出：(a) t，x，y，z邊的松弛是無用操作；(b) s，x，z邊的松弛是無用操 作；(c) s，t，y邊的松弛是無用操作；(d) s，x，y，z邊的松弛是無用操作。也 就是說，只有更新過的點(diǎn)所做的松弛才是有效操作，所以出現(xiàn)了更高效的算法， 即 SPFA：四、Bellman-Ford 算法的優(yōu)化SPFA(Shortest PathFaster Algorithm)算法SPFA算法是西南交通大學(xué)段凡丁

15、于1994年發(fā)表的。它是Bellman-Ford的 隊(duì)列優(yōu)化，時(shí)效性相對(duì)好，時(shí)間復(fù)雜度O(kE)，也是單源最短路算法，同時(shí)可 以處理負(fù)權(quán)邊。從名字即可看出，此算法速度非同一般。與Bellman-ford算法類似，SPFA算法采用一系列的松弛操作以得到從某一 個(gè)節(jié)點(diǎn)出發(fā)到達(dá)圖中其它所有節(jié)點(diǎn)的最短路徑。所不同的是，SPFA算法通過維 護(hù)一個(gè)隊(duì)列，使得一個(gè)節(jié)點(diǎn)的當(dāng)前最短路徑被更新之后沒有必要立刻去更新其他 的節(jié)點(diǎn)，從而大大減少了重復(fù)的操作次數(shù)。偽代碼：SPFA(Gw,s)INITIALIZE-SINGLE-SOURCE(GjS)INITIALIZE-QUEUE(Q)ENQUEUE(Q,s)While

16、 Not EMPTY(Q)Do u-DLQUEUE(Q)For 每條邊(u,v) in EGDo tmp-dvRelax(u,v,w)If (dv tmp) and (v 不在 Q 中)ENQUEUE(Q,v)Bellon-Ford算法，每次都松弛所有的邊，所以造成效率低下，而SPFA的高 效之處在于，它每次只松弛更新過的點(diǎn)連接的邊，簡(jiǎn)單的過程敘述就是：初始Diss = 0，其他賦值為Inf；將起點(diǎn)s放入空隊(duì)列Q；step 1.從Q中選取元素u，并刪除該元素；step 2.對(duì)所有和u相連的點(diǎn)v進(jìn)行松弛，如果v被更新且v不在隊(duì) 列中，把v加進(jìn)隊(duì)列；5) 一直循環(huán)step 1和step 2,直到隊(duì)

17、列為空。結(jié)束;另外，還需要了解的是，SPFA的算法時(shí)間效率是不穩(wěn)定的，即它對(duì)于不同 的圖所需要的時(shí)間有很大的差別。在最好情形下，每一個(gè)節(jié)點(diǎn)都只入隊(duì)一次，則 算法實(shí)際上變?yōu)閺V度優(yōu)先遍歷，其時(shí)間復(fù)雜度僅為0(E)。另一方面，存在這樣 的例子，使得每一個(gè)節(jié)點(diǎn)都被入隊(duì)(V -1)次，此時(shí)算法退化為Bellman-ford算法， 其時(shí)間復(fù)雜度為O(VE)。SPFA在負(fù)邊權(quán)圖上可以完全取代Bellman-ford算法，另外在稀疏圖中也表 現(xiàn)良好。但是在非負(fù)邊權(quán)圖中，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn) 定的Dijkstra算法，以及它的使用堆優(yōu)化的版本。通常的SPFA算法在一類網(wǎng)格 圖中的表現(xiàn)不盡如

18、人意。還是上邊那道題，用SPFA算法實(shí)現(xiàn)：1)鄰接矩陣實(shí)現(xiàn)，便于理解算法過程：01#include02#include03#include04#include05#include06#include07using namespace std;08const int NV = 101;09const int inf = INT_MAX 1;10int m, n;11int mapNVNV;12int disNV;13bool markNV;14int Spfa (int src, int des) (15for (int i = 0; i = n; i+) (16marki = false;17

19、disi = inf;18)19queue Q;20marksrc = true;21dissrc = 0;22Q.push(src);23while (!Q.empty() (24int first = Q.front();25Q.pop();26markfirst = false;27for (int i = 1; i = n; i+) (28if (disfirst + mapfirsti disi) (29if (!marki) (30Q.push(i);31)32disi = disfirst + mapfirsti;33marki = true;34)/for/while37ret

20、urn disdes;38)39int main() (40while (scanf(%d%d, &n, &m), n | m) ( 41int a, b, c;42for (int i = 1; i = n; i+) (43mapii = inf;44for (int j = i + 1; j = n; j+) (45mapij = mapji = inf;46)47)48while (m-) (49scanf(%d%d%d, &a, &b, &c);50mapab = mapba = c;51)52printf(%dn, Spfa(1, n);53)54return 0;55)2)更通用的

21、鄰接表形式：01#include02#include03#include04#include05#include06#include07#include08#include09using namespace std;10const int NV = 101;11const int NE = 20001;12const int inf = INT_MAX 1;13struct SPFA (14int n, size;15int disNV, headNV;16bool inNV;17struct edge (18int v, w, next;19edge () ()20edge (int V,

22、int NEXT, int W = 0) : v(V), next(NEXT), w(W) () 21ENE;22void init(int nn) (23n = nn, size = 0;24for (int i = 0; i = n; i+) (25headi = -1;26ini = 0;27disi = inf;282930inline void insert(int u, int v, int w) (31Esize = edge(v, headu, w);32headu = size+;3334inline bool relax(int u, int v, int w) (35if

23、 (disv = inf| disu + w disv) (36disv = disu +w;37return true;3839return false;4041int spfa(int src,int des) (42queue que;43dissrc = 0;44que.push(src);45insrc = true;46while (!que.empty() (47int u = que.front();48que.pop();49inu = false;50for (int i = headu; i != -1; i = Ei.next) (51int v = Ei.v;52if

24、 (relax(u, v, Ei.w) & !inv ) (53inv = true;54que.push(v);55/if56/for57/while58return disdes;59)/SFPA60G;61int main() (62int n, m;63while (scanf(%d%d, &n, &m), n | m) ( 64G.init(n);65int a, b, c;66for (int i = 0; i m; i+) (67scanf(%d%d%d, &a, &b, &c);68G.insert(a, b, c);69G.insert(b, a, c);70)71printf(%dn, G.spfa(1, n);72)73return 0;74)7576777五、理論分析與算法比較圖論中求最短路一般有四種比較常見的算法：Floyd、Dijkstra、Bell