第五章地理信息系統(tǒng)-路徑遍歷與最短路徑

物流信息管理大連海事大學(xué)第五章地理信息系統(tǒng)路徑遍歷與最短路徑一、路徑遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷二、最短路徑數(shù)學(xué)模型標(biāo)號(hào)法程序流程一、路徑遍歷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)都被訪問完為止。SubDeepthFirstSearch(vasInteger) ‘從v出發(fā)深度優(yōu)先遍歷圖g

Callvisit(v)

visited(v)

=1

w=FIRSTADJ(v)‘w為v的鄰接點(diǎn)

Dowhilevisited(w)=0‘當(dāng)鄰接點(diǎn)未訪問

CallDeepthFirstSearch(w)

w=NEXTADJ(v)‘找下一鄰接點(diǎn)

LoopEndSub深度優(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)都被訪問完為止。Callvisit(s)visited(s)=1SubBreadthFirstSearch(vasInteger) ‘從v出發(fā)廣度優(yōu)先遍歷圖g

Fori=1toNUMOFADJ(v)

w(i)=NEXTADJ(v)‘找下一鄰接點(diǎn)

Ifvisited(w(i))=0Then

Callvisit(w(i))

visited(w(i))=1

EndIf

Next Forj=1toNUMOFITEMS(w) CallBreadthFirstSearch(w(j)) NextEndSub廣度優(yōu)先遍歷算法描述二、最短路徑問題（一）最短路徑的含義“純距離”意義上的最短路徑例如，需要運(yùn)送一批物資從一個(gè)城市到另一個(gè)城市，選擇什么樣的運(yùn)輸路線距離最短？“經(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í)間”意義上的最短路徑

例如，某家經(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類問題，都可以抽象為同一類問題，即賦權(quán)圖上的最短路徑問題。

不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。權(quán)——這種權(quán)值既可以代表“純距離

”，又可以代表“經(jīng)濟(jì)距離

”，也可以代表“時(shí)間距離

”。

（二）最短路徑的算法標(biāo)號(hào)法1959年E.W.Dijkstar提出的標(biāo)號(hào)法是最短路徑問題最好的求解方法。

標(biāo)號(hào)法優(yōu)點(diǎn)

不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長度；同時(shí)適用于求解有向圖或無向圖上的最短路徑問題。.標(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)的最短路徑長度的上界，這種標(biāo)號(hào)為臨時(shí)標(biāo)號(hào)；P標(biāo)號(hào)表示從v1到該點(diǎn)的最短路長度，這種標(biāo)號(hào)為固定標(biāo)號(hào)。在最短路徑計(jì)算過程中，對(duì)于已經(jīng)得到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)的最短路徑及其長度。標(biāo)號(hào)法具體計(jì)算步驟

①如果剛剛得到P標(biāo)號(hào)的點(diǎn)是vi，那么，對(duì)于所有這樣的點(diǎn)將其T標(biāo)號(hào)修改為：min[T(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)＝+∞（j≠1）。15標(biāo)號(hào)法算法描述1Initialization:

2S={u}3forallnodesv4ifvadjacenttouthen5D(v)=c(u,v)6elseD(v)=∞

78Loop

9findwnotinSwiththesmallestD(w)10addwtoS11updateD(v)forallvadjacenttowandnotinS:12D(v)=min