網(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é)課號：70420133第5章最短路問題(ShortestPathProblem)1可編輯ppt許多實際問題都可以轉(zhuǎn)化為最短路問題

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

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

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

w33

w22

w44

w34

w23

w12

w13

w24

w14

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

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

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

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

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

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

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

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

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

即變量xij>0時,一定有

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

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

=10，u3

=11但此時只要u3=

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

=8，u3

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

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

13可編輯ppt最短路算法-當(dāng)網(wǎng)絡(luò)是無圈時，這一最短路算法的復(fù)雜度為5.2.2無圈網(wǎng)絡(luò)當(dāng)采用遞推計算求解上述方程時,每個頂點和每條弧均被考慮一次.這是求解最短路問題可能達(dá)到的最小的復(fù)雜度,因為任何算法都至少必須對每條弧考慮一次14可編輯ppt最短路算法–例例5.4計算如下網(wǎng)絡(luò)(圖5.4(a))中從節(jié)點A到所有其它節(jié)點的最短路.

EABCD1-25-1-1341ABCD1-11E-2E-2135415-13412計算過程:=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)號，進(jìn)行迭代計算.當(dāng)算法結(jié)束時，距離標(biāo)號表示的是從起點到該頂點的最短路長度.基本思想：對于V中每一個頂點j，賦予兩個數(shù)值（通常稱為“標(biāo)號”）：一個是距離標(biāo)號uj，記錄的是從起點到該頂點的最短路長度的上界；另一個是前趨標(biāo)號pred（j），記錄的是當(dāng)起點s到該頂點j的一條路長取到該上界時，該條路中頂點j前面的那個直接前趨（節(jié)點）.

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

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

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

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

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

pred(i)

i

j

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

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

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

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

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

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

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

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

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

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

如果迭代不收斂，即存在某個節(jié)點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)號us

=0,前趨標(biāo)號pred(s)=0;對所有其它節(jié)點j令uj為無窮大.STEP1:如果對所有的弧（i，j）有uj

ui

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

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

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

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

uj

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

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

，則結(jié)束，uj就是從起點s到節(jié)點j的最短路長，最短路可以通過前趨標(biāo)號（pred）回溯獲得.否則進(jìn)行下一步.STEP2：從LIST中刪去一個節(jié)點i,對從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計算網(wǎng)絡(luò)中所有節(jié)點之間的最短路：Bellman-Ford：O(nmn)=O(mn2)Floyd-Warshall算法基本思想：逐步逼近，迭代求解最短路方程:O(n3)5.3.3Floyd-Warshall算法

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

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

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

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

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