大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第六章：圖-第五節(jié)-最短路徑

第五節(jié)最短路徑1、最短路徑的問題最短路徑問題的提法很多，在這里僅討論單源最短路徑問題：從某個(gè)源點(diǎn)S∈V到G中其余各頂點(diǎn)的最短路徑。對(duì)于求多源點(diǎn)的最短路徑問題，可以用每個(gè)頂點(diǎn)作為源點(diǎn)調(diào)用一次單源最短路徑問題算法予以解決?！纠肯聢D所示帶權(quán)有向圖，假定以vl為源點(diǎn)，則v1到其他各頂點(diǎn)的最短路徑下表所示。源點(diǎn)最短路徑終點(diǎn)路徑長(zhǎng)度v1v1，v3，v2v25v1v1，v3v33v1v1，v3，v2，v4v410v1v1，v3，v5v5182、迪杰斯特拉(Dijkstra)算法該算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止?！舅惴ㄋ枷搿縿?chuàng)建三個(gè)數(shù)組，數(shù)組S記錄了當(dāng)前從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合；數(shù)組dist（簡(jiǎn)稱D）記錄當(dāng)前狀態(tài)源點(diǎn)到圖中其余各頂點(diǎn)之間的最短路徑長(zhǎng)度；數(shù)組path（簡(jiǎn)稱P）是最短路徑的路徑數(shù)組，其中path[j]表示從源點(diǎn)到頂點(diǎn)j的最短路徑上頂點(diǎn)的前驅(qū)頂點(diǎn)。每一次循環(huán)都是從數(shù)組D中選擇未被加入到數(shù)組S中的頂點(diǎn)到源點(diǎn)路徑最短的頂點(diǎn)加入到數(shù)組S中，然后對(duì)數(shù)組D和數(shù)組P進(jìn)行修改，直到所有頂點(diǎn)都加到了數(shù)組S中為止?！纠恳阎邢驁D如圖所示，根據(jù)迪杰斯特拉算法畫出求源點(diǎn)v1開始的單源最短路徑的過程示意圖，以及算法的動(dòng)態(tài)執(zhí)行過程。迪杰斯特拉算法的動(dòng)態(tài)執(zhí)行情況循環(huán)集合Sj

D[1]D[2]D[3]D[4]D[5]

P[1]P[2]P[3]P[4]P[5]初始化{1}10

9

∞

18

180

l

0

0

12{1，2}20

9

14

∞

180

1

2

0

13{l，2，3}30

9

14

17

160

l

2

3

34{1，2，3，5}50

9

14

17

160

1

2

3

35{1，2，3，5，4}40

9

14

17

160

1

2

3

3當(dāng)前講授【真題選解】（例題?填空題）已知有向圖如下圖所示，其中頂點(diǎn)A到頂點(diǎn)C的最短路徑長(zhǎng)度是_________。隱藏答案【答案】35【解析】迪杰斯特拉算法的動(dòng)態(tài)執(zhí)行情況循環(huán)集合S

j

D[1]D[2]D[3]D[4]D[5]D[6]

P[1]P[2]P[3]P[4]P[5]P[5]初始化{A}AO

15

∞

2

23

∞0

l

0

1

0

02{A，D}DO

15

∞

2

23

∞0

l

0

1

4

03{A，D，B}BO

15

43

2

23

∞0

l

2

1

4

04{A，D，B，E}EO

15

35

2

23

470

l

5

1

4

55{A，D，B，E，C}CO

15

35

2

23

470

l

5

1

4

56{A,D,B,E,C,F}FO

15

35

2

23

470

l

5