第五章地理信息系統(tǒng)-最短路徑算法

1、物流信息管理大連海事大學(xué)第五章 地理信息系統(tǒng)最短路徑原理與算法1. 數(shù)學(xué)模型2. 標(biāo)號(hào)法3. 程序流程最短路徑問題最短路徑問題（一）最短路徑的含義（一）最短路徑的含義“純距離純距離”意義上的最短路徑意義上的最短路徑 例如，需要運(yùn)送一批物資從一個(gè)城市到另一個(gè)城市，選擇什么樣的運(yùn)輸路線距離最短？“經(jīng)濟(jì)距離經(jīng)濟(jì)距離”意義上的最短路徑意義上的最短路徑 例如，某公司在10大港口C1，C2，C10設(shè)有貨棧，從Ci到Cj之間的直接航運(yùn)價(jià)格，是由市場(chǎng)動(dòng)態(tài)決定的。如果兩個(gè)港口之間無直接通航路線，則通過第三個(gè)港口轉(zhuǎn)運(yùn)。那么，各個(gè)港口之間最廉價(jià)的貨運(yùn)線路是什么？二、二、最短路徑問題最短路徑問題（一）最短路徑的含義（

2、一）最短路徑的含義 “時(shí)間時(shí)間”意義上的最短路徑意義上的最短路徑 例如，某家經(jīng)營(yíng)公司有一批貨物急需從一個(gè)城市運(yùn)往另一個(gè)城市，那么，在由公路、鐵路、河流航運(yùn)、航空運(yùn)輸?shù)?種運(yùn)輸方式和各個(gè)運(yùn)輸線路所構(gòu)成的交通網(wǎng)絡(luò)中，究竟選擇怎樣的運(yùn)輸路線最節(jié)省時(shí)間？ 以上3類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。 不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。 權(quán)這種權(quán)值既可以代表“純距離 ”，又可以代表“經(jīng)濟(jì)距離 ”，也可以代表“時(shí)間距離 ”。 （二）（二）最最短路徑的算法短路徑的算法標(biāo)號(hào)法標(biāo)號(hào)法 1959年E.W.Dijkstar 提出的標(biāo)號(hào)法是最短路徑問題最好的求解方法 。 標(biāo)號(hào)法優(yōu)點(diǎn)標(biāo)

3、號(hào)法優(yōu)點(diǎn) 不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長(zhǎng)度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長(zhǎng)度；同時(shí)適用于求解有向圖或無向圖上的最短路徑問題。.n標(biāo)號(hào)法的基本思想標(biāo)號(hào)法的基本思想 設(shè)G是一個(gè)賦權(quán)有向圖，即對(duì)于圖中的每一條邊，都賦予了一個(gè)權(quán)值。在圖G中指定兩個(gè)頂點(diǎn)，確定為起點(diǎn)和終點(diǎn)，不妨設(shè)v1為起點(diǎn)，vk為終點(diǎn)。 首先從v1開始，給每一個(gè)頂點(diǎn)標(biāo)一個(gè)數(shù)，稱為標(biāo) 號(hào)。這些標(biāo)號(hào)，又進(jìn)一步區(qū)分為T標(biāo)號(hào)和P標(biāo)號(hào)兩種類型。其中，每一個(gè)頂點(diǎn)的T標(biāo)號(hào)表示從起點(diǎn)v1到該點(diǎn)的最短路徑長(zhǎng)度的上界，這種標(biāo)號(hào)為臨時(shí)標(biāo)號(hào)；P標(biāo)號(hào)表示從v1到該點(diǎn)的最短路長(zhǎng)度，這種標(biāo)號(hào)為固定標(biāo)號(hào)。 在最短路徑計(jì)算過程中，對(duì)于已經(jīng)得到

4、P標(biāo)號(hào)的頂點(diǎn)，不再改變其標(biāo)號(hào)；對(duì)于凡是沒有標(biāo)上P標(biāo)號(hào)的頂點(diǎn)，先給它一個(gè)T標(biāo)號(hào)；算法的每一步就是把頂點(diǎn)的T標(biāo)號(hào)逐步修改，將其變?yōu)镻標(biāo)號(hào)。 那么，最多經(jīng)過k-1步，就可以求得到從起點(diǎn)v1到每一個(gè)頂點(diǎn)的最短路徑及其長(zhǎng)度。n標(biāo)號(hào)法具體計(jì)算步驟標(biāo)號(hào)法具體計(jì)算步驟 如果剛剛得到P標(biāo)號(hào)的點(diǎn)是vi，那么，對(duì)于所有這樣的點(diǎn) 將其T標(biāo)號(hào)修改為：minT(vj)，P(vi)+wij。 若G中沒有T標(biāo)號(hào)，則停止。否則，把點(diǎn) 的T標(biāo)號(hào)修改為P標(biāo)號(hào)，然后再轉(zhuǎn)入。 其中， 滿足 開始，先給v1標(biāo)上P標(biāo)號(hào)P(v1) 0，其余各點(diǎn)標(biāo)上T標(biāo)號(hào)T(vj)+（j1）。 )(min)(0jjvTvT0jv0jv標(biāo)號(hào)的標(biāo)號(hào)是而且TvEv

5、vvjjij,標(biāo)號(hào)法例子標(biāo)號(hào)法例子最小生成樹uvwxyzst節(jié)點(diǎn)前溯節(jié)點(diǎn)uuvuwuyvxwswtxzystartidendidtmpidmarked(N)= false標(biāo)記數(shù)組stpdis(N)= OO最短距離preid(N)= -1前溯節(jié)點(diǎn)號(hào)crtid = startid設(shè)置當(dāng)前節(jié)點(diǎn)while crtid endid搜索直到終點(diǎn) for linkid = 1 to L搜索所有鏈接 if link.o = crtid then如果與當(dāng)前節(jié)點(diǎn)鄰接 tmpid = link.d并且另一端點(diǎn)的最短距離較大 if stpdis(crtid) + link.dis stpdis(tmpid) then stpdis(tmpid) = stpdis(crtid) + link.dis preid(tmpid) = crtid修改另一端點(diǎn)的最短距離和前溯節(jié)點(diǎn) end if end if next crtid = endid設(shè)置下一個(gè)當(dāng)前節(jié)點(diǎn) for nodeid = 1 to N搜索所有節(jié)點(diǎn) if marked(nodeid) = false 找到未標(biāo)記的有更小距離的節(jié)點(diǎn) and stpdis(nodeid) st