通過前面的學(xué)習(xí)，我們已經(jīng)學(xué)會(huì)了圖與網(wǎng)絡(luò)問題中圖的基本概念和最小樹問題，本期小編帶大家學(xué)習(xí)最短路問題。

一 最短路問題

最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個(gè)模型，如設(shè)備更新、管道敷設(shè)、線路安排、廠區(qū)布局等。

最短路問題的一般提法如下:設(shè)G=(V,E)為連通圖，圖中各邊（vi,vj）有權(quán)l(xiāng)ij(lij=∞表示vi,vj間無邊)，vs,vt為圖中任意兩點(diǎn)，求一條道路μ，使它是從vs到vt的所有路中總權(quán)最小的路。即:L(μ)=Σ（vi，vj）∈μlij最小。

有些最短路問題也可以是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有結(jié)點(diǎn)的最短路，或求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。下面我們介紹兩種算法，可分別用于求解這幾種最短路問題。

二 Dijkstra算法

01基本思想

Dijkstra算法由Dijkstra于1959年提出，可用于求解指定兩點(diǎn)vs,vt間的最短路，或從指定點(diǎn)vs到其余各點(diǎn)的最短路，目前被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)最短路問題的最好方法。

算法的基本思路基于以下原理：若序列{vs，v1，...vn-1,vn}是從vs到vn的最短路，則序列{vs，v1，...vn-1}必為從vs到vn-1的最短路。

02算法基本步驟

???給始點(diǎn)vs以P標(biāo)號(hào)，P(vs)=0，其余節(jié)點(diǎn)均給T標(biāo)號(hào)，T(vi)=+∞(i=2,3,…,n)。

???設(shè)節(jié)點(diǎn)vi為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj：(vi,vj)∈E,且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改:T(vj)=min[T(vj),P(vi)+lij]

????比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把T標(biāo)號(hào)最小者改為P標(biāo)號(hào)，即:P(vk)= min[T(vi)]

當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部節(jié)點(diǎn)均為P標(biāo)號(hào)，則算法停止，否則用vk代替vi，返回步驟2。每一步迭代將一個(gè)點(diǎn)的標(biāo)號(hào)修改為P標(biāo)號(hào)的同時(shí)，記錄路徑。

03應(yīng)用

案例1

例1：用Dijkstra算法求圖中點(diǎn)v1到點(diǎn)v8的最短路。

解：

(1)首先給v1以P標(biāo)號(hào)，P(v1）=0，給其余所有點(diǎn)T標(biāo)號(hào)：T(vi)=+∞，（i=2,3,...8）

(2)考慮v1鄰點(diǎn)

T(v2)=min[T(v2),P(v1)+l12]=min[+∞,0+4]=4

T(v3)=min[T(v3),P(v1)+l13]=min[+∞,0+6]=6

(3)比較所有T標(biāo)號(hào)，T(v2)最小，令P(v2)=4，并記錄路徑(v1,v2)。

T(v4)=min[T(v4),P(v2)+l24]=min[+∞,4+5]=9

T(v5)=min[T(v5),P(v2)+l25]=min[+∞,4+4]=8

(4)比較所有T標(biāo)號(hào)，T(v3)最小，令P(v3)=6，并記錄路徑(v1,v3)。

(5)考慮v3鄰點(diǎn)

T(v4)=min[T(v4),P(v3)+l34]=min[9,4+6]=9

T(v5)=min[T(v5),P(v3)+l35]=min[8,6+7]=8

(6)比較所有T標(biāo)號(hào)，T(v5)最小，令P(v5)=8，并記錄路徑(v2，v5)。

(7)考慮v5鄰點(diǎn)

T(v6)=min[T(v6),P(v5)+l56]=min[+∞,8+5]=13

T(v7)=min[T(v5),P(v5)+l57]=min[+∞,8+6]=14

(8)比較所有T標(biāo)號(hào)，T(v4)最小，令P(v4)=9， 并記錄路徑(v2,v4)。

(9)考慮v4鄰點(diǎn)

T(v6)=min[T(v6),P(v4)+l46]=min[13,9+9]=13

T(v7)=min[T(v7),P(v4)+l47]=min[14,9+7]=14

(10)比較所有T標(biāo)號(hào)，T(v6)最小，令P(v6)=13, 并記錄路徑(v5,v6)。

(11)考慮v6鄰點(diǎn)

T(v7)=min[T(v7),P(v6)+l67]=min[14,13+5]=14

T(v8)=min[T(v8),P(v6)+l68]=min[+∞,13+4]=17

(12)比較所有T標(biāo)號(hào)，T(v7)最小，令P(v7)=14, 并記錄路徑(v5,v7)。

(13)考慮v7鄰點(diǎn)

T(v8)=min[T(v8),P(v7)+l78]=min[17,14+1]=15

(14)因?yàn)橹挥幸粋€(gè)T標(biāo)號(hào)T(v8)最小，令P(v8)=15,并記錄路徑(v7,v8)，v1到v8最短路為:v1→v2→v5→v7→v8。

★Dijkstra法實(shí)際應(yīng)用分析

①能夠一次算出從起點(diǎn)到其他各節(jié)點(diǎn)的最短路徑；

②計(jì)算效率不高，速度較慢，所需存儲(chǔ)空間多，在大規(guī)模規(guī)劃中受到一定限制；

③Dijkstra算法僅適合于所有的權(quán)wij?≥0的情形。如果當(dāng)賦權(quán)有向圖中存在有負(fù)權(quán)弧時(shí)，則算法失效。

案例2 設(shè)備更新問題

某工廠使用一臺(tái)設(shè)備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付較多維修費(fèi)；若購買一臺(tái)新設(shè)備，要付購買費(fèi)。試制訂一個(gè)5年的更新計(jì)劃，使總支出最少。由表知該設(shè)備在各年的購買費(fèi)，及在不同役齡的殘值與維修費(fèi)。

解：用點(diǎn)vi表示第i年年初購進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn)v6，表示第5年年底。

邊(vi,vj)表示第i年初購進(jìn)的設(shè)備一直使用到第j年年初(即第j-1年年底)。

邊(vi,vj)上的數(shù)字表示第i年初購進(jìn)設(shè)備后，一直使用到第j年初所需支付的購買、維修凈費(fèi)用。

例如(v1,v2)邊上的數(shù)字12=(第一年購買的費(fèi)用11)+(一年的維修費(fèi)用5)-(一年役齡機(jī)器的殘值4)，同理計(jì)算得到其他數(shù)字。

這樣設(shè)備更新問題就變?yōu)?求從v1到v6的最短路問題。

(1)首先給v1以P標(biāo)號(hào)，P(v1）=0，給其余所有點(diǎn)T標(biāo)號(hào)：T(vi)=+∞，（i=2,3,...6）

(2)考慮v1鄰點(diǎn)

T(v2)=min[T(v2),P(v1)+l12]=min[+∞,0+12]=12

T(v3)=min[T(v3),P(v1)+l13]=min[+∞,0+19]=19

T(v4)=min[T(v4),P(v1)+l14]=min[+∞,0+28]=28

T(v5)=min[T(v5),P(v1)+l15]=min[+∞,0+40]=40

T(v6)=min[T(v6),P(v1)+l16]=min[+∞,0+59]=59

(3)比較所有T標(biāo)號(hào)，T(v2)最小，所以P(v2)=12，并記錄路徑(v1，v2)。

(4)考慮v2鄰點(diǎn)

T(v3)=min[T(v3),P(v2)+l23]=min[19,12+13]=19

T(v4)=min[T(v4),P(v2)+l24]=min[28,12+20]=28

T(v5)=min[T(v5),P(v2)+l25]=min[40,12+29]=40

T(v6)=min[T(v6),P(v2)+l26]=min[59,12+41]=53

(5)比較所有T標(biāo)號(hào)，T(v3)最小，令P(v3)=19，并記錄路徑(v1,v3)。

(6)考慮v3鄰點(diǎn)

T(v4)=min[T(v4),P(v3)+l34]=min[28,19+14]=28

T(v5)=min[T(v5),P(v3)+l35]=min[40,19+21]=40

T(v6)=min[T(v6),P(v3)+l36]=min[53,19+30]=49

(7)比較T標(biāo)號(hào)，T(v4)最小，令P(v4)=28，并記錄路徑(v1,v4)。

(8)考慮v4鄰點(diǎn)

T(v5)=min[T(v5),P(v4)+l45]=min[40,28+15]=40

T(v6)=min[T(v6),P(v4)+l46]=min[49,28+22]=49

(9)比較所有T標(biāo)號(hào)，T(v5)最小，令P(v5)=40, 并記錄路徑(v1,v5)。

(10)考慮v5鄰點(diǎn)

T(v6)=min[T(v6),P(v5)+l56]=min[49,40+15]=49

(11)因?yàn)橹挥幸粋€(gè)T標(biāo)號(hào)T(v6)，令P(v6)=49,并記錄路徑(v3,v6)，計(jì)算結(jié)束。

計(jì)算結(jié)果表明:v1→v3→v6為最短路，路長(zhǎng)為49。即在第一年、第三年初各購買一臺(tái)新設(shè)備為最優(yōu)決策，這時(shí)5年的總費(fèi)用為49。

案例3 選址問題?

某連鎖企業(yè)在某地區(qū)有6個(gè)銷售點(diǎn)，已知該地區(qū)的交通網(wǎng)絡(luò)如圖所示，其中點(diǎn)代表銷售點(diǎn)，邊表示公路，lij為銷售點(diǎn)間公路距離，問倉庫應(yīng)建在哪個(gè)小區(qū)，可使離倉庫最遠(yuǎn)的銷售點(diǎn)到倉庫的路程最近?

解：此問題實(shí)際要求出圖的中心，可以化為一系列求最短路問題。

先求出v1到其他各點(diǎn)的最短路長(zhǎng)dj，令D(v1)=max(d1,d2,…,d6)，表示若倉庫建在v1，則離倉庫最遠(yuǎn)的銷售點(diǎn)距離為D(v1)。再依次計(jì)算v2,v3,…,v6到其余各點(diǎn)的最短路，每一次計(jì)算都是以此最小路問題，以D(v1)為例：

(1)首先給v1以P標(biāo)號(hào)，P(v1）=0，給其余所有點(diǎn)T標(biāo)號(hào)：T(vi)=+∞，（i=2,3,...6）

(2)考慮v1鄰點(diǎn)

T(v2)=min[T(v2),P(v1)+l12]=min[+∞,0+20]=20

T(v5)=min[T(v5),P(v1)+l15]=min[+∞,0+15]=15

(3)比較所有T標(biāo)號(hào)，T(v5)最小，所以P(v5)=15。

(4)考慮v5鄰點(diǎn)

T(v2)=min[T(v2),P(v5)+l25]=min[20,15+25]=20

T(v3)=min[T(v3),P(v5)+l35]=min[+∞,15+18]=33

T(v6)=min[T(v6),P(v5)+l56]=min[+∞,15+15]=30

(5)比較所有T標(biāo)號(hào)，T(v2)最小，令P(v2)=20。

(6)考慮v2鄰點(diǎn)

T(v3)=min[T(v3),P(v2)+l23]=min[33,20+20]=33

T(v4)=min[T(v4),P(v2)+l24]=min[+∞,20+60]=80

(7)比較所有T標(biāo)號(hào)，T(v6)最小，令P(v6)=30，v6鄰點(diǎn)僅有v5，再比較其余T標(biāo)號(hào)，T(v3)最小，令P(v3)=33。

(8)考慮v3鄰點(diǎn)

T(v4)=min[T(v4),P(v3)+l34]=min[80,33+30]=63

(9)比較所有T標(biāo)號(hào)，T(v4)最小，令P(v4)=63。由此得到：

d1=0，d2=20，d3=33

d4=63，d5=15，d6=30

所以：D(v1)=max(d1,d2,…,d6)=63

同理可求出D(v2),D(v3),…,D(v6)，D(vi)(i=1,…,6)中最小者即為所求，計(jì)算結(jié)果見下表：

由于D(v3)=33最小，所以倉庫應(yīng)建在v3，此時(shí)離倉庫最遠(yuǎn)的銷售點(diǎn)(v1和v6)距離為33。

三 Floyd算法

01基本思想

某些問題是要求解網(wǎng)絡(luò)上任意兩點(diǎn)間最短路，這類問題可以用Dijkstra算法依次改變起點(diǎn)的辦法計(jì)算，但比較繁瑣。而Floyd方法可直接求出網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。

Floyd算法的思想是將n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)表示為n行n列的矩陣，而矩陣中的元素(i,j)表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離uij，如果兩點(diǎn)直接沒有邊相連，則相應(yīng)的元素就是無窮(∞)。

求解過程中依次把各個(gè)節(jié)點(diǎn)當(dāng)成每對(duì)點(diǎn)之間的中間點(diǎn)，在加入中間點(diǎn)以后，判斷新的路徑是不是比原來的短，如果比原來的短，進(jìn)行替換，直到得到兩個(gè)節(jié)點(diǎn)之間的最短距離。

02算法基本步驟

為了計(jì)算方便，令網(wǎng)絡(luò)的權(quán)矩陣為U=(?uij?)nxn，uij為vi到vj的距離，其中

令S=(sij?)nxn?,?sij為vi到vj的路徑上第一條弧的終點(diǎn)。

（1）初始時(shí)，對(duì)于任意兩個(gè)頂點(diǎn)，若它們之間存在邊，則以此邊上的權(quán)值作為它們之間的最短路徑長(zhǎng)度，若不存在有向邊，則以∞作為它們之間的最短路徑長(zhǎng)度。

以此輸入權(quán)矩陣U(0)=U，并輸入S(0)=(sij?(0))nxn?, sij?(0)=j (i,j=1,2,3,..,n?)，此時(shí)vi到vj的路徑上第一條弧的終點(diǎn)為j。

（2）在原路徑中加入頂點(diǎn)v1作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑短，則以此新路徑代替原路徑，從而得到：

U(1)=(uij?(1）)nxn，uij(1)=min[uij(0）,uik(0)+ukj(0)]是從vi到vj路徑中的最短路長(zhǎng)度，路徑的中間點(diǎn)只允許為v1。

S(1)=(sij?(1))nxn?, sij?(1)=1或j ，代表此時(shí)vi到vj的路徑上第一條弧的終點(diǎn)可能是1也可能是j。

（3）以此類推，之后逐步嘗試在原路徑中加入k個(gè)頂點(diǎn)作為中間頂點(diǎn)，以更短的新路徑代替原路徑。

由此得到：U(k)?= (uij(k))nxn?(k=1,2,3,..,n)，其中uij(k)=min[uij(k-1),uik(k-1)+ukj(k-1)]是從vi到vj路徑中的最短路長(zhǎng)度，路徑的中間點(diǎn)只允許為v1,v2,...vk。

S(k)=(sij?(k))nxn? (k=1,2,3,..,n)

即若新的路徑長(zhǎng)于原路徑，vi到vj的路徑上第一條弧的終點(diǎn)不變；若新的路徑短于原路徑，vi到vj的路徑上第一條弧的終點(diǎn)為：加入k-1個(gè)頂點(diǎn)作為中間頂點(diǎn)后，vi到vk的路徑上第一條弧的終點(diǎn)。

（4）當(dāng)k=n時(shí)

U(n)=(uij(n))nxn，uij(n)就是vi到vj的最短路路長(zhǎng)。

S(n)=(sij(n))nxn?，sij(n)是vi到vj的最短路第一條弧的終點(diǎn)。

03應(yīng)用

案例4

求如下網(wǎng)絡(luò)中各點(diǎn)對(duì)間最短路的路長(zhǎng)。

解：

用U(0)的第一行、第一列來修正其余的uij，即作：uij(1)=min[uij(0),ui1(0)+u1j(0)]

同時(shí)，在修正uij(1)處修改Sij(1)=Si1(0)，v1成為每對(duì)點(diǎn)之間的中間點(diǎn)，如v4→v2路徑變?yōu)関4→v1→v2，其第一段弧與v4→v1的第一段弧相同。

用U(1)的第二行、第二列修正其余的uij

修正后，兩點(diǎn)間路徑可能經(jīng)過v1和v2，如v1→v3的路徑變?yōu)関1→v2→v3，其第一段弧與v1→v2的第一段弧相同。

用U(2)第三行、第三列修正其余的uij

用U(3)第四行、第四列修正其余的uij

用U(4)第五行、第五列修正其余的uij

?從v1到v3的最短路長(zhǎng)度u13(5)=8

路徑：∵ s13(5)=2,s23(5)=5,s53(5)=4,s43(5)=3

∴v1到v3的最短路路徑為：P13=P(v1,v2,v5,v4,v3)

?從v5到v2的最短路長(zhǎng)度u52(5)=7

路徑：∵?s52(5)=4,s42(5)=1,s12(5)=2

∴v5到v2的最短路路徑為：P52=P(v5,v4,v1,v2)

★Dijkstra和Floyd方法對(duì)比

相同點(diǎn)

?Dijkstra和Floyd都可以找到從一點(diǎn)到另一點(diǎn)的最短路徑；

?兩者思路相似，都是每次增加一個(gè)跳板，然后更新兩節(jié)點(diǎn)間距離。

不同點(diǎn)

?Dijkstra是解決單源最短路徑，而Floyd能解決任意源最短路徑問題。但用Dijkstra算法依次改變起點(diǎn)的辦法，也可計(jì)算任意源的最短路徑；

?Dijkstra屬于貪心算法，通過選擇將問題歸為小的子問題，而貪心算法選擇的策略具有無后效性，不存在回溯的過程，因此不能計(jì)算負(fù)權(quán)圖。Floyd是動(dòng)態(tài)規(guī)劃思想，將大規(guī)模的問題自頂向下劃分為了小規(guī)模的問題，因?yàn)閯?dòng)態(tài)規(guī)劃是可以回溯的，所以它可以計(jì)算負(fù)權(quán)圖。

以上就是關(guān)于最短路問題的全部?jī)?nèi)容了，學(xué)習(xí)完這一節(jié)，大家可以試著對(duì)一些實(shí)際問題進(jìn)行應(yīng)用練習(xí)。下一次小編將帶大家學(xué)習(xí)最大流問題，敬請(qǐng)關(guān)注！