第十三講空間分析與查詢四

1、第十三講 空間分析與查詢（四）中山大學 遙感與地理信息工程系網絡分析 網絡數據結構的基本組成部分和屬性 1、鏈（link） 網絡中流動的管線如街道、河流、水管，其狀態(tài)屬性包括阻力和需求。 2、結點（node） 網絡中鏈的結點，如港口、車站等，其狀態(tài)屬性包括阻力和需求等。 結點中的特殊類型障礙（barrier），禁止網絡上流動的點。拐點（turn），出現在網絡中的分割點上，其狀態(tài)有屬性和阻力，如拐彎的時間和限制（如在8點到18點不允許左拐）。中心（center），是接受或分配資源的位置，如水庫、商業(yè)中心，電站等，其狀態(tài)包括資源容量（如總量），阻力限額（中心到鏈的最大距離或時間）。站點（stop）

2、，在路徑選擇中資源增減的結點，如庫房、車站等，其狀態(tài)屬性有資源需求，如產品數量。 路徑分析靜態(tài)求最佳路徑：在給定每條鏈上的屬性后，求最佳路徑。n條最佳路徑分析：確定起或終點，求代價最小的n條路徑，因為在實際中最佳路徑的選擇只是理想情況，由于種種要素而要選擇近似最佳路徑。最短路徑或最佳耗費路徑：確定起點終點和要經過的中間點、中間連線，求最短路徑或最佳耗費路徑。動態(tài)最佳路徑分析：實際網絡中權值是隨權值關系式變化的，可能還會臨時出現一些障礙點，需要動態(tài)的計算最佳路徑。 int findmin(int *array, int bound)int min=1000;for(int i=0;ibound;

3、i+) if(arrayi=min) min=arrayi;return min; int array7=789,33,7898,7565,76,22,88;int result=findmin(array,7);assert(result = =22)最佳路徑求解 最佳路徑求解有多種不同的方法，其中dijkstra算法適合于求解某個起點（源點）到網絡中的其它各個結點的最佳路徑。dijkstra算法（1）1、引進一個輔助向量d，它的每個分量di表示當前所找到的從起點 vm 到每個終點vi的最短路徑的長度。 假設用帶權的鄰接矩陣arcs來表示帶權有向圖，arcsij表示弧 上的權值。若 不連通，

4、則arcsij=。那么di的初值為：di=arcsmi viv此外，將已找到的從vm 出發(fā)的最短路徑的終點的集合記為s，它的初始狀態(tài)為空集。dijkstra算法（2）2、選擇 vj 使得dj=mindi | viv-svj就是當前求得的一條從vm出發(fā)的最短路徑的終點。其中j為這條最短路徑的終點，將其加入到終點集合s，令s=sjdijkstra算法（3）3、修改輔助向量d，即修改從vm出發(fā)到集合v-s上任一頂點vk可達的最短路徑長度。 顯然，若dj+arcsjkdk，則表明從vm出發(fā)，經過vj到達vk的路徑更短。因此，如果dj+arcsjkdk，則修改dk為dk=dj+arcsjkvmvjvka

5、rcsjk= 8dk= 15dj =5v-ssdijkstra算法（4）4、重復操作第二步、第三步共n-1次。由此求得從v到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。 例子v5v0v4v1v3v21006030101020505帶權有向圖鄰接矩陣例子(思路)acibi如圖所示，a為所求最短距離的起點，其他bi, ci 為終點。我們要求的是一系列最短距離。我們先假定這些最短距離互不相等。那么我們可以把這些最短距離按升序（從小到大）排列。我們把所有頂點分為兩類c和b.令a到bi這些頂點的最短距離不為無窮大。 a到ci這些頂點的最短距離為無窮大。這就說明a到ci中的點要么不通，要么通過bi中的

6、點與之連接。 例子(思路)acibi這樣，對于a到ci中任何一個點的最小距離，我們總可以在bi中找到一點，使得a到這一點的最小距離小于前一個距離。（因為：a到ci中的點要么不通，要么通過bi中的點與之連通。 ）因此，我們可以先不考慮ci中的點。例子(思路)于是，對于右圖，我們第一步只考慮下圖：v5v0v4v1v3v210060301010505v5v0v4v21003010bi=v2,v4,v5例子(思路)我們用mindist這個數組來保存由v0到其它頂點的最小距離，這些距離按升序排列。考慮右圖：第一步，通過比較，我們知道 mindistancev0v2=mindist0=10,（v0-v2)

7、這是我們求出的第一個最小距離。一旦我們得到v2，我們就可以知道：v5v0v4v21003010例子(思路)v0跟 v2直接連通到的點v3 之間的最小距離不再是無窮大，它應當是mindistancev0v2+disv2v3, 這樣我們應當把v3放入前面的集合bi中。（注意：有多少v2直接連通到的點都應當考慮進來。）v5v0v4v3v2100301050bi=v2,v4,v5,v3例子(思路)第二步，我們把與v2直接連通的點v3考慮進來。dis05=100; dis04=30;dis02=10; dis03=60;除10以外，30是最小的。 我們可以證明30是v0到其它頂點除10以外最小的。v5v

8、0v4v3v2100301050例子(思路)不可能存在這樣一個點vn，使得10mindistance0n30.原因如前所述。v5v0v4v3v2100301050vnbi例子(思路)這樣我們得到我們的第二個最小距離：mindistancev0v4=mindist1=30 ,(v0-v4)接下來，我們把v4與之直接連通的點考慮進來。v5v0v4v3v2100301050bi例子以v0為起點，計算它到其它各頂點的最短路徑，計算過程中最短路徑長度向量d的變化見d0-d4，計算出的各條最短路徑見表4-4。10030100d10030601d90502d603d4d例子例子起點終點最短路徑路徑長度v0v

9、1無 v2(v0,v2)10 v3(v0,v4,v3)50 v4(v0,v4)30 v5(v0,v4,v3,v5)60求最短路徑的方法中心選址問題 中心點選址問題中，最佳選址位置的判定標準，是使其所在的頂點與圖中其它頂點之間的最大距離達到最小。 這個選址問題實際上就是求網絡圖的中心點問題。這類選址問題適宜于醫(yī)院、消防站等服務設施的布局問題。 中心選址問題的圖論描述 設g=(v,e)是一個無向賦權連通圖，其中v=v1,v2,vn，e=e1,e2,en。連接兩個頂點的邊的權值代表該兩頂點之間的距離。對于每個頂點vi，它與各頂點之間的最短路徑長度為di1,di2,din。頂點vi的最大服務距離是這幾

10、個最短路徑長度中的最大值，記為e(vi0)。e(vi0)=max(di1,di2,din)那么，中心點選址問題，就是求圖g的中點vi0，使得該頂點的最大服務距離達到最小，即 e(vi0)=mine(vi)中心選址問題的實例例如，某縣要在其所轄的8個鄉(xiāng)鎮(zhèn)之一修建一個消防站，為8個鄉(xiāng)鎮(zhèn)服務，要求消防站至最遠鄉(xiāng)鎮(zhèn)的距離達到最小。假設該8個鄉(xiāng)鎮(zhèn)之間的交通網絡被抽象為圖4-10所示的無向賦權連通圖，權值為鄉(xiāng)鎮(zhèn)之間的距離。下面求解消防站應設在哪個鄉(xiāng)鎮(zhèn)，即哪個頂點？中心選址問題的實例v6v8v1v7v5v4v2v389363253757中心選址問題的實例首先，用dijkstra算法計算出每一個頂點vi至其它各頂點vj的最短路徑長度dij(i, j=1,2,6)，寫出距離矩陣： 中心選址問題的實例其次，求距離矩陣中每行的最大值，即各個頂點的最大服務距離，得e(v1)=14, e(v2)=15, e(v3)=20, e(v4)=12, e(v5)=15, e(v6)=17, e(v7)=12, e(v8)=20最后計算最大服務距離的最小值。顯然，e(v4) = e(v7) = min e(vi)。所以，消防站應建在v4或v7點所在的鄉(xiāng)鎮(zhèn)即可。中心選址問題的實例其次，求距離矩陣中每行的最大值，即各個頂點的最大服務距離，得e(v1)=14, e(v2)=15, e(v3)=20, e(v4)