資源描述：
《最佳路徑問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。
1、路徑分析是GIS中最基本的功能，其核心是對最佳路徑的求解。從網(wǎng)絡模型的角度看，最佳路徑的求解是在指定網(wǎng)絡的兩個結(jié)點之間找一條阻礙強度最小的路徑。另一種路徑分析功能是求解最佳游歷方案，又分為弧段最佳游歷方案求解和結(jié)點最佳游歷方案求解兩種。o最佳路徑分析也稱最優(yōu)路徑分析，以最短路徑分析為主。這里“最佳”包含很多含義，不僅指一般地理意義上的距離最短，還可以是成本最少、耗費時間最短、資源流量（容量）最大、線路利用率最高等標準。很多網(wǎng)絡相關(guān)問題，如最可靠路徑問題、最大容量路徑問題、易達性評價問題和各種路徑分配問題均可納入最佳路徑問題的
2、范疇之中。無論判斷標準和實際問題中的約束條件如何變化，其核心實現(xiàn)方法都是最短路徑算法。o最短路徑問題從算法研究的角度考慮最短路徑問題通?？蓺w納為兩大類：一類是所有點對之間的最短路徑，另一類是單源點間的最短路徑問題。網(wǎng)絡分析：最佳路徑問題o“最佳路徑”中的“佳”包含很多含義，它不僅可以指一般地理意義上的距離最短，還可以是時間最短、費用最少、線路利用率最高等標準。但是無論引申為何種判斷標準，其核心實現(xiàn)方法都是最短路徑算法。o最短路徑的數(shù)據(jù)基礎是網(wǎng)絡，組成網(wǎng)絡的每一條弧段都有一個相應的權(quán)值，用來表示此弧段所連接的兩結(jié)點間阻抗值。在
3、數(shù)學模型中，這些權(quán)值可以為正值，也可以為負值。由于在GIS中一般的最短路徑問題都不涉及負回路的情況，因此以下所有的討論中假定弧段的權(quán)值都為非負值。o若一條弧段(vi，vj)的權(quán)值表示結(jié)點vi和vj間的長度，那么道路u＝{e1，e2，…，ek}的長度即為u上所有邊的長度之和。所謂最短路徑問題就是在vi和vj之間的所有路徑中，尋求長度最小的路徑，這樣的路徑稱為從vi到vj的最短路徑。o最短路徑問題的算法一般分為兩大類：一類是所有點對間的最短路徑，另一類則是單源點間的最短路徑問題，其各自的求解方法是不同的。5.3.2最佳路徑分析最
4、佳路徑分析也稱最優(yōu)路徑分析，以最短路徑分析為主，一直是計算機科學、運籌學、交通工程學、地理信息科學等學科的研究熱點。這里“最佳”包含很多含義，不僅指一般地理意義上的距離最短，還可以是成本最少、耗費時間最短、資源流量（容量）最大、線路利用率最高等標準。很多網(wǎng)絡相關(guān)問題，如最可靠路徑問題、最大容量路徑問題、易達性評價問題和各種路徑分配問題均可納入最佳路徑問題的范疇之中。無論判斷標準和實際問題中的約束條件如何變化，其核心實現(xiàn)方法都是最短路徑算法。地理網(wǎng)絡因地理元素屬性的不同而表現(xiàn)為同形不同性的網(wǎng)絡形式，為了進行網(wǎng)絡路徑分析，需要將
5、網(wǎng)絡轉(zhuǎn)換成加權(quán)有向圖，即給網(wǎng)絡中的弧段賦以權(quán)值，權(quán)值要根據(jù)約束條件而確定。若一條弧段的權(quán)表示起始結(jié)點和終止結(jié)點之間的長度，那么任意兩結(jié)點間的一條路徑的長度即為這條路上所有邊的長度之和。最短路徑問題就是在兩結(jié)點之間的所有路徑中，尋求長度最小的路徑，這樣的路徑稱為兩結(jié)點間的最短路徑。最短路徑問題的表達是比較簡單的，從算法研究的角度考慮最短路徑問題通?？蓺w納為兩大類：一類是所有點對之間的最短路徑，另一類是單源點間的最短路徑問題。1.最短路徑算法（1）Dijkstra算法基本思想戴克斯徒拉（Dijkstra）算法是E.W.Dijks
6、tra于1959年提出的一種按路徑長度遞增的次序產(chǎn)生最短路徑的算法，此算法被認為是解決單源點間最短路徑問題比較經(jīng)典而且有效的算法。其基本思路是：假設每個點都有一對標號（dj,pj），其中dj是從起源點s到點j的最短路徑的長度（從頂點到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法也稱標號法或染色法，其基本過程如下：V2V0V1100V3V5V46020301010505圖5.37帶權(quán)的有向圖①初始化。起源點設置為ds=0，ps為空，并標記起源
7、點s，記k=s，其他所有點設為未標記點。②檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置dj=min［dj,dk+lkj］其中，lkj為從點k到j的直接連接距離。③選取下一個點。從所有未標記的結(jié)點中，選取dj中最小的一個idi=min［dj,所有未標記的點j］點i就被選為最短路徑中的一點，并設為已標記的點。④找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點，記為i=j*⑤標記點i。如果所有點已標記，則算法完全推出，否則，記k=i，重復步驟②③④。圖5.37為某一帶權(quán)有向圖，若對其施行Di
8、jkstra算法，則所得從V0到其余各頂點的最短路徑以及運算過程中距離的變化情況如表5.5所示。表5.5Dijkstra算法示例及計算過程終點從源點V0到各終點的距離值和最短路徑的求解過程i=1i=2i=3i=4i=5V1∞∞∞∞∞V210（V0,V2）V3∞60（V0,V2,V3）50（
