資源描述：
《FD算法求解最短路徑》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、萬方數(shù)據(jù)第30卷第6期2003年11月華北電力大學學報JournalofNorthChi帥E】ectricPowerUⅡiversityV0130，No6Nov．2003文章編號：1007-269l(2003)06·0075-03F．D算法求解最短路徑程曉榮1，劉斌1’2，陸旭112，牛習現(xiàn)1(1華北電力大學計算機科學與工程系，河北保定07l003；2．盤錦電業(yè)局通信所，遼寧盤錦124叭O)摘要：分析Floyd算法與Dqks觚算法的基本思想，將二者結合起來，給出一種新的求最短路徑的優(yōu)化算法——F．D算法，用F．D算法求解基于GIs的電力通信線路最短路徑，并
2、在約束條件下對所求最短路徑進行修正，驗證了F．D算法的先進性和高效性，優(yōu)化了通信線路的拓撲，實際應用意義重大。關鍵詞：F．D算法；最短路徑；電力通信線路中固分類號：TN913文獻標識碼：AShortestpathsolutionbasedonF—D(Floyd-Dijkstra)algorithmCHENGXiao-ron91，LIUBinl2，LUXul2，NlUXi-xianl(1．Departmentofcompu時sc螂ce如dEn西neering，No咄chinaElec嘶cP0werUnivefs峨Baomn9071003chma；2corn士
3、IIunicationDepar嘶emofElectdcalPowerBuIc跏，Pa坷in124010，china)Abs打act：ThebasicconceptsofF10yd卸dD埒ks燈aa培onmmsare鋤alyzed咒spectivel弘An刪0ptiInizaIi叩algo血hm—F-Dalgo蛐mispfopo∞d．F-Dalg刪也nlcalcuJafes恤sh嘣eslp毗hOfGIS-b撇dpowercommllnicatjonl訊ewIIichisthenMvisedbyres柏i日edcondnion．Thetopologysm蚓咂
4、eofpower∞m日叫nica越Onl婦b叩毗ed．K鯽word自：F—Da190fimtll：曲om8tp蛐；paw盯comm哪ic拜tion抽。引言由于電力系統(tǒng)線路繁多，對線路的設計、架設、在線使用、故障、空閑狀態(tài)、各用戶信息的管理，以及通信過程中所經(jīng)由的各條路徑信息的管理顯得異常重要。如何找到兩個設備之間一條最短路徑，最高效率地利用線路資源是管理系統(tǒng)中要解決的一個重要問題。針對線路中各種通信連接設備和交接箱端用戶的連接情況，把其等價為一個無向圖中部分頂點問的最短路徑問題，尋找其最短路徑，為線路的架設安排合理的路線和行程，可大大縮短架線距離和節(jié)省開支
5、。目前通常使用Floyd或Di-Jks缸算法計算最短路徑，由于在實際應用中，存在一些條件約束，必須使用·種綜合方法來實現(xiàn)最優(yōu)設計。本文使用一種優(yōu)化的F—D算法，實現(xiàn)了基于GIS(Geo伊aphicIⅡformationSystem)的電力通信線路管理中線路拓撲和最短路徑的查找。l優(yōu)化的F-D算法1．1F_D算法F—D算法的思想是，先用Floyd算法計算多對頂點之間的最短路徑，如果有某種約束條件使路徑中少數(shù)頂點之間的鄰接關系發(fā)生變化，確定這些被改變的頂點對，需利用Diiks仃a算法計算這些頂點對之間的最短路徑，加上其余部分路徑就得到該圖中各對頂點之間的新的最
6、短路徑，并在約束條件發(fā)生作用的情況下求出各項點間最終的最短路徑。收稿日期：2002．12．20作者簡介：程曉榮(1963一)，女，華北電力大學計算機科學與l程系副教授萬方數(shù)據(jù)76華北電力大學學報2003年1．1．1Floyd算法求最短路徑端子容量已滿，必須重新計算，繞過該頂點，取消(1)設圖G由HG)，瓜G)組成，HG)為頂點集構成路徑的幾條邊。合，聯(lián)G)為邊集合，權矩陣一=叫J(3)線路用戶分布密度的考慮，頂點增加或修(2)若從K到K最短路徑不經(jīng)過K點，則改連通圖G。鐘切刊”“阿](3)若從形到”最短路徑經(jīng)過酢點，則∥[f√卜min(一忙”[f棚一¨”[
7、‘明斗爿“一’[幻])經(jīng)H次比較后，4“k[n}：]就是圖中每一對頂點之間的最短路徑。1．1．2對得到的最短路徑檢驗實際問題中確定檢測標準，檢驗得到的一?是否滿足實際要求，設從m點到口點最短路徑，依次對邊耳G)集合中的‰。P。，?，‰備條邊驗證，判路徑中每條邊是否滿足實際條件，滿足則繼續(xù)，否則用Dijks仃a算法進行修正。1．1．3用Di-kstra算法修正路徑(1)若從m到g的某條邊g(f．，)，不滿足實際需要，則甜‘o。。(2)令頂點f標號為o，其他頂點標號為一，稱頂點溈定標頂點，其他頂點為未定標頂點。(3)對所有路徑中未給出定標的頂點放入喋合，蝶合表
8、示從Ⅲ出發(fā)的最短路徑終點集合，對u中未定標點用暫時標號表示，暫時標
