【正文】 ， … ， vn對(duì)應(yīng)數(shù) b(n)，那么，這些數(shù) b(i)就稱為 vi的標(biāo)號(hào)，當(dāng)然，在不同的問(wèn)題中，標(biāo)號(hào) b(i)一般代表不同的意義 . 回到我們要解決的最短有向路問(wèn)題上來(lái) .為確定起見(jiàn)，我們?cè)O(shè) vs=v1， vt=vn,也就是說(shuō)我們要找的是從v1到 vn的最短有向路 .下面介紹的方法可以把從 v1到 G的每一個(gè)頂點(diǎn) vj的最短有向路都求出來(lái) (或者指出不存在從 v1到 vj的有向路，即 v1不可達(dá) vj)． 我們把整個(gè)計(jì)算分成若干“輪”來(lái)進(jìn)行 (一個(gè)“輪”就是一個(gè)大步 )，每一輪中，將求出 v1到某一個(gè)頂點(diǎn) vj的最短路以及這條最短路的長(zhǎng)度 b(j).我們把 b(j)就叫做頂點(diǎn) vj的標(biāo)號(hào) .再?gòu)?qiáng)調(diào)一下， 頂點(diǎn) vj的標(biāo)號(hào)代表的是從 v1到 vj的最短路的長(zhǎng)度 .另外，如果說(shuō)“頂點(diǎn) vj已經(jīng)有標(biāo)號(hào)了”或“ vj是已標(biāo)號(hào)點(diǎn)”，就意味著從 v1到 vj的最短路以及這條最短路的長(zhǎng)度都已經(jīng)求出來(lái)了 . 計(jì)算開(kāi)始時(shí)，令 b(1)=0， v1變?yōu)橐褬?biāo)號(hào)點(diǎn)，其余頂點(diǎn)都是未標(biāo)號(hào)點(diǎn) .這樣做的意義很清楚，因?yàn)?b(1)代表從 v1到 v1的最短路的長(zhǎng)度，當(dāng)然不用計(jì)算就可以知道，它應(yīng)該等于 0. 如果計(jì)算是在一張圖上進(jìn)行，那么我們可以在頂點(diǎn) v1旁邊寫(xiě)一個(gè)數(shù) 0，表示這是 v1的標(biāo)號(hào)并且已算出 . 每一輪計(jì)算可以分成下面幾個(gè)步驟 . 步驟 1 找出所具有下述性質(zhì)的弧 i,j：起點(diǎn) vi是已標(biāo)號(hào)點(diǎn)而終點(diǎn) vj是未標(biāo)號(hào)點(diǎn) .如果這樣的弧不存在，計(jì)算結(jié)束 . 步驟 2 對(duì)于步驟 1中找到的每一條弧 i,j，計(jì)算一個(gè)數(shù)： ki,j=b(i)+li,j. (如果這個(gè) ki,j在前面各輪計(jì)算中已經(jīng)算過(guò)，就不必再算 )也就是說(shuō)： ki,j等于弧的起點(diǎn)的 標(biāo)號(hào)加上弧的長(zhǎng)度 .把算出的 ki,j的值就寫(xiě)在弧 i,j的旁邊，并在數(shù)的外面加上一個(gè)方括號(hào)．然后找出使ki,j最小的弧 c,d(如果有好幾條弧都使 ki,j達(dá)到最小，可任取一條 ) 步驟 3 把弧 c,d畫(huà)成粗線，把頂點(diǎn) vd變?yōu)橐褬?biāo)號(hào)點(diǎn)，令 vd的標(biāo)號(hào) b(d)就等于 kc,d.這一輪計(jì)算結(jié)束 . 在一輪計(jì)算結(jié)束后，應(yīng)該檢查一下，是不是所有頂點(diǎn)都得到標(biāo)號(hào)了，如果是的，那么整個(gè)計(jì)算就結(jié)束了；如果不是，即還有未標(biāo)號(hào)的頂點(diǎn)，就轉(zhuǎn)向下一輪計(jì)算 (即再?gòu)牟襟E 1開(kāi)始計(jì)算 ). 如果我們要求從 vs到 vt的最短路，只要 vt得到標(biāo)號(hào)，計(jì)算就結(jié)束了，從而可以省去一些計(jì)算 . 如果在計(jì)算結(jié)束時(shí)，還有一些點(diǎn)沒(méi)有得到標(biāo)號(hào)，那么可以肯定，從起點(diǎn)到這些點(diǎn)的有向路是不存在的 . 該計(jì)算方法的框式圖如下： 開(kāi)始：令 b(1)=0， v1為已標(biāo)號(hào)點(diǎn) 求所有起點(diǎn)已標(biāo)號(hào)、終點(diǎn)未標(biāo)號(hào) 的弧的集合 B， B是不是空集合？ 對(duì)于 B中的每一條弧 i,j，計(jì)算， ki,j=b(i)+li,j,求出使 ki,j最 小的弧 c,d. 將弧 c,d加粗，令 b(d)=kc,d, vd成為已標(biāo)號(hào)點(diǎn) 是否還有未標(biāo)號(hào)的頂點(diǎn) 計(jì)算結(jié)束 是 否 是 現(xiàn)在來(lái)討論標(biāo)號(hào)法好不好？要回答這個(gè)問(wèn)題 ,首先應(yīng)該明確一下什么叫“好” ,什么叫“不好”．一般說(shuō)來(lái)，主要的好壞標(biāo)準(zhǔn)是計(jì)算起來(lái)快不快不快 (還有比的標(biāo)準(zhǔn)，例如容不容易拿上計(jì)算機(jī)計(jì)算；是否易于普及等等 )，或者說(shuō)，用這個(gè)方法計(jì)算時(shí)，需要進(jìn)行的運(yùn)算次數(shù)多不多 .當(dāng)然，運(yùn)算次數(shù)越少越好 . 167。 于是問(wèn)題轉(zhuǎn)化為在該圖中求 (8,0,0)到 (4,4,0)的一條最短路 (求最短路的算法在有向圖中仍適用 ).結(jié)果如下： ( 8 , 0 , 0 ) ( 3 , 5 , 0 ) ( 3 , 2 , 3 ) ( 6 , 2 , 0 ) ( 6 , 0 , 2 ) ( 1 , 5 , 2)( 1 , 4 , 3 ) ( 4 , 4 , 0 ) .? ? ? ? ??? 每種組合用一個(gè)點(diǎn)表示，若點(diǎn) u能通過(guò)倒酒的方式變換為 v,則 u向 v 連有向邊，并將各邊賦權(quán) 1，得一個(gè)有向賦權(quán)圖 . 大家也許會(huì)認(rèn)為，這兩個(gè)例子本來(lái)就不很難，把它轉(zhuǎn)化成圖論問(wèn)題，倒相當(dāng)麻煩，有什么好處呢？其實(shí)這種做法還是很有好處的 .因?yàn)樵谵D(zhuǎn)化前，想解決這些問(wèn)題，只能用湊的辦法，或者最多是憑經(jīng)驗(yàn) .而轉(zhuǎn)化成圖論問(wèn)題以后，就可以用一種系統(tǒng)的方法解決了 . 最后，還要指出一下，求最短有向路和求最短無(wú)向路這兩個(gè)問(wèn)題是密切關(guān)聯(lián)的 .下面將看到，求最短有向路的計(jì)算方法也可以用來(lái)求最短無(wú)向路 . 在這一章中，我們假設(shè)遇到的圖 G都是簡(jiǎn)單圖 .這樣假設(shè)是合理的，因?yàn)槿绻?G有平行弧或平行邊，例如有好幾條從 vi到 vj的弧，那么很顯然，可以把這些弧中最短的一條留下，其余的都去掉，然后在剩下的簡(jiǎn)單圖上再來(lái)求從 vs到 vt的最短有向路 .因?yàn)?G是簡(jiǎn)單圖，所以每一條弧 ak被它的起點(diǎn) vi與終點(diǎn) vj唯一決定，因此，下面我們就用 vi,vj或 i,j來(lái)表示一條弧，用 (vi,vj)或 (i,j)來(lái)表示邊，而用 l(i,j)來(lái)表示弧或邊的長(zhǎng)度 . 這一節(jié)介紹一種求有向圖上最短有向路的方法，叫做 標(biāo)號(hào)法。(7,0,1)。(6,0,2)。 (6,2,0)。(5,1,2)。(5,3,0)。 (4,2,2)。(4,4,0)。(3,3,2)。 (3,5,0)。(2,4,2)。(1,4,3)。的最短路” . 例 2: 某兩人有一只 8升的酒壺裝滿了酒，還有兩只空壺，分別為 5升和 3升 .現(xiàn)要將酒平分，求最少的操作次數(shù) . 解 設(shè) x1,x2,x3分別表示 8,5,3升酒壺中的酒量 .則 1 2 3 1 2 38 , 8 , 5 , x x x x x? ? ? ? ? ?容易算出 (x1,x2,x3) 的組合形式共 24種 . (0,5,3)。 MWS MWV WSV MS MWSV 例如， MWSV經(jīng)過(guò)一次渡河可以變成 WV(人帶著羊過(guò)河，左岸留下狼和白菜 )，又例如 MWV經(jīng)過(guò)一次渡河可以變?yōu)?W(人帶著白菜過(guò)河，留下狼 )，或變?yōu)?然反過(guò)來(lái)， W也可以變?yōu)?MWV(人帶著白菜從右岸返回左岸 ). 作出了圖 G以后，渡河問(wèn)題就歸結(jié)為下述問(wèn)題了：“在圖 G中找一條連接頂點(diǎn) MWSV與 216。(空集 ) 例如 MS表示人和羊在左岸，而狼和白菜在右岸； 216。第三章 最短路問(wèn)題 讓我們先把