快速排序的Dijkstra算法在配網(wǎng)搶修路徑中的應(yīng)用

《快速排序的Dijkstra算法在配網(wǎng)搶修路徑中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、維普資訊http://www.cqvip.com第3l卷第2期四川電力技術(shù)Vo1．31。No．22OO8年o4月SichuanElectricPowerTechnologyApr．-2008快速排序的Dijkstra算法在配網(wǎng)搶修路徑中的應(yīng)用王倩，呂林(四川大學(xué)電氣信息學(xué)院，四川成都610065)摘要：配電網(wǎng)最佳搶修路徑問題實(shí)際上屬于城市交通網(wǎng)絡(luò)中的最短路徑i'~-I題。針對(duì)Dijkstra算法的優(yōu)缺點(diǎn)及在電力行業(yè)中的廣泛應(yīng)用，提出了一種改進(jìn)的Dijkstra算法：對(duì)存放臨時(shí)標(biāo)注節(jié)點(diǎn)的無序序列按照快速

2、排序的方法來轉(zhuǎn)化為有序序列。實(shí)踐證明。這種算法滿足最佳搶修路徑的要求。關(guān)鍵詞：最短路徑；Dijkstra；快速排序Ab喇：ThesubjectofthebestrushrepairpathindistributionnetworkbelongstothesubjectoftheshortestpathinuIbaIl幽cnetwork．AccordingtotheadvantagesanddisadvantagesofDijksu-a~gorithmanditswideapplicationtoele

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

4、；Dijkstraalgorithm；fastcompositor．中圖分類號(hào)：忉5文獻(xiàn)標(biāo)識(shí)碼：B文章編號(hào)：1003—6954(2o08)02—0030—02隨著城市配電網(wǎng)的發(fā)展，用戶不斷增加，配電網(wǎng)最短路徑，而Floyd算法適合用于求解全源最短路也日趨復(fù)雜。由于長期以來，電力建設(shè)存在著重發(fā)徑。目前求最短路徑的算法還有A*，Bellman—ford，電、輕輸配電的問題，使中國城市配網(wǎng)建設(shè)相對(duì)落后。TQQ，DKA，DKD，K(<=3)條漸次最短路徑搜索算法中國的配網(wǎng)存在很多的問題，具體表現(xiàn)在：①電源布等

5、。點(diǎn)不合理，供電半徑過長，線損高；②網(wǎng)絡(luò)結(jié)構(gòu)不合對(duì)于求配電網(wǎng)最佳搶修路徑，最適合的是Dijk．理，使運(yùn)行方式安排不夠靈活；③負(fù)荷增長飛速、電網(wǎng)stra算法，Dijkstra算法是目前許多工程解決最短路徑建設(shè)用地緊張。因此，配電網(wǎng)發(fā)生故障的可能性將是問題的理論基礎(chǔ)，只是不同工程對(duì)Dijkstra算法采用不可避免的。一旦停電，就將會(huì)給社會(huì)造成嚴(yán)重的經(jīng)了不同的改進(jìn)方法。濟(jì)損失和不良的影響，所以當(dāng)電力網(wǎng)絡(luò)發(fā)生故障時(shí)能1．1Dijkstra算法基本思想夠及時(shí)排除故障，恢復(fù)供電網(wǎng)的正常供電，從而縮短對(duì)圖G=(，E

6、)，源點(diǎn)EV，設(shè)置兩個(gè)頂點(diǎn)的集停電時(shí)間，使經(jīng)濟(jì)損失減少到最低就顯得尤為重要合s和T=V—S，集合s中存放已找到最短路徑的了。頂點(diǎn)，集合存放當(dāng)前還未找到的最短路徑的長度于是，這就引出了配電網(wǎng)最佳搶修路徑問題。配最短的頂點(diǎn)。初始狀態(tài)時(shí)，集合中只包含源點(diǎn)'／3。，然電網(wǎng)最佳搶修路徑問題，既是GIS系統(tǒng)網(wǎng)絡(luò)分析中的后不斷從集合中選取到頂點(diǎn)'／30路徑長度最短的頂一個(gè)研究熱點(diǎn)，也是DMS的重要組成部分，其目的是點(diǎn)加入到集合中，集合Is中每加入一個(gè)新的頂點(diǎn)'／30，根據(jù)發(fā)生故障的地點(diǎn)以及搶修隊(duì)目前所處的位置，及都

7、要修改頂點(diǎn)'／30到集合中剩余頂點(diǎn)的最短路徑長時(shí)派出搶修人員到達(dá)現(xiàn)場，從而縮短停電時(shí)間，減少度值，集合中各頂點(diǎn)新的最短路徑長度值為原來經(jīng)濟(jì)損失。的最短路徑長度值與頂點(diǎn)'／3。的最短路徑長度值加上'／30到該頂點(diǎn)的路徑長度值中的較小值。此過程不斷1技術(shù)現(xiàn)狀重復(fù)，直到集合的頂點(diǎn)全部加入到s中為止。這樣就可以得到最短路徑的值。在這種基于貪心策略目前對(duì)于配電網(wǎng)最佳搶修路徑技術(shù)的研究大多的Dijkstra算法的過程中，由于Dijkstra在運(yùn)行時(shí)要執(zhí)集中在最短路徑算法的研究上，解決最短路徑問題的行兩套嵌套的FO

8、R語句，因此其總的時(shí)間復(fù)雜度是算法在諸多工程領(lǐng)域都有較強(qiáng)的實(shí)用價(jià)值。一般來0(／7,)。說最短路徑問題分為單源最短路徑和全源最短路徑1．2Dijksu'a算法的應(yīng)用問題，公認(rèn)的比較好的Dijkstm算法比較適合于單源在電力行業(yè)中，改進(jìn)的Dijkstra算法更是應(yīng)用廣·3O·維普資訊http://www.cqvip.com第3l卷第2期四川電力技術(shù)Vo1．31．No．22OO8年o4月SidmmElee~cPowerTeehnoto~Apt．．2OO8泛。