文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > Dijkstra’s algorithm with Fibonacci heaps An executable description
侵权投诉

Dijkstra’s algorithm with Fibonacci heaps An executable description

Abstract. We construct a readable, compact and efficient implementation of Dijkstra’s shortest path algorithm and Fibonacci heaps using Constraint Handling Rules (CHR), which is increasingly used as a high-level rule-based general-purpose programming lang

TheSSSPproblemwithnonnegativeedgeweightscanbesolvedusingDijkstra’sclassicalalgorithm[7].AnaiveimplementationofthisalgorithmrunsinO(n2)time,whichissuboptimalfornon-densegraphs.E cientimplementationsuseapriorityqueue,adatastructureconsistingofasetofitem-keypairs,subjecttothefollowingoperations:insert,addinganewpairtothequeue;extract-min,returningandremovingthepairwiththeminimumkey;anddecrease-key,decreasingthekeyofagivenitem.Fibonacciheaps(F-heaps)implementinsertanddecrease-keyinO(1)amortizedtime,andextract-mininO(logn)amortizedtime,wherenisthenumberofelementsinthequeue.UsingF-heaps[9],Dijkstra’salgorithmtakesO(m+nlogn)time.ThiscombinationisstillthefastestknownalgorithmforsolvingthisvariantoftheSSSPproblem.3Anexecutabledescriptionofthealgorithms

Inthissection,wegiveahigh-leveldescriptionofDijkstra’salgorithmwithFibonacciheapsusingCHRrules,whicharedirectlyexecutableinanyCHRsystem.AllrecentCHRsystemsimplementthere nedoperationalsemantics[8],whichimpliesthattherulesaretriedintextualorder.Correctness,termination,andcomplexityoftheprogramcruciallydependonthisexecutionstrategy.Thiscanbeavoidedbyintroducingauxiliary agconstraints,additionalguards,andextrarules,althoughtheresulting(con uent)programwouldbelesscompactandtheconstantfactorinitscomplexitywouldbeworse.

3.1Dijkstra’salgorithm

Theinputgraphisgivenasmedge/3constraints:a(directed)edgefromnodeAtoBwithweightWisrepresentedasedge(A,B,W).Nodenamesareintegersin[1,n]andweightsarenon-negativenumbers.Thequeryconsistsofasequenceofedge/3constraintsfollowedbyonedijkstra(S)constraint,whereSisthesourcenode.Theoutputofthealgorithmconsistsofndistance(X,D)constraints,whereDisthedistancefromnodeStonodeX.

DuringtheexecutionofDijkstra’salgorithm,eachnodeisinoneofthreestates:unlabeled,labeled(withatentativedistance),orscanned(andannotatedwithacorrectdistance).

Weuseaglobalpriorityqueuetostorethelabelednodes;theitemisthenodename,thekeyisitstentativedistance.WhenanodeXisscanned,westoreitsdistanceDasadistance(X,D)constraint.Theunlabelednodesarenotstoredexplicitly.Weassumethatthepriorityqueuehasadecrins(Item,Key)operationwhichinserts(Item,Key)intothequeueifItemisnotalreadyinthequeue;otherwiseitupdatesthekeyofItemifthenewkeyKeyissmallerthantheoriginalkey(ifitislarger,theoperationhasnoe ect).Wealsoassumethatthereisanextractoperationwhichreturnstheitemwiththesmallestkeyandremovesitfromthequeue(andfailswhenthequeueisempty).

Initially,everynodeisunlabeledexceptforthesourcenodewhichgetstentative(andcorrect)distancezero.Westartbyscanningthesource:

start_scanning@dijkstra(A)<=>scan(A,0).

Toscananode,we rstoutputits naldistance.Thenweexaminealloutgoingedgestorelabeltheneighbors.Thecandidatelabelforaneighboristhesumofthedistanceofthescannednodeandtheweightoftheconnectingedge:

final_dist@scan(N,L)==>distance(N,L).

label_neighb@scan(N,L),edge(N,N2,W)==>L2isL+W,relabel(N2,L2).

Thenwescanthelabelednodewiththesmallesttentativedistance(orstopiftherearenolabelednodesleft):

scan_next

scan_done@scan(N,L)<=>extract_min(N2,L2)|scan(N2,L2).@scan(N,L)<=>true.

上一页第2页

你可能喜欢

热门文档

相关文档

  • fibonacci heaps

    Dijkstra’s algorithm wi... 16页 免费 Dijkstra... Meeting 11 October 4, 2005 Fibonacci Heaps The...cost applied to an initially empty Fibonacci heap...

  • Are Fibonacci heaps optimal

    Dijkstra’s algorithm wi... 10页 免费 Rangan. Relaxed fibonacc... 暂无...[5] invented an implementation of the priority queue called Fibonacci heaps....

  • Are Fibonacci heaps optimal

    Dijkstra’s algorithm wi... 10页 免费 Rangan. Relaxed fibonacc... 暂无...[5] invented an implementation of the priority queue called Fibonacci heaps....

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email