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

網(wǎng)

絡(luò)

優(yōu)

化

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

謝金星辦公室：理科樓2206#（電話：62787812）Email:jxie@/~jxie/courses/netopt清華大學(xué)課號(hào)：70420133第5章最短路問(wèn)題(ShortestPathProblem)1網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!許多實(shí)際問(wèn)題都可以轉(zhuǎn)化為最短路問(wèn)題

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

ST最短路問(wèn)題的例子和意義2網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!例5.1（Single-levelUncapacitatedLotsizing）某工廠生產(chǎn)某種產(chǎn)品用以滿足市場(chǎng)需求,且已知在時(shí)段t中的市場(chǎng)需求為dt.在某時(shí)段t,如果開(kāi)工生產(chǎn),則生產(chǎn)開(kāi)工所需的生產(chǎn)準(zhǔn)備費(fèi)為st,單件產(chǎn)品的生產(chǎn)費(fèi)為ct.在某時(shí)段t期末,如果有產(chǎn)品庫(kù)存,單件產(chǎn)品的庫(kù)存費(fèi)為ht.假設(shè)初始庫(kù)存為0,不考慮能力限制,工廠應(yīng)如何安排生產(chǎn),可以保證按時(shí)滿足生產(chǎn),且使總費(fèi)用最小?（Wagner–Whitin，1958）最短路問(wèn)題的例子-單產(chǎn)品、無(wú)能力限制的批量問(wèn)題

假設(shè)在時(shí)段t,產(chǎn)品的生產(chǎn)量為xt,期末產(chǎn)品的庫(kù)存為It(I0=0);用二進(jìn)制變量yt表示在時(shí)段t工廠是否進(jìn)行生產(chǎn)準(zhǔn)備.假設(shè)費(fèi)用均非負(fù)，則在最優(yōu)解中，即可以證明：一定存在滿足條件的最優(yōu)解.可以只考慮3網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!單產(chǎn)品、無(wú)能力限制的批量問(wèn)題記wij為第i時(shí)段生產(chǎn)量為時(shí)所導(dǎo)致的費(fèi)用(包括生產(chǎn)準(zhǔn)備費(fèi)、生產(chǎn)費(fèi)和庫(kù)存費(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網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!最短路問(wèn)題給定有向網(wǎng)絡(luò)N，?。╥，j）對(duì)應(yīng)的權(quán)又稱(chēng)為弧長(zhǎng)（或費(fèi)用）.對(duì)于其中的兩個(gè)頂點(diǎn)s，t，以s為起點(diǎn)和t為終點(diǎn)的有向路稱(chēng)為s-t有向路，其所經(jīng)過(guò)的所有弧上的權(quán)（或弧長(zhǎng)、費(fèi)用）之和稱(chēng)為該有向路的權(quán)（或弧長(zhǎng)、費(fèi)用）.所有s-t有向路中權(quán)(或弧長(zhǎng)、費(fèi)用)最小的一條稱(chēng)為s-t最短路.

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

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

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

零有向圈簡(jiǎn)稱(chēng)為“零圈”,而“無(wú)圈”指的是不存在有向圈.st5網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!xij表示弧（i，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}？最短路問(wèn)題的數(shù)學(xué)描述6網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!Bellman方程當(dāng)某弧(i,j)位于最短路上時(shí)，

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

如果u為對(duì)偶問(wèn)題最優(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（通常稱(chēng)為

“標(biāo)號(hào)”），在us=0時(shí)表示的正好是節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路的長(zhǎng)度.一般情況下直接求解最短路方程是相當(dāng)困難的.7網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!如果將定理中的條件“只含正有向圈”改為“不含負(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等最短路樹(shù)（樹(shù)形圖）123101-1s對(duì)于一般的網(wǎng)絡(luò)，Bellman方程只是最短路長(zhǎng)度必須滿足的必要條件，而不是充分條件；對(duì)于只含正有向圈(或無(wú)圈)的連通有向網(wǎng)絡(luò)，它才是充要條件.8網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!最短路算法-當(dāng)網(wǎng)絡(luò)是無(wú)圈時(shí)，這一最短路算法的復(fù)雜度為5.2.2無(wú)圈網(wǎng)絡(luò)當(dāng)采用遞推計(jì)算求解上述方程時(shí),每個(gè)頂點(diǎn)和每條弧均被考慮一次.這是求解最短路問(wèn)題可能達(dá)到的最小的復(fù)雜度,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞?duì)每條弧考慮一次9網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!最短路算法-算法通過(guò)不斷修改這些標(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ù)值（通常稱(chēng)為“標(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ì)算的過(guò)程中，所有頂點(diǎn)實(shí)際上被分成了兩類(lèi)：一類(lèi)是離起點(diǎn)s較近的頂點(diǎn)，它們的距離標(biāo)號(hào)表示的是從點(diǎn)s到該頂點(diǎn)的最短路長(zhǎng)度，因此其標(biāo)號(hào)不會(huì)在以后的迭代中再被改變（稱(chēng)為永久標(biāo)號(hào)）；一類(lèi)是離起點(diǎn)s較遠(yuǎn)的頂點(diǎn)，它們的距離標(biāo)號(hào)表示的只是從點(diǎn)到該頂點(diǎn)的最短路長(zhǎng)度的上界，因此其標(biāo)號(hào)還可能會(huì)在以后的迭代中再被改變（稱(chēng)為臨時(shí)標(biāo)號(hào)）.

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

10網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!正費(fèi)用網(wǎng)絡(luò)（Dijkstra算法）歸納法.算法開(kāi)始時(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)過(guò)S中的頂點(diǎn)到達(dá)頂點(diǎn)j的最短路路長(zhǎng).對(duì)于中的其它頂點(diǎn)k，修改標(biāo)號(hào)，不會(huì)破壞結(jié)論（2）.11網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!標(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ú)圈網(wǎng)絡(luò)的最短路算法，也可以看成是一種標(biāo)號(hào)算法.標(biāo)號(hào)設(shè)定算法（Label-SettingAlgorithm）：在通過(guò)迭代過(guò)程對(duì)標(biāo)號(hào)進(jìn)行逐步修正的過(guò)程中，每次迭代將一個(gè)頂點(diǎn)從臨時(shí)標(biāo)號(hào)集合中移入永久標(biāo)號(hào)集合中.一般只能用來(lái)求解無(wú)圈網(wǎng)絡(luò)和正費(fèi)用網(wǎng)絡(luò)的最短路問(wèn)題.標(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ò)的最短路問(wèn)題采用.12網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!Bellman-Ford算法的復(fù)雜度

對(duì)于不含負(fù)有向圈的網(wǎng)絡(luò)，最短路中弧的條數(shù)不超過(guò)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使得<,則說(shuō)明網(wǎng)絡(luò)本來(lái)就含有負(fù)有向圈.因此本算法也可以用于判斷網(wǎng)絡(luò)是否含有負(fù)有向圈，復(fù)雜度為O（mn）.

13網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!算法的總復(fù)雜度為O(mn2C).

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

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

ui

+wij，則結(jié)束，uj就是從起點(diǎn)s到節(jié)點(diǎn)j的最短路長(zhǎng)，最短路可以通過(guò)前趨標(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ù)不超過(guò)2nC次總迭代次數(shù)不會(huì)超過(guò)2n2C次每次迭代都對(duì)所有弧進(jìn)行檢查和判斷,需要m次操作（不指明具體尋找弧的方法時(shí)）5.3.2一般的標(biāo)號(hào)修正算法

14網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!改進(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為無(wú)窮大。STEP1.如果LIST=

，則結(jié)束，uj就是從起點(diǎn)s到節(jié)點(diǎn)j的最短路長(zhǎng)，最短路可以通過(guò)前趨標(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ù)雜度為15網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!Floyd-Warshall算法的復(fù)雜度

對(duì)于不含負(fù)有向圈的網(wǎng)絡(luò)，最短路中弧的條數(shù)不超過(guò)n-1條.算法一定在n步迭代后收斂

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

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

在某次迭代k發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)i使得<0,則說(shuō)明網(wǎng)絡(luò)本來(lái)就含有負(fù)有向圈.16網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!Floyd-Warshall算法的例

12344-3-365106-7317網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!Floyd-Warshall算法的例

終點(diǎn)1234

起點(diǎn)1

(1,2)(1,3)(1,3),(3,4)2(2,1)

(2,3)(2,3),(3,4)3(3,4),(4,2),(2,1)(3,4),(4,2)

(3,4)4(4,2),(2,1)(4,2)(4,2)(2,3)

18網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!例5.3計(jì)劃評(píng)審技術(shù),即PERT(ProjectEvaluation&ReviewTechnique),又稱(chēng)網(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)路問(wèn)題和最短路問(wèn)題都是可解的.(開(kāi)始)AF(結(jié)束)566744513B

EDC19網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!無(wú)向網(wǎng)絡(luò)上的最短路問(wèn)題一般可以轉(zhuǎn)化為有向網(wǎng)絡(luò)上的問(wèn)題.如果所有弧上的權(quán)全為非負(fù)（或非正）數(shù)，只需將無(wú)向圖的一條邊代之以兩條對(duì)稱(chēng)的有向弧即可.如果弧上的權(quán)有負(fù)有正，一般來(lái)說(shuō)問(wèn)題要復(fù)雜得多。最短路問(wèn)題–兩點(diǎn)說(shuō)明最長(zhǎng)路問(wèn)題可以轉(zhuǎn)化為最短路問(wèn)題，把弧上的費(fèi)用反號(hào)即可.必須指出：目前為止，一切最短路算法都只對(duì)不含負(fù)有向圈的網(wǎng)絡(luò)有效.對(duì)于含負(fù)有向圈的網(wǎng)絡(luò)，最短路問(wèn)題是NP困難的.因此，本章中除非特別說(shuō)明，一律假定網(wǎng)絡(luò)不包含負(fù)有向圈.

20網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!5.2.1Bellman方程對(duì)偶問(wèn)題為

根據(jù)互補(bǔ)松弛條件,當(dāng)x和u分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解時(shí):21網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!定理5.1對(duì)于只含正有向圈的連通有向網(wǎng)絡(luò)，從起點(diǎn)s到任一頂點(diǎn)j都存在最短路，它們構(gòu)成以起點(diǎn)s為根的樹(shù)形圖（稱(chēng)為最短路樹(shù)（TreeofShortestPaths）或最短路樹(shù)形圖（ShortestPathArborescence）），最短路的長(zhǎng)度可以由Bellman方程唯一確定.前一部分實(shí)際上是Bellman最優(yōu)化原理的直接結(jié)果；后一部分中Bellman方程解的唯一性可以用反證法證明（略）最短路樹(shù)（樹(shù)形圖）AF566744513BEDC22網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!最短路算法-如果采用鄰接表表示法，可首先計(jì)算各節(jié)點(diǎn)的入度；然后找入度為零者編號(hào)；去掉已編號(hào)節(jié)點(diǎn)及相關(guān)弧，同時(shí)修改相鄰節(jié)點(diǎn)入度（只需掃描該去掉的節(jié)點(diǎn)的出?。灰来晤?lèi)推。如果采用鄰接矩陣表示法，可首先計(jì)算各節(jié)點(diǎn)的入度；然后找入度為零者編號(hào)；去掉已編號(hào)節(jié)點(diǎn)及相關(guān)弧，同時(shí)修改相鄰節(jié)點(diǎn)入度（只需掃描該去掉的節(jié)點(diǎn)的對(duì)應(yīng)行）；依次類(lèi)推。5.2.2無(wú)圈網(wǎng)絡(luò)引理5.1(拓?fù)渑判?TopologicalOrdering)設(shè)有向圖D不含有向圈,則D的頂點(diǎn)總可以重新編號(hào),使得.

該算法自然可以用來(lái)判斷有向圖是否無(wú)圈圖.

23網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!最短路算法–例例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ì)算過(guò)程:=0,=min{0+1}=1,=min{0+(-1)}=-1,=min{0+5,1+(-2),-1+3}=-1,=min{-1+1,-1+4}=0.24網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!正費(fèi)用網(wǎng)絡(luò)（Dijkstra算法）STEP1.如果S=V,則uj為節(jié)點(diǎn)s到節(jié)點(diǎn)j的最短路路長(zhǎng)(最短路可以通過(guò)數(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.25網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!Dijkstra算法-計(jì)算復(fù)雜性分析

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

對(duì)于距離修改過(guò)程，注意到一個(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ù)最多為這一過(guò)程的整體效應(yīng)相當(dāng)于對(duì)每條弧進(jìn)行一次檢查，所以該過(guò)程的總計(jì)算復(fù)雜度為O（m）.

對(duì)于稠密網(wǎng)絡(luò)，這是求解最短路問(wèn)題可能達(dá)到的最小的復(fù)雜度,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞?duì)每條弧考慮一次.對(duì)于稀疏網(wǎng)絡(luò)，利用各種形式的堆（Heap），其復(fù)雜度可以降為或等26網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!一般費(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)過(guò)的弧數(shù)不超過(guò)k條時(shí)的最短路路長(zhǎng).

k=1顯然成立.假設(shè)對(duì)k成立,下面考慮k+1的情況.從起點(diǎn)s=1到頂點(diǎn)j且所經(jīng)過(guò)的弧數(shù)不超過(guò)k+1條時(shí)的最短路有兩種可能：只含有不超過(guò)k條?。缓衚+1條弧。27網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!Bellman-Ford算法（例）123451253-4231234512-4328網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!Bellman-Ford算法是（一般）標(biāo)號(hào)修正算法的特例經(jīng)過(guò)k遍檢查以后，節(jié)點(diǎn)j所獲得的距離標(biāo)號(hào)

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

29網(wǎng)絡(luò)優(yōu)化第5章最短路問(wèn)題共33頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間的最短路：Bellman-Ford：O(nmn)=O(mn2)Floyd-Warshall算法基本思想