算法合集之《最短路算法及其應(yīng)用》

《算法合集之《最短路算法及其應(yīng)用》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、2006年全國(guó)信息學(xué)冬令營(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)鍵字】最短路【目錄】一、基本概念21．1定義21．2簡(jiǎn)單變體21．3負(fù)權(quán)邊31．4重要性質(zhì)及松弛技術(shù)4二、常用算法52．1Dijkstra算法52．2Bellman-For

2、d算法72．3SPFA算法8三、應(yīng)用舉例103．1例題1——貨幣兌換103．2例題2——雙調(diào)路徑113．3例題3——Layout133．4例題4——網(wǎng)絡(luò)提速15第23頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座四、總結(jié)18【正文】一、基本概念1．1定義乘汽車旅行的人總希望找出到目的地盡可能短的行程。如果有一張地圖并在地圖上標(biāo)出了每對(duì)十字路口之間的距離，如何找出這一最短行程？一種可能的方法是枚舉出所有路徑，并計(jì)算出每條路徑的長(zhǎng)度，然后選擇最短的一條。然而我們很容易看到，即使不考慮含回路的路徑，依然存在數(shù)以百萬(wàn)計(jì)的行車路線，而其中絕大多數(shù)是沒(méi)必要考慮的。下面我

3、們將闡明如何有效地解決這類問(wèn)題。在最短路問(wèn)題中，給出的是一有向加權(quán)圖G=(V,E)，在其上定義的加權(quán)函數(shù)W:ER為從邊到實(shí)型權(quán)值的映射。路徑P=(v0,v1,……,vk)的權(quán)是指其組成邊的所有權(quán)值之和：定義u到v間最短路徑的權(quán)為從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑定義為權(quán)的任何路徑。在乘車旅行的例子中，我們可以把公路地圖模型化為一個(gè)圖：結(jié)點(diǎn)表示路口，邊表示連接兩個(gè)路口的公路，邊權(quán)表示公路的長(zhǎng)度。我們的目標(biāo)是從起點(diǎn)出發(fā)找一條到達(dá)目的地的最短路徑。邊的權(quán)常被解釋為一種度量方法，而不僅僅是距離。它們常常被用來(lái)表示時(shí)間、金錢、罰款、損失或任何其他沿路徑線性積累的

4、數(shù)量形式。1．2簡(jiǎn)單變體單目標(biāo)最短路徑問(wèn)題：找出從每一結(jié)點(diǎn)v到某指定結(jié)點(diǎn)u的一條最短路徑。把圖中的每條邊反向，我們就可以把這一問(wèn)題轉(zhuǎn)化為單源最短路徑問(wèn)題。單對(duì)結(jié)點(diǎn)間的最短路徑問(wèn)題：對(duì)于某給定結(jié)點(diǎn)u和v，找出從u到v的一條最短路徑。如果我們解決了源結(jié)點(diǎn)為u的單源問(wèn)題，則這一問(wèn)題也就獲得了解決。對(duì)于該問(wèn)題的最壞情況，從漸進(jìn)意義上看，目前還未發(fā)現(xiàn)比最好的單源算法更快的方法。每對(duì)結(jié)點(diǎn)間的最短路徑問(wèn)題：對(duì)于每對(duì)結(jié)點(diǎn)u和v，找出從u到v第23頁(yè)2006年全國(guó)信息學(xué)冬令營(yíng)講座的最短路徑。我們可以用單源算法對(duì)每個(gè)結(jié)點(diǎn)作為源點(diǎn)運(yùn)行一次就可以解決問(wèn)題。1．3負(fù)權(quán)邊

5、在某些單源最短路問(wèn)題中，可能存在權(quán)為負(fù)的邊。如果圖G(V,E)不包含由源s可達(dá)的負(fù)權(quán)回路，則對(duì)所有，最短路徑的權(quán)的定義依然正確。即使它是一個(gè)負(fù)值也是如此。但如果存在一從s可達(dá)的負(fù)權(quán)回路，最短路徑的定義就不能成立了。從s到該回路上的結(jié)點(diǎn)不存在最短路徑——因?yàn)槲覀兛偪梢皂樦页龅摹白疃獭甭窂皆俅┻^(guò)負(fù)權(quán)回路從而獲得一權(quán)值更小的路徑，因此如果從s到v的某路徑中存在一負(fù)權(quán)回路，我們定義。圖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只存在一條路徑(路徑)，所以：。類

6、似地，從s到b也只有一條通路，所以：。從s到c則存在無(wú)數(shù)條路徑：,,等等。因?yàn)榛芈?c,d,c>的權(quán)為6+(-3)=3>0，所以從s到c的最短路徑為，其權(quán)為：。類似地，從s到d的最短路徑為，其權(quán)為：。同樣，從s到e存在無(wú)數(shù)條路徑：,,等等.由于回路的權(quán)為3+(-6)=-3<0，所以從s到e沒(méi)有最短路徑。只要穿越負(fù)權(quán)回路任意次，我們就可以發(fā)現(xiàn)從s到e的路徑可以有任意小的負(fù)權(quán)值，所以：類似地，第23頁(yè)

7、2006年全國(guó)信息學(xué)冬令營(yíng)講座因?yàn)間是從f可達(dá)的結(jié)點(diǎn)，我們從s到g的路徑可以有任意小的負(fù)權(quán)值，則：。結(jié)點(diǎn)h，j，i也形成一權(quán)值為負(fù)的回路，但因?yàn)樗鼈儚膕不可達(dá)，因此。一些最短路徑的算法，例如Dijkstra算法，都假定輸入圖中所有邊的權(quán)取非負(fù)數(shù)，如公路地圖實(shí)例。另外一些最短路算法，如Bellman-Ford算法，允許輸入圖中存在權(quán)為負(fù)的邊，只要不存在從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路，這些算法都能給出正確的解答。特定地說(shuō)，如果存在這樣一個(gè)權(quán)為負(fù)的回路，這些算法可以檢測(cè)出這種回路的存在。1．4重要性質(zhì)及松弛技術(shù)本文的算法所運(yùn)用的主要技術(shù)是松弛技術(shù)，它反復(fù)減

8、小每個(gè)結(jié)點(diǎn)的實(shí)際最短路徑的權(quán)的上限，直到該上限等于最短路徑的權(quán)。讓我們看看如何運(yùn)用松弛技術(shù)并正式證明它的一些特性。定理1(最優(yōu)子結(jié)構(gòu))給定有向加權(quán)圖G