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

2、.................................................................................211定義.................................................................................................................................212簡(jiǎn)單

3、變體..........................................................................................................................213負(fù)權(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年全國(guó)信息學(xué)冬令營(yíng)講座第3頁(yè)路徑。我們可以用單源算法對(duì)每個(gè)結(jié)點(diǎn)作為源點(diǎn)運(yùn)行一次就可以解決問(wèn)題。13負(fù)權(quán)邊負(fù)權(quán)邊在某些單源最短路問(wèn)題中，可能存在權(quán)為負(fù)的邊。如果圖G(VE)不包含由源s可達(dá)的負(fù)權(quán)回路，則對(duì)所有，最短路徑的權(quán)的定義依然正確。svV?()sv?即使它是一個(gè)負(fù)值也是如此。但如果存在一從s可達(dá)的負(fù)權(quán)回路

10、，最短路徑的定義就不能成立了。從s到該回路上的結(jié)點(diǎn)不存在最短路徑——因?yàn)槲覀兛偪梢皂樦页龅摹白疃獭甭窂皆俅┻^(guò)負(fù)權(quán)回路從而獲得一權(quán)值更小的路徑，因此如果從s到v的某路徑中存在一負(fù)權(quán)回路，我們定義。()sv????圖1含有負(fù)權(quán)和負(fù)權(quán)回路的圖圖1說(shuō)明負(fù)的權(quán)值對(duì)最短路徑的權(quán)的影響。每個(gè)結(jié)點(diǎn)內(nèi)的數(shù)字是從源點(diǎn)s到該結(jié)點(diǎn)的最短路徑的權(quán)。因?yàn)閺膕到a只存在一條路徑(路徑)，所以：。()()3sawsa???類似地，從s到b也只有一條通路，所以：。()