地理信息系統(tǒng)課程GIS網(wǎng)絡(luò)分析省公開(kāi)課金獎(jiǎng)全國(guó)賽課一等獎(jiǎng)微課獲獎(jiǎng)?wù)n件

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

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

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

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

問(wèn)題引入：2/251網(wǎng)絡(luò)分析基礎(chǔ)

網(wǎng)絡(luò)：是由點(diǎn)、線(xiàn)組成系統(tǒng)，通慣用來(lái)描述某種資源或物質(zhì)在空間中運(yùn)動(dòng)?？杀硎緸橛删W(wǎng)絡(luò)結(jié)點(diǎn)集V、網(wǎng)絡(luò)邊集E和事件點(diǎn)集P組成集合，即有D={V，E，P}

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

網(wǎng)絡(luò)分析基本研究對(duì)象：線(xiàn)狀目標(biāo)和點(diǎn)狀目標(biāo)。

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

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

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

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

6/25

2)道路是一雙行道，且正向阻強(qiáng)為40km/s，負(fù)向阻強(qiáng)為35km/s，詳細(xì)表示為鏈弧號(hào)起結(jié)點(diǎn)終止點(diǎn)正方向阻強(qiáng)（km/s）反方向阻強(qiáng)（km/s）p1p7174035

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

若每個(gè)需求點(diǎn)都分配給與之最近一個(gè)供給點(diǎn)，則

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

二、資源分配目標(biāo)方程若資源分配要求供給點(diǎn)與需求點(diǎn)之間總加權(quán)距離為最小，則對(duì)應(yīng)目標(biāo)方程是

若要求距離最小時(shí)，目標(biāo)方程是

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