網(wǎng)絡(luò)優(yōu)化第5章最短路問題

網(wǎng)

絡(luò)

優(yōu)

化

NetworkOptimization/netopt清華大學(xué)數(shù)學(xué)科學(xué)系

謝金星辦公室：理科樓2206#（電話：62787812）Email:jxie@/~jxie/courses/netopt清華大學(xué)課號(hào)：70420133第5章最短路問題(ShortestPathProblem)1可編輯ppt許多實(shí)際問題都可以轉(zhuǎn)化為最短路問題

其有效算法經(jīng)常在其它網(wǎng)絡(luò)優(yōu)化問題中作為子算法調(diào)用

ST最短路問題的例子和意義2可編輯ppt例5.1（Single-levelUncapacitatedLotsizing）某工廠生產(chǎn)某種產(chǎn)品用以滿足市場(chǎng)需求,且已知在時(shí)段t中的市場(chǎng)需求為dt.在某時(shí)段t,如果開工生產(chǎn),則生產(chǎn)開工所需的生產(chǎn)準(zhǔn)備費(fèi)為st,單件產(chǎn)品的生產(chǎn)費(fèi)為ct.在某時(shí)段t期末,如果有產(chǎn)品庫存,單件產(chǎn)品的庫存費(fèi)為ht.假設(shè)初始庫存為0,不考慮能力限制,工廠應(yīng)如何安排生產(chǎn),可以保證按時(shí)滿足生產(chǎn),且使總費(fèi)用最小?（Wagner–Whitin，1958）最短路問題的例子-單產(chǎn)品、無能力限制的批量問題

假設(shè)在時(shí)段t,產(chǎn)品的生產(chǎn)量為xt,期末產(chǎn)品的庫存為It(I0=0);用二進(jìn)制變量yt表示在時(shí)段t工廠是否進(jìn)行生產(chǎn)準(zhǔn)備.假設(shè)費(fèi)用均非負(fù)，則在最優(yōu)解中，即可以證明：一定存在滿足條件的最優(yōu)解.可以只考慮3可編輯ppt單產(chǎn)品、無能力限制的批量問題記wij為第i時(shí)段生產(chǎn)量為時(shí)所導(dǎo)致的費(fèi)用(包括生產(chǎn)準(zhǔn)備費(fèi)、生產(chǎn)費(fèi)和庫存費(fèi)),即其中網(wǎng)絡(luò)：從所有節(jié)點(diǎn)i到j(luò)(>i)連一條弧,弧上的權(quán)為wi,j-1,如T=4時(shí)：12345w11

w33

w22

w44

w34

w23

w12

w13

w24

w14

4可編輯ppt例5.3計(jì)劃評(píng)審技術(shù),即PERT(ProjectEvaluation&ReviewTechnique),又稱網(wǎng)絡(luò)計(jì)劃技術(shù)或統(tǒng)籌法)大型復(fù)雜工程項(xiàng)目(Project)往往被分成許多子項(xiàng)目,子項(xiàng)目之間有一定的先后順序(偏序)要求,每一子項(xiàng)目需要一定的時(shí)間完成.PERT網(wǎng)絡(luò)的每條弧表示一個(gè)子項(xiàng)目,如果以弧長(zhǎng)表示每一子項(xiàng)目需要的時(shí)間,則最早完工時(shí)間對(duì)應(yīng)于網(wǎng)絡(luò)中的最長(zhǎng)路(關(guān)鍵路線).工程上所謂的關(guān)鍵路線法(CPM:CriticalPathMethod)基本上也是計(jì)劃評(píng)審技術(shù)的一部分.項(xiàng)目網(wǎng)絡(luò)不含圈,其最長(zhǎng)路問題和最短路問題都是可解的.(開始)AF(結(jié)束)566744513B

EDC5可編輯ppt最短路問題給定有向網(wǎng)絡(luò)N，弧（i，j）對(duì)應(yīng)的權(quán)又稱為弧長(zhǎng)（或費(fèi)用）.對(duì)于其中的兩個(gè)頂點(diǎn)s，t，以s為起點(diǎn)和t為終點(diǎn)的有向路稱為s-t有向路，其所經(jīng)過的所有弧上的權(quán)（或弧長(zhǎng)、費(fèi)用）之和稱為該有向路的權(quán)（或弧長(zhǎng)、費(fèi)用）.所有s-t有向路中權(quán)(或弧長(zhǎng)、費(fèi)用)最小的一條稱為s-t最短路.

對(duì)于有向網(wǎng)絡(luò)中的一個(gè)圈，定義它的權(quán)為圈上所有前向弧上的權(quán)的和,減去圈上所有反向弧上的權(quán).權(quán)為正的圈稱為正圈;權(quán)為負(fù)的圈稱為負(fù)圈;權(quán)為0的圈稱為零圈.對(duì)一個(gè)有向圈，

它的權(quán)就是圈上所有弧上的權(quán)的和.本章的圈一般都是指有向圈,我們直接將正有向圈簡(jiǎn)稱為“正圈”，

負(fù)有向圈簡(jiǎn)稱為“負(fù)圈”，

零有向圈簡(jiǎn)稱為“零圈”,而“無圈”指的是不存在有向圈.st6可編輯ppt無向網(wǎng)絡(luò)上的最短路問題一般可以轉(zhuǎn)化為有向網(wǎng)絡(luò)上的問題.如果所有弧上的權(quán)全為非負(fù)（或非正）數(shù)，只需將無向圖的一條邊代之以兩條對(duì)稱的有向弧即可.如果弧上的權(quán)有負(fù)有正，一般來說問題要復(fù)雜得多。最短路問題–兩點(diǎn)說明最長(zhǎng)路問題可以轉(zhuǎn)化為最短路問題，把弧上的費(fèi)用反號(hào)即可.必須指出：目前為止，一切最短路算法都只對(duì)不含負(fù)有向圈的網(wǎng)絡(luò)有效.對(duì)于含負(fù)有向圈的網(wǎng)絡(luò)，最短路問題是NP困難的.因此，本章中除非特別說明，一律假定網(wǎng)絡(luò)不包含負(fù)有向圈.

7可編輯pptxij表示?。╥，j）是否位于s-t路上：當(dāng)xij=1時(shí)，表示?。╥，j）位于s-t路上，當(dāng)xij=0時(shí)，表示?。╥，j）不在s-t路上.

關(guān)聯(lián)矩陣是全么模矩陣，因此0-1變量可以松弛為區(qū)間[0,1]中的實(shí)數(shù)不含負(fù)圈，變量直接松弛為所有非負(fù)實(shí)數(shù)思考：為什么xij可以不限定為{0，1}？最短路問題的數(shù)學(xué)描述8可編輯ppt5.2.1Bellman方程對(duì)偶問題為

根據(jù)互補(bǔ)松弛條件,當(dāng)x和u分別為原問題和對(duì)偶問題的最優(yōu)解時(shí):9可編輯pptBellman方程當(dāng)某弧(i,j)位于最短路上時(shí)，

即變量xij>0時(shí),一定有

如果u為對(duì)偶問題最優(yōu)解,易知u+c(c為任意實(shí)數(shù))仍為最優(yōu)解.不妨令us=0，則u的具體數(shù)值就可以唯一確定了.Bellman方程(最短路方程、動(dòng)態(tài)規(guī)劃基本方程)相當(dāng)于對(duì)節(jié)點(diǎn)j賦予的一個(gè)實(shí)數(shù)值uj（通常稱為

“標(biāo)號(hào)”），在us=0時(shí)表示的正好是節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路的長(zhǎng)度.一般情況下直接求解最短路方程是相當(dāng)困難的.10可編輯ppt定理5.1對(duì)于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點(diǎn)s到任一頂點(diǎn)j都存在最短路，它們構(gòu)成以起點(diǎn)s為根的樹形圖（稱為最短路樹（TreeofShortestPaths）或最短路樹形圖（ShortestPathArborescence）），最短路的長(zhǎng)度可以由Bellman方程唯一確定.前一部分實(shí)際上是Bellman最優(yōu)化原理的直接結(jié)果；后一部分中Bellman方程解的唯一性可以用反證法證明（略）最短路樹（樹形圖）AF566744513BEDC11可編輯ppt如果將定理中的條件“只含正有向圈”改為“不含負(fù)有向圈”：上述最短路仍然存在；Bellman方程的解的唯一性可能不成立.起點(diǎn)s到頂點(diǎn)的最短路長(zhǎng)度分別是us=u1=0，u2

=10，u3

=11但此時(shí)只要u3=

u2+111(us=u1=0)就可以滿足Bellman方程.如us=u1=0，u2

=8，u3

=9等最短路樹（樹形圖）123101-1s對(duì)于一般的網(wǎng)絡(luò)，Bellman方程只是最短路長(zhǎng)度必須滿足的必要條件，而不是充分條件；對(duì)于只含正有向圈(或無圈)的連通有向網(wǎng)絡(luò)，它才是充要條件.12可編輯ppt最短路算法-如果采用鄰接表表示法，可首先計(jì)算各節(jié)點(diǎn)的入度；然后找入度為零者編號(hào)；去掉已編號(hào)節(jié)點(diǎn)及相關(guān)弧，同時(shí)修改相鄰節(jié)點(diǎn)入度（只需掃描該去掉的節(jié)點(diǎn)的出?。?；依次類推。如果采用鄰接矩陣表示法，可首先計(jì)算各節(jié)點(diǎn)的入度；然后找入度為零者編號(hào)；去掉已編號(hào)節(jié)點(diǎn)及相關(guān)弧，同時(shí)修改相鄰節(jié)點(diǎn)入度（只需掃描該去掉的節(jié)點(diǎn)的對(duì)應(yīng)行）；依次類推。5.2.2無圈網(wǎng)絡(luò)引理5.1(拓?fù)渑判?TopologicalOrdering)設(shè)有向圖D不含有向圈,則D的頂點(diǎn)總可以重新編號(hào),使得.

該算法自然可以用來判斷有向圖是否無圈圖.

13可編輯ppt最短路算法-當(dāng)網(wǎng)絡(luò)是無圈時(shí)，這一最短路算法的復(fù)雜度為5.2.2無圈網(wǎng)絡(luò)當(dāng)采用遞推計(jì)算求解上述方程時(shí),每個(gè)頂點(diǎn)和每條弧均被考慮一次.這是求解最短路問題可能達(dá)到的最小的復(fù)雜度,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞?duì)每條弧考慮一次14可編輯ppt最短路算法–例例5.4計(jì)算如下網(wǎng)絡(luò)(圖5.4(a))中從節(jié)點(diǎn)A到所有其它節(jié)點(diǎn)的最短路.

EABCD1-25-1-1341ABCD1-11E-2E-2135415-13412計(jì)算過程:=0,=min{0+1}=1,=min{0+(-1)}=-1,=min{0+5,1+(-2),-1+3}=-1,=min{-1+1,-1+4}=0.15可編輯ppt最短路算法-算法通過不斷修改這些標(biāo)號(hào)，進(jìn)行迭代計(jì)算.當(dāng)算法結(jié)束時(shí)，距離標(biāo)號(hào)表示的是從起點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度.基本思想：對(duì)于V中每一個(gè)頂點(diǎn)j，賦予兩個(gè)數(shù)值（通常稱為“標(biāo)號(hào)”）：一個(gè)是距離標(biāo)號(hào)uj，記錄的是從起點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度的上界；另一個(gè)是前趨標(biāo)號(hào)pred（j），記錄的是當(dāng)起點(diǎn)s到該頂點(diǎn)j的一條路長(zhǎng)取到該上界時(shí)，該條路中頂點(diǎn)j前面的那個(gè)直接前趨（節(jié)點(diǎn)）.

迭代進(jìn)行計(jì)算的過程中，所有頂點(diǎn)實(shí)際上被分成了兩類：一類是離起點(diǎn)s較近的頂點(diǎn)，它們的距離標(biāo)號(hào)表示的是從點(diǎn)s到該頂點(diǎn)的最短路長(zhǎng)度，因此其標(biāo)號(hào)不會(huì)在以后的迭代中再被改變（稱為永久標(biāo)號(hào)）；一類是離起點(diǎn)s較遠(yuǎn)的頂點(diǎn)，它們的距離標(biāo)號(hào)表示的只是從點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度的上界，因此其標(biāo)號(hào)還可能會(huì)在以后的迭代中再被改變（稱為臨時(shí)標(biāo)號(hào)）.

5.2.3正費(fèi)用網(wǎng)絡(luò)(Dijkstra,1959)

16可編輯ppt正費(fèi)用網(wǎng)絡(luò)（Dijkstra算法）STEP1.如果S=V,則uj為節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路路長(zhǎng)(最短路可以通過數(shù)組pred所記錄的信息反向追蹤獲得),結(jié)束.否則繼續(xù)STEP2.STEP0.(初始化)令S=，=V，；對(duì)V中的頂點(diǎn)j(js)令初始距離標(biāo)號(hào).

STEP2.從中找到距離標(biāo)號(hào)最小的節(jié)點(diǎn)i，把它從刪除，加入S.對(duì)于所有從i出發(fā)的弧,若，則令.

轉(zhuǎn)STEP1.17可編輯ppt正費(fèi)用網(wǎng)絡(luò)（Dijkstra算法）歸納法.算法開始時(shí)結(jié)論成立.設(shè)直到迭代的第k步，上述結(jié)論(1)(2)成立.pred(j)

pred(i)

i

j

sP1P2S中具有最小標(biāo)號(hào)的頂點(diǎn)i可以移入S中，這不會(huì)破壞結(jié)論（1）.引理5.2在上述Dijkstra算法中,

（1）對(duì)于S中的任一頂點(diǎn)j，其距離標(biāo)號(hào)uj是從起點(diǎn)s到該頂點(diǎn)j的最短路路長(zhǎng)； （2）對(duì)于中的任一頂點(diǎn)j，其距離標(biāo)號(hào)uj是從起點(diǎn)s出發(fā)，只經(jīng)過S中的頂點(diǎn)到達(dá)頂點(diǎn)j的最短路路長(zhǎng).對(duì)于中的其它頂點(diǎn)k，修改標(biāo)號(hào)，不會(huì)破壞結(jié)論（2）.18可編輯pptDijkstra算法-計(jì)算復(fù)雜性分析

對(duì)于節(jié)點(diǎn)尋找過程，第一次循環(huán)時(shí)需要n次比較操作，第二次循環(huán)時(shí)需要n-1次比較操作，…，依次類推.因此，節(jié)點(diǎn)尋找過程的復(fù)雜度為綜上所述，該算法的復(fù)雜度為該算法的主要計(jì)算量在于STEP2循環(huán)（最多執(zhí)行n次），它包括兩個(gè)過程：節(jié)點(diǎn)尋找過程（從中找到距離標(biāo)號(hào)最小的節(jié)點(diǎn)i）和距離修改過程（修改與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)的距離標(biāo)號(hào)）.

對(duì)于距離修改過程，注意到一個(gè)頂點(diǎn)只有當(dāng)它與頂點(diǎn)i相鄰時(shí)，其標(biāo)號(hào)才可能變更，才需要修改標(biāo)號(hào).每次循環(huán)所需要修改標(biāo)號(hào)的頂點(diǎn)個(gè)數(shù)最多為這一過程的整體效應(yīng)相當(dāng)于對(duì)每條弧進(jìn)行一次檢查，所以該過程的總計(jì)算復(fù)雜度為O（m）.

對(duì)于稠密網(wǎng)絡(luò)，這是求解最短路問題可能達(dá)到的最小的復(fù)雜度,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞?duì)每條弧考慮一次.對(duì)于稀疏網(wǎng)絡(luò)，利用各種形式的堆（Heap），其復(fù)雜度可以降為或等19可編輯ppt標(biāo)號(hào)算法（LabelingAlgorithm）標(biāo)號(hào)算法：目的就是在算法結(jié)束時(shí)將所有臨時(shí)標(biāo)號(hào)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào).無圈網(wǎng)絡(luò)的最短路算法，也可以看成是一種標(biāo)號(hào)算法.標(biāo)號(hào)設(shè)定算法（Label-SettingAlgorithm）：在通過迭代過程對(duì)標(biāo)號(hào)進(jìn)行逐步修正的過程中，每次迭代將一個(gè)頂點(diǎn)從臨時(shí)標(biāo)號(hào)集合中移入永久標(biāo)號(hào)集合中.一般只能用來求解無圈網(wǎng)絡(luò)和正費(fèi)用網(wǎng)絡(luò)的最短路問題.標(biāo)號(hào)修正算法（Label-CorrectingAlgorithm）：每次迭代時(shí)并不一定將任何頂點(diǎn)標(biāo)號(hào)從臨時(shí)標(biāo)號(hào)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào)，只是對(duì)臨時(shí)標(biāo)號(hào)進(jìn)行一次修正，所有頂點(diǎn)標(biāo)號(hào)仍然都是臨時(shí)標(biāo)號(hào)；只有在所有迭代終止時(shí)，所有頂點(diǎn)標(biāo)號(hào)同時(shí)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào).標(biāo)號(hào)設(shè)定算法可以看成是標(biāo)號(hào)修正算法的特例，因?yàn)樵谒惴ńK止之前，任何永久標(biāo)號(hào)都可以看成是一種特殊的臨時(shí)標(biāo)號(hào).對(duì)于一般費(fèi)用網(wǎng)絡(luò)的最短路問題采用.20可編輯ppt一般費(fèi)用網(wǎng)絡(luò)：標(biāo)號(hào)修正算法

(逐次逼近法，SuccessiveApproximation)5.3.1Bellman-Ford算法(Ford,1956)歸納法計(jì)算從起點(diǎn)到所有其它頂點(diǎn)的最短路:相當(dāng)于迭代法解Bellman方程引理5.3在（5.11）~(5.13)中,臨時(shí)標(biāo)號(hào)是從起點(diǎn)s=1到頂點(diǎn)j且所經(jīng)過的弧數(shù)不超過k條時(shí)的最短路路長(zhǎng).

k=1顯然成立.假設(shè)對(duì)k成立,下面考慮k+1的情況.從起點(diǎn)s=1到頂點(diǎn)j且所經(jīng)過的弧數(shù)不超過k+1條時(shí)的最短路有兩種可能：只含有不超過k條??；含有k+1條弧。21可編輯pptBellman-Ford算法的復(fù)雜度

對(duì)于不含負(fù)有向圈的網(wǎng)絡(luò)，最短路中弧的條數(shù)不超過n-1條.

算法一定在n-1步迭代后收斂

算法的主要工作量是(5.13)式的循環(huán)迭代，對(duì)給定的k和j，只需檢查節(jié)點(diǎn)j的所有入弧即可.所以，對(duì)給定的k，正好需要對(duì)網(wǎng)絡(luò)中的每條弧檢查一次.因此，算法的總復(fù)雜度為O（mn）.

如果迭代不收斂，即存在某個(gè)節(jié)點(diǎn)j使得<,則說明網(wǎng)絡(luò)本來就含有負(fù)有向圈.

因此本算法也可以用于判斷網(wǎng)絡(luò)是否含有負(fù)有向圈，復(fù)雜度為O（mn）.

22可編輯pptBellman-Ford算法（例）123451253-4231234512-4323可編輯ppt算法的總復(fù)雜度為O(mn2C).

基本思想：逐步逼近，迭代求解最短路方程STEP0:令距離標(biāo)號(hào)us

=0,前趨標(biāo)號(hào)pred(s)=0;對(duì)所有其它節(jié)點(diǎn)j令uj為無窮大.STEP1:如果對(duì)所有的?。╥，j）有uj

ui

+wij，則結(jié)束，uj就是從起點(diǎn)s到節(jié)點(diǎn)j的最短路長(zhǎng)，最短路可以通過前趨標(biāo)號(hào)（pred）獲得.否則進(jìn)行下一步.整數(shù)權(quán)，每次迭代使得一個(gè)節(jié)點(diǎn)的距離標(biāo)號(hào)至少減少1對(duì)每個(gè)節(jié)點(diǎn)的距離標(biāo)號(hào)的修正次數(shù)不超過2nC次總迭代次數(shù)不會(huì)超過2n2C次每次迭代都對(duì)所有弧進(jìn)行檢查和判斷,需要m次操作（不指明具體尋找弧的方法時(shí)）5.3.2一般的標(biāo)號(hào)修正算法

24可編輯pptBellman-Ford算法是（一般）標(biāo)號(hào)修正算法的特例經(jīng)過k遍檢查以后，節(jié)點(diǎn)j所獲得的距離標(biāo)號(hào)

uj表示從起點(diǎn)s=1到頂點(diǎn)j且所經(jīng)過的弧數(shù)不超過k條時(shí)的最短路路長(zhǎng).在一般標(biāo)號(hào)修正算法中，可以首先對(duì)所有弧給定一個(gè)順序，然后依次檢查每條?。╥，j）并且在必要時(shí)對(duì)uj進(jìn)行修正(減少)；當(dāng)所有弧均被檢查一遍以后，再從第一條弧開始下一遍檢查.這正是Bellman-Ford算法

25可編輯ppt改進(jìn)的（一般）標(biāo)號(hào)修正算法基本思想：用鏈表記錄可能滿足

uj

>ui+wij的弧的起點(diǎn)STEP0:令LIST={s},距離標(biāo)號(hào)us

=0,前趨標(biāo)號(hào)pred(s)=0;對(duì)所有其它節(jié)點(diǎn)j令uj為無窮大。STEP1.如果LIST=

，則結(jié)束，uj就是從起點(diǎn)s到節(jié)點(diǎn)j的最短路長(zhǎng)，最短路可以通過前趨標(biāo)號(hào)（pred）回溯獲得.否則進(jìn)行下一步.STEP2：從LIST中刪去一個(gè)節(jié)點(diǎn)i,對(duì)從i出發(fā)的每條?。╥，j）判斷是否滿足uj

>ui+wij.如果是,則令uj

=ui+wij,pred(j)=i,并令LIST=LIST{j}.當(dāng)從i出發(fā)的所有弧都檢查完以后,轉(zhuǎn)STEP1.這一算法的總復(fù)雜度為26可編輯ppt計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間的最短路：Bellman-Ford：O(nmn)=O(mn2)Floyd-Warshall算法基本思想：逐步逼近，迭代求解最短路方程:O(n3)5.3.3Floyd-Warshall算法

（1962)引理5.4在（5.14）~(5.16)中,臨時(shí)標(biāo)號(hào)是不通過k，k+1，…,n節(jié)點(diǎn)(i,j除外)時(shí)從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路路長(zhǎng).歸納法k=1顯然成立.假設(shè)對(duì)k成立,下面考慮k+1的情況.從起點(diǎn)i到j(luò)且不通過k+1,…,n節(jié)點(diǎn)的最短路有兩種可能：(1)不經(jīng)過k節(jié)點(diǎn)；(2)經(jīng)過k節(jié)點(diǎn)。27可編輯pptFloyd-Warshall算法的復(fù)雜度

對(duì)于不含負(fù)有向圈的網(wǎng)絡(luò)，最短路中弧的條數(shù)不超過n-1條.

算法一定在n步迭代后收斂

算法的主要工作量是(5.16)式的循環(huán)迭代(三重循環(huán)),算法的總復(fù)雜度為O（n3）.

如果迭代不收斂，即存在節(jié)點(diǎn)i,j使得<,則說明網(wǎng)絡(luò)本來就含有負(fù)有向圈.因此本算法也可以用于判斷網(wǎng)絡(luò)是否含有負(fù)有向圈，復(fù)