算法設(shè)計(jì)與分析 課件 第五章 貪心法 5.2.3 單源最短路徑問(wèn)題

計(jì)算機(jī)算法設(shè)計(jì)與分析第5章貪心法5.2.3單源最短路徑問(wèn)題給定一個(gè)帶權(quán)有向圖

G=(V,E)，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。給定圖G中的一個(gè)頂點(diǎn)v0∈V，稱為源點(diǎn)。求源點(diǎn)v0到G中其余各頂點(diǎn)的最短路徑長(zhǎng)度。這里的長(zhǎng)度是指路徑上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。5.2.3單源最短路徑問(wèn)題源點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度11無(wú)

2(1,3,2)7

3(1,3)3

4(1,3,2,4)9

5(1,3,5)55.2.3單源最短路徑問(wèn)題dist[i]表示計(jì)算過(guò)程中源點(diǎn)到各目標(biāo)頂點(diǎn)i的當(dāng)前最短路徑長(zhǎng)度，dist[i]隨著計(jì)算過(guò)程會(huì)不斷變化，其初始值為源點(diǎn)到其余頂點(diǎn)有向邊的權(quán)值，若不存在有向邊則用無(wú)窮大。path[i]表示在最短路徑上頂點(diǎn)i的前一個(gè)頂點(diǎn)編號(hào)。集合S表示已求出最短路徑的頂點(diǎn)的集合。集合T（T=V-S）表示尚未確定最短路徑的頂點(diǎn)集合，V是圖G中頂點(diǎn)的集合。二維數(shù)組edge表示圖G的鄰接矩陣。貪心策略，Dijkstra算法迪杰斯特拉（Dijkstra）提出了一個(gè)按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑的貪心算法，對(duì)于有向帶權(quán)圖，算法步驟如下：（1）令S={1}，T=V-S，T中頂點(diǎn)i對(duì)應(yīng)的距離值dist[i]：若邊<1,i>∈E，dist[i]=edge[1][i],否則dist[i]=∞。（2）從T中選取一個(gè)其距S最近，即dist值最小的頂點(diǎn)k，加入S，T=V-{k}，對(duì)T中所有的頂點(diǎn)i的距離值dist[i]進(jìn)行修改：

（3）重復(fù)上述步驟（2），直到S中包含所有頂點(diǎn)，即|S|=|V|為止，這時(shí)T=V-S={}。單源最短路徑問(wèn)題迭代Sk2345初始{1}--dist[2]=10path[2]=1dist[3]=3path[3]=1dist[4]=∞path[4]=-1dist[5]=∞path[5]=-11{1,3}3dist[2]=7path[2]=3--dist[4]=11path[4]=3dist[5]=5path[5]=32{1,3,5}5dist[2]=7path[2]=3--dist[4]=11path[4]=3--3{1,3,5,2}2----dist[4]=9path[4]=2--4{1,3,5,2,4}4--------效率分析每次從T中尋找一個(gè)最小dist值的頂點(diǎn)k加入到S（找最小值時(shí)間復(fù)雜度O(n)），并修改T中剩余頂點(diǎn)的dist值。對(duì)于n個(gè)頂點(diǎn)的圖G，這個(gè)過(guò)程需要重復(fù)n-1次，所以算法時(shí)間復(fù)雜度為O(n2)。若在尋找最小dist值過(guò)