搜索
21 120012JournalofBeijingInstituteofTechnologyVol.21 No.1Feb.2001 :1001-0645(2001)01-0031-04于东凯, 刘玉树(, 100081) :.,,,,,.:;;;:TP301.6 :A:20000631::(1975-),,;(1941-),,,.,、、,.[1]..1 FloydDijkstra,Floyd.Dijkstra,.Cherkassky1993SUNSparc-1017,[2].1996ZhanNoonCherkassky1715,:Dijkstra[3].1.1 Dijkstra,、,ForwardStar[3].,,.,1,2,3,…,..1.2 Dijkstra,Dijkstra.Dijkstra,3:d(i),p(i)s(i).d(i)i;p(i),i;s(i),、3.d(i),d(v0)=0(v0);s(i)=unla-beled,s(v0)=temporarylabeled.: scanprocedure begin repeat ifthereisnotemporarylabelednodethenendprocedurewithfailflag; else forallsuccessornodesofido ifd(i)+l(i,j)d(j)then begin d(j)=d(i)+l(i,j); p(j)=i; s(j)=temporarylabeled; end s(i)=permanentlylabeled; untilthetargetnodeispermanentlabeled; end.1.3 Dijkstra,[3].FIFO(first-in-first-out),LIFO(last-in-first-out)BFS(best-first-search)[4].BFSDijkstra.,、、[4,5].O(n),n,n,O(n2),O(n).2 Dijkstra2.1 Dijkstra,:1 Gv;e;dG(v)Gv;v(G)G;X(G)G.2 G;G,f.GH(G);GF(G);dG(f)Gf,Gf.3221 3 G,G*:Gf,G*f*,Ge,G*e*;G*f*g*e*,Gf*g*fge.G*G.1 v(G*)=H(G),X(G*)=X(G),dG*(f*)=dG(f)f∈F(G).2 GG2.3 G,∑f∈Fd(f)=2X.4 G,v(G)-X(G)+H(G)=2().. v(G)3v(G)≥3f∈F(G)dG(f)≥3,∑f∈Fd(f)≥3H.32X(G)≥3H(G),4v(G)-X(G)+2X(G)/3≥2,X(G)≤3v(G)-6,2∑v∈Gd(v)≤6v(G)-12,G6.,Dijkstra.:,、7,7,;.2.2 ,Dijkstra,BFS..,id(i),jd(j),,.,,1.0,,.,,,O(lgn)[6],n.,,,n.3 Dijkstra:33 1:.,..,6,O(n).O(lgn),,O(nlgn),O(n).,,.:[1] BondyJA,MurtyUSR..,,.:,1984.[2] CherkasskyBK,GoldbergAV,RadzikT.Shortestpathsalgorithms:Theoryandexperi-mentalevaluation[R].Stanford:ComputerScienceDepartment,StanfordUniversity,Tech-nicalReport93-1480,1993.[3] ZhanFB.Threefastestshortestpathalgorithmsonrealroadnetworks[J].JournalofGeo-graphicInformationandDecisionAnalysis,1997,1(1):69-82.[4] GalloG,PallottinoS.Shortestpathsalgorithms[J].AnnalsofOperationsResearch,1988,13:3-79.[5] AhujaRK,MehlhornK,OrlinJB,etal.Fasteralgorithmsfortheshortestpathproblem[J].JournalofAssociationofComputingMachinery,1990,37:213-223.[6] RichardEK.Liner-spacebest-firstsearch[J].ArtificialIntelligence,1993,62:41-78.StudyonaRoutingAlgorithmBasedonIchnographyYUDong-kai, LIUYu-shu(Dept.ofComputerScienceandEngineering,BeijingInstituteofTechnology,Beijing100081,China)Abstract:Dealswiththecomputationoftheshortestpathsoveranetworkofanichnographytoresolvethetimecomplexityandspacecomplexityproblemsintheshortestpathsearchingalgorithm.Thisalgorithmisbasedonrealnetworkimple-mentation.Anewdatastructureisdesignedandalinertimeandspaceexpenseisreachedinsearchingfortheshortestpathsinarealnetworkofichnography.Inthisarticle,astrictdemonstrationisgiventodemonstratethetimeandspaceexpendi-ture.Keywords:shortestpath;graph;ichnography;Eulerformula3421