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.
Dijkstra’s algorithm wi... 16页 免费 Dijkstra... Meeting 11 October 4, 2005 Fibonacci Heaps The...cost applied to an initially empty Fibonacci heap...
Dijkstra’s algorithm wi... 10页 免费 Rangan. Relaxed fibonacc... 暂无...[5] invented an implementation of the priority queue called Fibonacci heaps....
Dijkstra’s algorithm wi... 10页 免费 Rangan. Relaxed fibonacc... 暂无...[5] invented an implementation of the priority queue called Fibonacci heaps....
热门文档