運(yùn)籌學(xué)最短路徑實(shí)驗(yàn)

運(yùn)籌學(xué)最短路徑實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目:最短路徑問(wèn)題實(shí)驗(yàn)學(xué)時(shí):4實(shí)驗(yàn)日期:20121130實(shí)驗(yàn)要求案例模型分析實(shí)驗(yàn)內(nèi)容:用最短路徑模型解決具體問(wèn)題前言運(yùn)輸就是物流過(guò)程的主要職能之一,也就是物流過(guò)程各項(xiàng)業(yè)務(wù)的中心活動(dòng)。物流過(guò)DijkstraDijkstra算法的基本步驟如下:給起點(diǎn)

Pp1

0TTV1

。若vi

點(diǎn)為剛得到的ｐ標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn)為vj

,vi j

這條邊,且v Tvj

的T標(biāo)號(hào)進(jìn)行如下更改Tj

minTvj

i

lij(3)比較所有具有Ｔ標(biāo)號(hào)的點(diǎn),把最小者改為Ｐ標(biāo)號(hào),即P

i

,當(dāng)存在兩個(gè)以上最小者時(shí),可同時(shí)改為Ｐ標(biāo)號(hào),若全部點(diǎn)均為Ｐ標(biāo)號(hào),則停止,否則vvi

改為第二步重做。0運(yùn)籌學(xué)最短路徑實(shí)驗(yàn)運(yùn)籌學(xué)最短路徑實(shí)驗(yàn)PAGEPAGE1案例分析v1

出發(fā),經(jīng)哪條路線達(dá)到v8

才能使總行程最短？使用Dijkstra求解。v 5 v 9 v2 4 64 4 7 5 4v v1 86 4 5 1v3步驟:

7 v 6 v5 7首先給v1

P1

0TTi

i1,2,,8(1)考察點(diǎn)

,邊

,V,V1 1 2 1 3T

min,0442

2

12 TV minTV3

,PV l1

,066(2)比較所有T2

3

T2

4最小,所以給V2

以P標(biāo)號(hào),令PV2

4,記錄路徑,V1 23、 (1)V2

P,V2 4

,V2 5Tl ,4594 4 2 24TV5

5

2

l25

min,448(2)比較所有T3

4

5

T3

6最小,給V3

以P標(biāo)號(hào),令PV3

6,記錄路徑,V1 34、 (1)V3

P,V3 4

,V3 5T4T

4

3

l34l

49min8,6785 5 3 35(2T4

5

T5

8最小,給V5

以P標(biāo)號(hào),令PV5

8,記錄路徑,V2 55、(1)V5

P,V5 6

,V5 7T6T

6

5

l56l

,8513,86147 7 5 57(2)比較所有T標(biāo)號(hào)4

6

7

T4

9最小,給V4

以P標(biāo)號(hào),令9,記錄路徑,V4 2 46、(1)V4

P,V4 6

,V4 7T6T7

67

44

l46l47

913714(2)比較所有T6

7

T6

13最小,給V6

以P6

13,記錄路徑,V5 67、(1)V6

P,V6 7

,V6 8T7T

7

6

l67l

min14,13414min,134178 8 6 68(2)比較所有T標(biāo)號(hào),7

8

T7

14V7

以P標(biāo)號(hào),令PV7

14,記錄路徑,V5 78、(1)V7

P,V7 8TV8

8

7

l78

min17,14115,V7 8

(2)比較所有TT8

15最小,給V8

以P8

15,記錄路徑至此可以得到最短路徑為VV1 2

VV5

V158實(shí)驗(yàn)總結(jié)科學(xué)合理的運(yùn)輸路線對(duì)物流的成本的大小影響很大。Dijkstra力,Dijkstra,根據(jù)距V1

從近到遠(yuǎn)的順序,依次求