亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

算法

在這個(gè)圖中，假設(shè)A是起點(diǎn)，并且邊以最壞的順序處理，從右到左，需要|V|?1步或4次計(jì)算路徑長度。相反地，若邊以最優(yōu)順序處理，從左到右，算法只需要在一次遍歷內(nèi)完成。

貝爾曼-福特算法與迪科斯徹算法類似，都以松弛操作為基礎(chǔ)，即估計(jì)的最短路徑值漸漸地被更加準(zhǔn)確的值替代，直至得到最優(yōu)解。在兩個(gè)算法中，計(jì)算時(shí)每個(gè)邊之間的估計(jì)距離值都比真實(shí)值大，并且被新找到路徑的最小長度替代。 然而，迪科斯徹算法以貪心法選取未被處理的具有最小權(quán)值的節(jié)點(diǎn)，然后對其的出邊進(jìn)行松弛操作；而貝爾曼-福特算法簡單地對所有邊進(jìn)行松弛操作，共| V | ? 1次，其中 | V |是圖的點(diǎn)的數(shù)量。在重復(fù)地計(jì)算中，已計(jì)算得到正確的距離的邊的數(shù)量不斷增加，直到所有邊都計(jì)算得到了正確的路徑。這樣的策略使得貝爾曼-福特算法比迪科斯徹算法適用于更多種類的輸入。

貝爾曼-福特算法的最多運(yùn)行O（| V |·| E |)次，| V |和| E |分別是節(jié)點(diǎn)和邊的數(shù)量）。

偽代碼表示

原理

松弛

每次松弛操作實(shí)際上是對相鄰節(jié)點(diǎn)的訪問，第 n {\displaystyle n} 次松弛操作保證了所有深度為n的路徑最短。由于圖的最短路徑最長不會(huì)經(jīng)過超過 V ? ? --> 1 {\displaystyle V-1} 條邊，所以可知貝爾曼-福特算法所得為最短路徑。

負(fù)邊權(quán)操作

與迪科斯徹算法不同的是，迪科斯徹算法的基本操作“拓展”是在深度上尋路，而“松弛”操作則是在廣度上尋路，這就確定了貝爾曼-福特算法可以對負(fù)邊進(jìn)行操作而不會(huì)影響結(jié)果。

負(fù)權(quán)環(huán)判定

因?yàn)樨?fù)權(quán)環(huán)可以無限制的降低總花費(fèi)，所以如果發(fā)現(xiàn)第 n {\displaystyle n} 次操作仍可降低花銷，就一定存在負(fù)權(quán)環(huán)。

優(yōu)化

循環(huán)的提前跳出

在實(shí)際操作中，貝爾曼-福特算法經(jīng)常會(huì)在未達(dá)到V-1次前就出解，V-1其實(shí)是最大值。于是可以在循環(huán)中設(shè)置判定，在某次循環(huán)不再進(jìn)行松弛時(shí)，直接退出循環(huán)，進(jìn)行負(fù)權(quán)環(huán)判定。

隊(duì)列優(yōu)化

求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm。 SPFA算法是西南交通大學(xué)段凡丁于1994年發(fā)表的。 松弛操作必定只會(huì)發(fā)生在最短路徑前導(dǎo)節(jié)點(diǎn)松弛成功過的節(jié)點(diǎn)上，用一個(gè)隊(duì)列記錄松弛過的節(jié)點(diǎn)，可以避免了冗余計(jì)算。復(fù)雜度可以降低到O(kE)，k是個(gè)比較小的系數(shù)(并且在絕大多數(shù)的圖中，k<=2，然而在一些精心構(gòu)造的圖中可能會(huì)上升到很高)

Begininitialize-single-source(G,s);initialize-queue(Q);enqueue(Q,s);whilenotempty(Q)dobeginu:=dequeue(Q);foreachv∈adj[u]dobegintmp:=d[v];relax(u,v);if(tmpd[v])and(notvinQ)thenenqueue(Q,v);end;end;End;

樣例

例：V={v1,v2,v3,v4} E={(v1,v2),(v1,v3),(v2,v4),(v4,v3)} weight(v1,v2)=-1 weight(v1,v3)=3 weight(v2,v4)=3 weight(v4,v3)=-1

運(yùn)行如表： D:Dist[v]，P:Pred[v]

參考文獻(xiàn)

^

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。