快速排序的Dijkstra算法在配网抢修路径中的应用

《快速排序的Dijkstra算法在配网抢修路径中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、维普资讯http://www.cqvip.com第3l卷第2期四川电力技术Vo1．31。No．22OO8年o4月SichuanElectricPowerTechnologyApr．-2008快速排序的Dijkstra算法在配网抢修路径中的应用王倩，吕林(四川大学电气信息学院，四川成都610065)摘要：配电网最佳抢修路径问题实际上属于城市交通网络中的最短路径i'~-I题。针对Dijkstra算法的优缺点及在电力行业中的广泛应用，提出了一种改进的Dijkstra算法：对存放临时标注节点的无序序列按照快速

2、排序的方法来转化为有序序列。实践证明。这种算法满足最佳抢修路径的要求。关键词：最短路径；Dijkstra；快速排序Ab喇：ThesubjectofthebestrushrepairpathindistributionnetworkbelongstothesubjectoftheshortestpathinuIbaIl幽cnetwork．AccordingtotheadvantagesanddisadvantagesofDijksu-a~gorithmanditswideapplicationtoele

3、ctricpowerindustry，animprovedDijkstraalgorithmisputforward：invirtueoffastcompositor，theout—of—orderlistthatdepositsthetemporarylabelnodesistransferredtoin-of-orderlist．Theexampleshowsthealgorithmsatisfiestheneedofbestrushrepairpath．Keywords；shortestpath

4、；Dijkstraalgorithm；fastcompositor．中图分类号：忉5文献标识码：B文章编号：1003—6954(2o08)02—0030—02随着城市配电网的发展，用户不断增加，配电网最短路径，而Floyd算法适合用于求解全源最短路也日趋复杂。由于长期以来，电力建设存在着重发径。目前求最短路径的算法还有A*，Bellman—ford，电、轻输配电的问题，使中国城市配网建设相对落后。TQQ，DKA，DKD，K(<=3)条渐次最短路径搜索算法中国的配网存在很多的问题，具体表现在：①电源布等

5、。点不合理，供电半径过长，线损高；②网络结构不合对于求配电网最佳抢修路径，最适合的是Dijk．理，使运行方式安排不够灵活；③负荷增长飞速、电网stra算法，Dijkstra算法是目前许多工程解决最短路径建设用地紧张。因此，配电网发生故障的可能性将是问题的理论基础，只是不同工程对Dijkstra算法采用不可避免的。一旦停电，就将会给社会造成严重的经了不同的改进方法。济损失和不良的影响，所以当电力网络发生故障时能1．1Dijkstra算法基本思想够及时排除故障，恢复供电网的正常供电，从而缩短对图G=(，E

6、)，源点EV，设置两个顶点的集停电时间，使经济损失减少到最低就显得尤为重要合s和T=V—S，集合s中存放已找到最短路径的了。顶点，集合存放当前还未找到的最短路径的长度于是，这就引出了配电网最佳抢修路径问题。配最短的顶点。初始状态时，集合中只包含源点'／3。，然电网最佳抢修路径问题，既是GIS系统网络分析中的后不断从集合中选取到顶点'／30路径长度最短的顶一个研究热点，也是DMS的重要组成部分，其目的是点加入到集合中，集合Is中每加入一个新的顶点'／30，根据发生故障的地点以及抢修队目前所处的位置，及都

7、要修改顶点'／30到集合中剩余顶点的最短路径长时派出抢修人员到达现场，从而缩短停电时间，减少度值，集合中各顶点新的最短路径长度值为原来经济损失。的最短路径长度值与顶点'／3。的最短路径长度值加上'／30到该顶点的路径长度值中的较小值。此过程不断1技术现状重复，直到集合的顶点全部加入到s中为止。这样就可以得到最短路径的值。在这种基于贪心策略目前对于配电网最佳抢修路径技术的研究大多的Dijkstra算法的过程中，由于Dijkstra在运行时要执集中在最短路径算法的研究上，解决最短路径问题的行两套嵌套的FO

8、R语句，因此其总的时间复杂度是算法在诸多工程领域都有较强的实用价值。一般来0(／7,)。说最短路径问题分为单源最短路径和全源最短路径1．2Dijksu'a算法的应用问题，公认的比较好的Dijkstm算法比较适合于单源在电力行业中，改进的Dijkstra算法更是应用广·3O·维普资讯http://www.cqvip.com第3l卷第2期四川电力技术Vo1．31．No．22OO8年o4月SidmmElee~cPowerTeehnoto~Apt．．2OO8泛。