最短路模型的構(gòu)建與求解方法方案曹利國(guó)教案

1、最短路模型的構(gòu)建與求解方法教案長(zhǎng)沙市一中 曹利國(guó)課題：最短路模型的構(gòu)建與求解方法重點(diǎn)：最短路問(wèn)題的求解方法難點(diǎn)：最短路問(wèn)題的模型構(gòu)建方法過(guò)程：一、最短路問(wèn)題的原型（1）單源最短路問(wèn)題問(wèn)題描述：用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問(wèn)題： 從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑最短路徑 求解方法：Dijstra算法。算法思想：用n表示圖中節(jié)點(diǎn)的個(gè)數(shù)，用g : 1.n,1.nof integer儲(chǔ)存?zhèn)€個(gè)頂點(diǎn)之間的距離，用vis : array1.nof boolean 儲(chǔ)存

2、個(gè)點(diǎn)的訪問(wèn)情況。用disk : array1.nof integer儲(chǔ)存起點(diǎn)到其他各點(diǎn)的最短距離，初始化：disk1.n= +，diskfrom=0，vis1.n=false。Repeat 找到一個(gè)未訪問(wèn)（visi=false）且在所有未訪問(wèn)的節(jié)點(diǎn)中最短距離最?。╠iskidiskk kvisk=false）的節(jié)點(diǎn)I; 用找到的節(jié)點(diǎn)I更新其他節(jié)點(diǎn)的最短距離（if diski+gI,jdiskj then diskj=diski+gI,j）Until 所有節(jié)點(diǎn)都擴(kuò)張過(guò)了。（2）任意頂點(diǎn)對(duì)之間的最短路問(wèn)題 求解方法：Floyed算法。方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次-

3、T(n)=O(n)方法二：弗洛伊德(Floyd)算法，其算法思想：逐個(gè)頂點(diǎn)試探法。具體步驟：v 初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線元素為0，若存在弧，則對(duì)應(yīng)元素為權(quán)值；否則為v 逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值v所有頂點(diǎn)試探完畢，算法結(jié)束二、模型構(gòu)建方法與問(wèn)題分析問(wèn)題A：過(guò)河問(wèn)題。一個(gè)人帶了一只狼、一只兔子和一棵白菜想要過(guò)河。河上有一只獨(dú)木船，每次除了人以外，只能帶一樣?xùn)|西。另外如果人不在旁時(shí)狼就要吃兔子，兔子就要吃白菜。問(wèn)應(yīng)該怎樣安排過(guò)河，才能做到既把所有東西都帶過(guò)河，在河上來(lái)回的次數(shù)又最少？.分析：（一）構(gòu)圖（1） 圖的節(jié)點(diǎn)對(duì)于左岸的情況

4、，我們可以用集合表示。這樣一共會(huì)有24=16種狀態(tài)：人、狼、兔、菜 人、狼、兔人、狼、菜 人、兔、菜狼、兔、菜 人、狼 人、兔 人、菜 狼、兔 狼、菜 兔、菜 人 狼兔 菜 這其中有狼吃兔子、兔子吃菜的情況的有：狼、兔、菜，人、狼，人、菜，狼、兔，兔、菜，人 共6種情況。將他們刪掉后就剩下10個(gè)集合了。將這10個(gè)集合看成我們的圖中的10個(gè)節(jié)點(diǎn)。（2） 圖的邊與權(quán)這10個(gè)節(jié)點(diǎn)，若是一個(gè)節(jié)點(diǎn)的情況可以通過(guò)一次渡河得到另一個(gè)節(jié)點(diǎn)的情況，就在這兩個(gè)節(jié)點(diǎn)之間連一條權(quán)值為1的無(wú)向邊。構(gòu)建后的圖論模型如下：（二）問(wèn)題轉(zhuǎn)化：構(gòu)建好圖論模型后，問(wèn)題轉(zhuǎn)化成了求 人、狼、兔、菜 到 的最短路徑了。問(wèn)題B：最優(yōu)乘車（

5、NOI97試題）問(wèn)題描述： H城是一個(gè)旅游勝地，每年都有成千上萬(wàn)的人前來(lái)觀光。為方便游客，巴士公司在各個(gè)旅游景點(diǎn)及賓館，飯店等地都設(shè)置了巴士站并開(kāi)通了一些單程巴士線路。每條單程巴士線路從某個(gè)巴士站出發(fā)，依次途經(jīng)若干個(gè)巴士站，最終到達(dá)終點(diǎn)巴士站。 一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒(méi)有一路巴士可以直接到達(dá)S公園，則他可能要先乘某一路巴士坐幾站，再下來(lái)?yè)Q乘同一站臺(tái)的另一路巴士, 這樣換乘幾次后到達(dá)S公園。 現(xiàn)在用整數(shù)1，2， N 給H城的所有的巴士站編號(hào)，約定這名旅客所在飯店的巴士站編號(hào)為1，2， S，公園巴士站的編號(hào)為N。 寫(xiě)一個(gè)程序，幫助這名旅客尋找一個(gè)最優(yōu)乘車方

6、案,使他在從飯店乘車到S公園的過(guò)程中換車的次數(shù)最少。輸入輸出 輸入文件是INPUT.TXT。文件的第一行有兩個(gè)數(shù)字M和N(1=M=100 1N 7 3 6這條線路。由于巴士在同一線路上行走不需換車，我們可設(shè)4 7，4 3，4 6，7 3，7 6，3 6這些邊的權(quán)值都為1。對(duì)每條線路我們都這樣構(gòu)圖，然后問(wèn)題就轉(zhuǎn)化成求起點(diǎn)1到終點(diǎn)n的最短路。圖2：67473621356747362135把圖2中的編號(hào)一樣的點(diǎn)合并，再求從1到n的最短路即可。（二）問(wèn)題轉(zhuǎn)化：假設(shè)最短路長(zhǎng)為m 。由于坐車耗費(fèi)在每條線路上的代價(jià)都是1，而不同線路間是通過(guò)同一站聯(lián)系的，所以換線路并不耗時(shí)，因此m即表示從起點(diǎn)1到終點(diǎn)n所經(jīng)過(guò)

7、的最少線路數(shù)。而最少換車次數(shù)即等于經(jīng)過(guò)的最少線路數(shù)減一。問(wèn)題C：求解01串問(wèn)題（NOI99試題）問(wèn)題描述：給定7個(gè)整數(shù)N,A0,B0,L0,A1,B1,L1，要求設(shè)計(jì)一個(gè)01串S=s1s2sisN，滿足：（1）si=0或si=1，1=i=N；（2）對(duì)于S的任何連續(xù)的長(zhǎng)度為L(zhǎng)0的子串sjsj+1sj+L0-1(1=j=N-L0+1)，0的個(gè)數(shù)大于等于A0且小于等于B0;（3）對(duì)于S的任何連續(xù)的長(zhǎng)度為L(zhǎng)1的子串sjsj+1sj+L1-1(1=j=N-L1+1)，1的個(gè)數(shù)大于等于A1且小于等于B1;例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，則存在一個(gè)滿足上述所有條件的

8、01串S=010101。輸入僅一行，有7個(gè)整數(shù)，依次表示N,A0,B0,L0,A1,B1,L1（3=N=1000，1= A0=B0=L0=N，1=A1=B1=L1=N），相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。輸出僅一行，若不存在滿足所有條件的01串，則輸出一個(gè)整數(shù)-1，否則輸出一個(gè)滿足所有條件的01串。樣例輸入6 1 2 3 1 1 2樣例輸出010101.分析這是一道非常特別的最短路問(wèn)題，它的點(diǎn)與邊的建立借用了數(shù)學(xué)概念。（一）構(gòu)圖既然是一道最短路問(wèn)題，就一定要用到圖論模型。問(wèn)題是如何構(gòu)建本題的圖論模型：（1） 圖的節(jié)點(diǎn)用Ci表示s1,s2.si中1的個(gè)數(shù)，我們可以得到C1,C2.Cn，用他們作圖的

9、節(jié)點(diǎn)，將C0也考慮進(jìn)去（顯然：C0=0），我們就得到了N+1個(gè)節(jié)點(diǎn)。（2）圖的邊與權(quán)。若我們已找到一個(gè)串S，則這個(gè)串S必須滿足如下性質(zhì)：對(duì)任意的i，C i一定符合下面的不等式：于是，根據(jù)這些不等式，我們得到了點(diǎn)與點(diǎn)之間的關(guān)系。按照這些不等式中大于等于符號(hào)的方向連接有向邊，用加號(hào)后面的值作為邊的權(quán)值，我們的構(gòu)圖就完成了。例如，樣例數(shù)據(jù)可以得到下面的圖：C0 C1 C2 C3 C6 C5C4 1 0 0 1 1 1 1 1 1 1 1 1 1 -1 0 0 0 0 2 2 2 2 -1 -1 -1 -1 -1 -1 -1 -1 C數(shù)組0123456值0112233得到的S序列：101010(二)模

10、型求解（1） 判斷是否有解考慮下面這樣一種情況：若x+y+z 0 則 Ci Ci這顯然是不可能得到的，所以若是出現(xiàn)了這種情況，則說(shuō)明無(wú)解。這種情況就是構(gòu)建的圖中出現(xiàn)負(fù)權(quán)回路的情況?。?）求出S序列要求出S序列，我們只要求出C數(shù)組就可以了。因?yàn)镃數(shù)組和S序列是一一對(duì)應(yīng)的關(guān)系。而C數(shù)組的值，又可以通過(guò)構(gòu)建的圖論模型來(lái)求。圖中C0節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)的最短距離，就是各個(gè)節(jié)點(diǎn)的值。（3）算法思想從前兩步得知，我們需要完成兩件工作：第一件就是判斷圖中是否有負(fù)權(quán)回路；第二件就是求C0到各個(gè)節(jié)點(diǎn)的最短距離。要解決這兩件事情，我們可以選擇Bellman-Ford算法。Bellman_Ford 算法思想用d i 表示

11、源點(diǎn)到其他點(diǎn)的最短距離值，用cost i , j 表示邊（i，j）的權(quán)值。 Repeat 標(biāo)志變量置true 枚舉所有的邊（i，j） 如果d i + cost i , j d j ， 則更新d j 值 = d i + cost i , j 標(biāo)志變量置false Until 無(wú)法再更新到所有點(diǎn)的最短距離（即標(biāo)志變量等于true）（4）算法改進(jìn)分析Bellman-Ford算法的本質(zhì)，我們可以在它的基礎(chǔ)上得到一個(gè)更簡(jiǎn)單的迭代算法：1）每一輪更新依次訪問(wèn)C0到Cn。每次訪問(wèn)到節(jié)點(diǎn)Ci，根據(jù)前面推出的6個(gè)不等式，更新另外6個(gè)節(jié)點(diǎn)的值。2）重復(fù)1步驟，直到無(wú)法更新或更新的輪數(shù)大于2n為止。顯然，若更新的輪數(shù)大于2n，則說(shuō)明有負(fù)權(quán)回路，問(wèn)題無(wú)解；若更新的輪數(shù)小于等于2n，則說(shuō)明沒(méi)有負(fù)權(quán)回路，于是根據(jù)C數(shù)組構(gòu)造出S序列輸出。三、總結(jié)最短路是圖論的經(jīng)典