FD算法求解最短路径

《FD算法求解最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第30卷第6期2003年11月华北电力大学学报JournalofNorthChi帅E】ectricPowerUⅡiversityV0130，No6Nov．2003文章编号：1007-269l(2003)06·0075-03F．D算法求解最短路径程晓荣1，刘斌1’2，陆旭112，牛习现1(1华北电力大学计算机科学与工程系，河北保定07l003；2．盘锦电业局通信所，辽宁盘锦124叭O)摘要：分析Floyd算法与Dqks觚算法的基本思想，将二者结合起来，给出一种新的求最短路径的优化算法——F．D算法，用F．D算法求解基于GIs的电力通信线路最短路径，并

2、在约束条件下对所求最短路径进行修正，验证了F．D算法的先进性和高效性，优化了通信线路的拓扑，实际应用意义重大。关键词：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抽。引言由于电力系统线路繁多，对线路的设计、架设、在线使用、故障、空闲状态、各用户信息的管理，以及通信过程中所经由的各条路径信息的管理显得异常重要。如何找到两个设备之间一条最短路径，最高效率地利用线路资源是管理系统中要解决的一个重要问题。针对线路中各种通信连接设备和交接箱端用户的连接情况，把其等价为一个无向图中部分顶点问的最短路径问题，寻找其最短路径，为线路的架设安排合理的路线和行程，可大大缩短架线距离和节省开支

5、。目前通常使用Floyd或Di-Jks缸算法计算最短路径，由于在实际应用中，存在一些条件约束，必须使用·种综合方法来实现最优设计。本文使用一种优化的F—D算法，实现了基于GIS(Geo伊aphicIⅡformationSystem)的电力通信线路管理中线路拓扑和最短路径的查找。l优化的F-D算法1．1F_D算法F—D算法的思想是，先用Floyd算法计算多对顶点之间的最短路径，如果有某种约束条件使路径中少数顶点之间的邻接关系发生变化，确定这些被改变的顶点对，需利用Diiks仃a算法计算这些顶点对之间的最短路径，加上其余部分路径就得到该图中各对顶点之间的新的最

6、短路径，并在约束条件发生作用的情况下求出各项点间最终的最短路径。收稿日期：2002．12．20作者简介：程晓荣(1963一)，女，华北电力大学计算机科学与l程系副教授万方数据76华北电力大学学报2003年1．1．1Floyd算法求最短路径端子容量已满，必须重新计算，绕过该顶点，取消(1)设图G由HG)，瓜G)组成，HG)为顶点集构成路径的几条边。合，联G)为边集合，权矩阵一=叫J(3)线路用户分布密度的考虑，顶点增加或修(2)若从K到K最短路径不经过K点，则改连通图G。钟切刊”“阿](3)若从形到”最短路径经过酢点，则∥[f√卜min(一忙”[f棚一¨”[

7、‘明斗爿“一’[幻])经H次比较后，4“k[n}：]就是图中每一对顶点之间的最短路径。1．1．2对得到的最短路径检验实际问题中确定检测标准，检验得到的一⋯是否满足实际要求，设从m点到口点最短路径，依次对边耳G)集合中的‰。P。，⋯，‰备条边验证，判路径中每条边是否满足实际条件，满足则继续，否则用Dijks仃a算法进行修正。1．1．3用Di-kstra算法修正路径(1)若从m到g的某条边g(f．，)，不满足实际需要，则甜‘o。。(2)令顶点f标号为o，其他顶点标号为一，称顶点沩定标顶点，其他顶点为未定标顶点。(3)对所有路径中未给出定标的顶点放入喋合，蝶合表

8、示从Ⅲ出发的最短路径终点集合，对u中未定标点用暂时标号表示，暂时标