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

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

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

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

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

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