1、物流信息管理大連海事大學(xué)第五章 地理信息系統(tǒng)路徑遍歷與最短路徑一、路徑遍歷1. 深度優(yōu)先遍歷2. 廣度優(yōu)先遍歷二、最短路徑1. 數(shù)學(xué)模型2. 標(biāo)號法3. 程序流程一、路徑遍歷1.深度優(yōu)先遍歷(1)首先訪問頂點(diǎn)i，并將其訪問標(biāo)記置為訪問過，即visited(i) =1；(2) 然后搜索與頂點(diǎn)i有邊相連的下一個(gè)頂點(diǎn)j，若j未被訪問過，則訪問它，并將j的訪問標(biāo)記置為訪問過，visited(j)=1，然后從j開始重復(fù)此過程，若j已訪問，再看與i有邊相連的其它頂點(diǎn)；(3) 若與i有邊相連的頂點(diǎn)都被訪問過，則退回到前一個(gè)訪問頂點(diǎn)并重復(fù)剛才過程，直到圖中所有頂點(diǎn)都被訪問完為止。Sub Sub DeepthF

2、irstSearchDeepthFirstSearch(v as Integer)(v as Integer) 從從v v出發(fā)深度優(yōu)先遍歷圖出發(fā)深度優(yōu)先遍歷圖g gCall visit(v) Call visit(v) visited(vvisited(v) ) = = 1 1w=FIRSTADJ(v) ww=FIRSTADJ(v) w為為v v的鄰接點(diǎn)的鄰接點(diǎn) Do Do while while visited(w)=0 visited(w)=0 當(dāng)當(dāng)鄰接鄰接點(diǎn)未訪問點(diǎn)未訪問 Call Call DeepthFirstSearchDeepthFirstSearch(w)(w) w=NEXTA

3、DJ(v) w=NEXTADJ(v) 找找下一鄰接點(diǎn)下一鄰接點(diǎn) LoopLoopEnd SubEnd Sub深度優(yōu)先遍歷算法描述2.廣度優(yōu)先遍歷廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G 中任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是：(1) 首先訪問頂點(diǎn)i，并將其訪問標(biāo)志置為已被訪問，即visited(i)=1；(2) 接著依次訪問與頂點(diǎn)i有邊相連的所有頂點(diǎn)W1，W2，Wt；(3) 然后再按順序訪問與W1，W2，Wt有邊相連又未曾訪問過的頂點(diǎn)；依此類推，直到圖中所有頂點(diǎn)都被訪問完為止 。 Call visit(s) Call visit(s) visit

4、ed(s) visited(s) = = 1 1Sub Sub BreadthFirstSearchBreadthFirstSearch(v as Integer)(v as Integer) 從從v v出發(fā)廣度優(yōu)先出發(fā)廣度優(yōu)先遍歷圖遍歷圖g gFor For i i=1 to NUMOFADJ(v)=1 to NUMOFADJ(v)w(w(i i) = NEXTADJ(v) = NEXTADJ(v) ) 找下一鄰接找下一鄰接點(diǎn)點(diǎn)If visited( w(If visited( w(i i) ) = 0 Then) ) = 0 ThenCall Call visitvisit( w( w(i

5、 i) ) ) ) visited( w(visited( w(i i) ) ) ) = = 1 1End IfEnd IfNextNextFor For j=1 j=1 to to NUMOFITEMS(w)NUMOFITEMS(w)Call Call BreadthFirstSearchBreadthFirstSearch( w(j) )( w(j) )NextNextEnd SubEnd Sub廣度優(yōu)先遍歷算法描述二、二、最短路徑問題最短路徑問題（一）最短路徑的含義（一）最短路徑的含義“純距離純距離”意義上的最短路徑意義上的最短路徑 例如，需要運(yùn)送一批物資從一個(gè)城市到另一個(gè)城市，選擇什么

6、樣的運(yùn)輸路線距離最短？“經(jīng)濟(jì)距離經(jīng)濟(jì)距離”意義上的最短路徑意義上的最短路徑 例如，某公司在10大港口C1，C2，C10設(shè)有貨棧，從Ci到Cj之間的直接航運(yùn)價(jià)格，是由市場動(dòng)態(tài)決定的。如果兩個(gè)港口之間無直接通航路線，則通過第三個(gè)港口轉(zhuǎn)運(yùn)。那么，各個(gè)港口之間最廉價(jià)的貨運(yùn)線路是什么？二、二、最短路徑問題最短路徑問題（一）最短路徑的含義（一）最短路徑的含義 “時(shí)間時(shí)間”意義上的最短路徑意義上的最短路徑 例如，某家經(jī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類問題，都可以抽

7、象為同一類問題，即賦權(quán)圖上的最短路徑問題。 不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。 權(quán)這種權(quán)值既可以代表“純距離 ”，又可以代表“經(jīng)濟(jì)距離 ”，也可以代表“時(shí)間距離 ”。 （二）（二）最短路徑的算法最短路徑的算法標(biāo)號法標(biāo)號法 1959年E.W.Dijkstar 提出的標(biāo)號法是最短路徑問題最好的求解方法 。 標(biāo)號法優(yōu)點(diǎn)標(biāo)號法優(yōu)點(diǎn) 不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長度；同時(shí)適用于求解有向圖或無向圖上的最短路徑問題。.n標(biāo)號法的基本思想標(biāo)號法的基本思想 設(shè)G是一個(gè)賦權(quán)有向圖，即對于圖中的每一條邊，都賦予了一個(gè)權(quán)值。在圖G中指定兩個(gè)頂

8、點(diǎn)，確定為起點(diǎn)和終點(diǎn)，不妨設(shè)v1為起點(diǎn)，vk為終點(diǎn)。 首先從v1開始，給每一個(gè)頂點(diǎn)標(biāo)一個(gè)數(shù)，稱為標(biāo) 號。這些標(biāo)號，又進(jìn)一步區(qū)分為T標(biāo)號和P標(biāo)號兩種類型。其中，每一個(gè)頂點(diǎn)的T標(biāo)號表示從起點(diǎn)v1到該點(diǎn)的最短路徑長度的上界，這種標(biāo)號為臨時(shí)標(biāo)號；P標(biāo)號表示從v1到該點(diǎn)的最短路長度，這種標(biāo)號為固定標(biāo)號。 在最短路徑計(jì)算過程中，對于已經(jīng)得到P標(biāo)號的頂點(diǎn)，不再改變其標(biāo)號；對于凡是沒有標(biāo)上P標(biāo)號的頂點(diǎn)，先給它一個(gè)T標(biāo)號；算法的每一步就是把頂點(diǎn)的T標(biāo)號逐步修改，將其變?yōu)镻標(biāo)號。 那么，最多經(jīng)過k-1步，就可以求得到從起點(diǎn)v1到每一個(gè)頂點(diǎn)的最短路徑及其長度。n標(biāo)號法具體計(jì)算步驟標(biāo)號法具體計(jì)算步驟 如果剛剛得到P標(biāo)

9、號的點(diǎn)是vi，那么，對于所有這樣的點(diǎn) 將其T標(biāo)號修改為：minT(vj)，P(vi)+wij。 若G中沒有T標(biāo)號，則停止。否則，把點(diǎn) 的T標(biāo)號修改為P標(biāo)號，然后再轉(zhuǎn)入。 其中， 滿足 開始，先給v1標(biāo)上P標(biāo)號P(v1) 0，其余各點(diǎn)標(biāo)上T標(biāo)號T(vj)+（j1）。 )(min)(0jjvTvT0jv0jv標(biāo)號的標(biāo)號是而且TvEvvvjjij,15標(biāo)號法算法描述1 Initialization: 2 S = u 3 for all nodes v 4 if v adjacent to u then5 D(v) = c(u,v) 6 else D(v) = 7 8 Loop 9 find w not in S with the smallest D(w)10 add w to S 11 update D(v) for all