基于平面图的最短路径算法的研究

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