地理信息系統(tǒng)課程GIS網(wǎng)絡分析省公開課金獎全國賽課一等獎微課獲獎課件

①將一批貨物從甲地運到乙地，能夠經(jīng)過多條路線，怎樣求取運輸費用最低路線——最正確路徑②

當?shù)叵旅簹夤艿栏难b時，若關(guān)閉某個閥門，需要確定受影響用戶——連通問題③某城市擬建立一消防站，怎樣確定10分鐘之內(nèi)能到達全部街道——資源分配④常樂村15號在那個地方——地址匹配

問題引入：1/25什么是網(wǎng)絡分析?

在GIS中，網(wǎng)絡分析是指依據(jù)網(wǎng)絡拓撲關(guān)系（結(jié)點與弧段拓撲、弧段連通性），經(jīng)過考查網(wǎng)絡元素空間及屬性數(shù)據(jù)，以數(shù)學理論模型為基礎，對網(wǎng)絡性能特征進行多方面研究一個分析計算。

問題引入：2/251網(wǎng)絡分析基礎

網(wǎng)絡：是由點、線組成系統(tǒng)，通慣用來描述某種資源或物質(zhì)在空間中運動。可表示為由網(wǎng)絡結(jié)點集V、網(wǎng)絡邊集E和事件點集P組成集合，即有D={V，E，P}

網(wǎng)絡分析：是對地理網(wǎng)絡和城市基礎設施網(wǎng)絡等網(wǎng)狀事物以及它們相互關(guān)系和內(nèi)在聯(lián)絡進行地理分析和模型化。

網(wǎng)絡分析基本研究對象：線狀目標和點狀目標。

網(wǎng)絡分析主要研究內(nèi)容：最短路徑分析、資源分配、連通分析等。3/25由一系列相互連通點和線組成，用來描述地理要素（資源）流動情況。4/251網(wǎng)絡分析基礎

網(wǎng)絡基本元素包含網(wǎng)絡中心、邊、結(jié)點、站、拐角和障礙等，以下列圖。

5/251網(wǎng)絡分析基礎1、資源：是網(wǎng)絡中傳輸物質(zhì)、能量、信息等。資源經(jīng)過在網(wǎng)絡中流動實現(xiàn)傳輸和分配。資源屬性與網(wǎng)絡通行規(guī)則聯(lián)合作用影響資源在網(wǎng)絡中流動情況。

2、鏈：圖或網(wǎng)絡中線狀要素，表現(xiàn)是網(wǎng)絡中地理實體和現(xiàn)象，通慣用中心線代表地理實體和現(xiàn)象本身。鏈有圖形信息和屬性信息。屬性信息包含妨礙強度、資源需求量、資源流動約束條件。

6/25

2)道路是一雙行道，且正向阻強為40km/s，負向阻強為35km/s，詳細表示為鏈弧號起結(jié)點終止點正方向阻強（km/s）反方向阻強（km/s）p1p7174035

3）道路是一單行道，且阻強為20km/s，詳細表示為：鏈弧號起結(jié)點終止點正方向阻強（km/s）反方向阻強（km/s）P6p86820-1(表不通)7/253、結(jié)點：網(wǎng)絡鏈兩個端點

4、站點：網(wǎng)絡中裝載或卸下資源結(jié)點位置。站屬性主要有兩種：資源需求量和妨礙強度。

5、中心：網(wǎng)絡中含有一定容量，能夠從鏈上獲取資源結(jié)點所在地。中心屬性有兩種：一是中心資源容量，一是中心妨礙強度。

6、障礙：對資源傳輸起阻斷作用結(jié)點或鏈，它妨礙了資源在與其相連鏈間流動，代表了網(wǎng)絡中元素不可通行狀態(tài)。（障礙連續(xù)）

8/257、拐角：網(wǎng)絡結(jié)點處，全部資源流動可能轉(zhuǎn)向。其屬性主要是拐角妨礙強度。

9/258、權(quán)值：用于存放經(jīng)過一條鏈或結(jié)點時所需要成本。10/252最短路徑分析

路徑分析：是在指定網(wǎng)絡結(jié)點間找出最正確路徑。最短路徑：在網(wǎng)絡兩節(jié)點之間找到一條抗阻最小路徑。路徑分析關(guān)鍵：對路徑求解，即怎樣求出滿足條件最優(yōu)路徑。

11/25Dijkstra算法Dijkstra算法是最經(jīng)典按路徑長度遞增次序產(chǎn)生最短路徑方法。

Dijkstra算法基本思想：標識源點到已得到點最短路徑，再尋找到下一個點最短路徑（由近及遠尋找起點到其它節(jié)點最正確路徑，直至抵達目標節(jié)點）。適合用于全部弧權(quán)為非負最短路徑算法。

Dijkstra算法詳細步驟：（1）初始化：設置源s點：ds=0,ps=空集;其它點：ds=∞,ps=?;將起源點s標號，記k=s，其它點還未處理；（2）距離計算。計算從全部標識點k到其它直接連接未標識點j距離lij，并令dj=min{dj，dk+lkj}

12/25（3）選取下一點。從上述結(jié)點集中，選取dj最小所對應點為最短路徑中下一連接點i，并作標識。（4）找到點i前一點。從已標識點中找到連接到點i前一點j*,并令i=j*作為前一點。（5）標識點i。假如全部點已標識，則算法完全退出，不然，記k=i，轉(zhuǎn)到（2）再繼續(xù)，直到全部點都已標識。

13/25以下列圖，設A為源點，求A到其它各頂點（B、C、D、E、F）最短路徑。線上所標注為相鄰線段之間距離，即權(quán)值。（注：此圖為隨意所畫，其相鄰頂點間距離與圖中目視長度不能一一對等）14/2515/2516/253資源分配一、基本概念：

資源分配：在網(wǎng)絡中依據(jù)應用需求將資源分配到所需地點。

資源分配研究問題包含：（1）需求點和供給點都確定情況下，現(xiàn)在資源分配，如物資配送；（2）新增供給點，如新變電所選址；（3）新增需求點，如新建居民地。

資源分配關(guān)鍵：資源定位及分配。資源定位：指已知需求，確定在哪里布設最適當供給點，即尋找最正確供給點。資源分配：就是確定需求源分別受哪個供給點服務。17/253資源分配

資源分配數(shù)學模型：

設有n個需求點Pi（xi,yi），bi是每個需求點需求量（i=1,2,…,n）,m個供給點Qj（uj,vj）（j=1,2,…,m）。tij和dij分別是供給點Qj對需求點Pi提供供給量和兩點間距離。若全部需求點都受到供給點服務，則

若每個需求點都分配給與之最近一個供給點，則

需求點Pi需求是否由供給點Qj供給可用矩陣（Xij）表示，且18/253資源分配

二、資源分配目標方程若資源分配要求供給點與需求點之間總加權(quán)距離為最小，則對應目標方程是

若要求距離最小時，目標方程是

若要求全部需求點在一給定服務半徑s內(nèi)，則目標方程是其中19/254、連通性分析----最小生成樹（1）概念連通圖：在一個圖中，任意兩個節(jié)點之間都存在一條路。樹：若一個連通圖中不存在任何回路，則稱為樹。生成樹權(quán)數(shù)：生成樹中各邊權(quán)數(shù)之和。最小生成樹：圖極小連通子圖。（2）應用：通信線路、快遞5620/25①樹中邊數(shù)比節(jié)點數(shù)少1②樹中兩節(jié)點之間最多有一條邊③樹中任意去掉一條邊，就變成不連通圖④樹中添加一條邊就會組成回路普通來說，一個圖生成樹可能不止一個樹性質(zhì)21/25(4)算法（Kruskal，克羅斯克爾算法，也叫“避圈”法）1）先把圖中各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小一條邊為最小生成樹中邊。2）在剩下邊中，按次序取下一條邊。若該邊與最小生成樹中已經(jīng)有邊，組成回路，則舍去該邊，不然選中生成樹。3）重復2），直到有M-1條邊被選進生成樹中，這M-1條邊就組成最小生成樹3.1.2連通性分析----最小生成樹22/25詳細步驟克羅斯克爾算法23/25(4)算法（Kruskal，克羅斯克爾算法，也叫“避圈”法）1）先把圖中各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小一條邊