最短路算法[1]

1、2006年全國信息學(xué)冬令營講座第1頁最短路算法及其應(yīng)用最短路算法及其應(yīng)用廣東北江中學(xué)余遠銘【摘要】最短路問題是圖論中的核心問題之一，它是許多更深層算法的基礎(chǔ)。同時，該問題有著大量的生產(chǎn)實際的背景。不少問題從表面上看與最短路問題沒有什么關(guān)系，卻也可以歸結(jié)為最短路問題。本文較詳盡地介紹了相關(guān)的基本概念、常用算法及其適用范圍，并對其應(yīng)用做出了舉例說明，側(cè)重于模型的建立、思考和證明的過程，最后作出總結(jié)?！娟P(guān)鍵字】最短路【目錄】一、基本概念...

2、.................................................................................211定義.................................................................................................................................212簡單

3、變體..........................................................................................................................213負權(quán)邊..........................................................................................

4、....................................314重要性質(zhì)及松弛技術(shù)......................................................................................................4二、常用算法...............................................................

5、.....................521Dijkstra算法.................................................................................................................522BellmanFd算法...........................................................

6、.............................................723SPFA算法.....................................................................................................................8三、應(yīng)用舉例..........................................

7、........................................1031例題1——貨幣兌換....................................................................................................1032例題2——雙調(diào)路徑......................................................

8、..............................................1133例題3——Layout.........................................................................................................1334例題4——網(wǎng)絡(luò)提速.........................................

9、...........................................................152006年全國信息學(xué)冬令營講座第3頁路徑。我們可以用單源算法對每個結(jié)點作為源點運行一次就可以解決問題。13負權(quán)邊負權(quán)邊在某些單源最短路問題中，可能存在權(quán)為負的邊。如果圖G(VE)不包含由源s可達的負權(quán)回路，則對所有，最短路徑的權(quán)的定義依然正確。svV?()sv?即使它是一個負值也是如此。但如果存在一從s可達的負權(quán)回路

10、，最短路徑的定義就不能成立了。從s到該回路上的結(jié)點不存在最短路徑——因為我們總可以順著找出的“最短”路徑再穿過負權(quán)回路從而獲得一權(quán)值更小的路徑，因此如果從s到v的某路徑中存在一負權(quán)回路，我們定義。()sv????圖1含有負權(quán)和負權(quán)回路的圖圖1說明負的權(quán)值對最短路徑的權(quán)的影響。每個結(jié)點內(nèi)的數(shù)字是從源點s到該結(jié)點的最短路徑的權(quán)。因為從s到a只存在一條路徑(路徑)，所以：。()()3sawsa???類似地，從s到b也只有一條通路，所以：。()