網(wǎng)上找的一些圖論bellman

1、Bellman-Ford 算法及其優(yōu)Bellman-Ford 算法與另一個非常著名的 Dijkstra 算法一樣，用于求解單源點最短路徑問題。Bellman-ford 算法除了可求解邊權(quán)均非以解決存在負(fù)權(quán)（意義是什么，好好思考），而 Dijkstra 算法只能處理負(fù)，因此 Bellman-Ford 算法的適用面要廣泛一些。是，原始的 Bellman-Ford 算法時間復(fù)雜度為 O（VE）,比 Dijkstra 法導(dǎo)論也只介紹了基本Bellman-Ford 算法及其優(yōu)Bellman-Ford 算法與另一個非常著名的 Dijkstra 算法一樣，用于求解單源點最短路徑問題。Bellman-ford

2、 算法除了可求解邊權(quán)均非以解決存在負(fù)權(quán)（意義是什么，好好思考），而 Dijkstra 算法只能處理負(fù)，因此 Bellman-Ford 算法的適用面要廣泛一些。是，原始的 Bellman-Ford 算法時間復(fù)雜度為 O（VE）,比 Dijkstra 法導(dǎo)論也只介紹了基本的 Bellman-Ford 算法，在國內(nèi)常見的基本信息學(xué)奧中也均未提及，因此該算法的知名度與被掌握度都不如 算法。事實上，有多種形式的 Bellman-Ford 算法，例如近一兩年被熱捧的 SPFA（Shortest-Faster Algoithm 更快的最短路徑算法）算法的時間效率甚至由于 Dijkstra 算法，因此有關(guān) B

3、ellman-Ford 算法的諸多問題常常困擾奧賽選手。如：該算法值得掌握么？怎樣用編程語言具體實現(xiàn)？有哪些優(yōu)化？與 SPFA 本文試圖對 Bellman-算法做一個比較全面的介紹。給出幾種實現(xiàn)程序，從理論和實測兩方面分析他們的時間復(fù)雜度，供大家在備戰(zhàn)省選和后noi 時參考Bellman-Ford 算法Bellman-Ford 算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點最短路徑問題。對于給定的帶權(quán)（有向或無向）G=（V,E），其源點為 s權(quán)函數(shù)w集E 。對圖 G 運行 Bellman-Ford 算法的結(jié)果是一個布爾值，表明圖中是否存在著一個從源點 s 可達(dá)的負(fù)權(quán)回路。若不存這樣的回路，算法

4、將給出從源點s G 的任意頂點v 的最短路徑dvBellman-Ford 算法流程分為三個階段：初始化：將除源點外的所有頂點的最短距離估計值dv ds 迭代求解：反復(fù)對邊集 E 中的每條邊進(jìn)行松弛操作，使得頂點集 V 中的每個頂點 v 的最短距離估計值逐步 近其最短距離；（運行|v|-次檢驗負(fù)權(quán)回路：判斷邊集 E 中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回 false回 true，并且從源點可達(dá)的頂點 v 的最短距離保存在 dv算法描述如下Bellman-Ford(G,w,s) /G ，邊集數(shù)w ，s 為源1foreachvertexv V（G）dv 2ds /134fo

5、ri=1to|v|-1/2 for each edge（u,v） E(G) do /邊集數(shù)組要用到，窮舉每條邊5If4fori=1to|v|-1/2 for each edge（u,v） E(G) do /邊集數(shù)組要用到，窮舉每條邊5Ifdvdu+w(u,v)/67/松弛操作 2階段結(jié)foreachedge（u,v）E(G)8 9ExitExit首，圖的任意一條最短路徑既不能包含負(fù)權(quán)回路，也不會包含正權(quán)回路，因此它最多包含|v|-條邊s 可達(dá)的所有頂點如果 一個以 s 為根的最短路徑樹。Bellman-Ford 算法的迭代松弛操作，際上就是按頂點距離 s 在對每條邊進(jìn)行 1 遍松弛的時候，生成

6、了從 s 出發(fā)，層次至多為 1 的那些樹枝。也就是說，找到了與 s 至多有 1 對每條邊進(jìn)行第 2 2 層次的樹枝，就是說找到了經(jīng)過 2 條邊相連的那些頂點的最短路徑|v|-條邊，所以，只需要循環(huán)|v|-1 次（但是，每次還要判斷松弛，這里浪費了大量的時間，怎么優(yōu)化？單純的優(yōu)化是否可行如果沒有負(fù)權(quán)回路由于最短路徑樹的高度最多只能是|v|-1，所以最多經(jīng)過|v|-1 遍松弛操作后所有從 s 可達(dá)的頂點必將求出最短距離。如仍保持 +sv如果有負(fù)權(quán)回路，那么第 |v|-1 遍松弛操作仍然會成功，這時，負(fù)權(quán)的頂點不會收斂例如對于上圖，邊上方框中的數(shù)字代表權(quán)值，頂點 A,B,C 之間存在負(fù)權(quán)回路。S 是

7、源點，頂點中數(shù)字表示運行 Bellman-Ford 算法后各點的最此時 da的值為 1，大于 dc+w(c,a)的值-2，由此 da可以松弛為-2，然后 db又可以松弛為-5,dc又可以松弛為-7.下一個周期，da不會終止。因此，在迭代求解最短路徑階段結(jié)束后，可以通過檢驗邊集 E 此時 da的值為 1，大于 dc+w(c,a)的值-2，由此 da可以松弛為-2，然后 db又可以松弛為-5,dc又可以松弛為-7.下一個周期，da不會終止。因此，在迭代求解最短路徑階段結(jié)束后，可以通過檢驗邊集 E 的每條邊(u,v)是否滿足關(guān)系可以更新為更小的值，這個過du+ w(u,v) 來判斷是否存在負(fù)權(quán)回路】61112223445125634645664-56-programw:array1.maxn,1.maxnofpre:array1.maxnvis:array1.maxn;procedureforu:=1to nforv:=1tonfori:=1to mw:array1.maxn,1.maxnofpre:array1.maxnvis:array1.maxn;procedureforu:=1to nforv:=1tonfori:=1to mprocedure;fori:=1tonfori:=1ton forj: