搜索
Apr.2006,Volume3,No.4(SerialNo.17)JournalofCommunicationandComputer,ISSN1548-7709,USA3311215200DijkstraA*DijkstraA*DijkstraDijkstraA*DijkstraA*11971-1.DijkstraDijkstra2.DijkstraDijkstra[1]VSD[Uj]NODEUSE[Uj]D[Uj]U0UjNODEUSE[Uj]01U0Uj1D[Ui]=0D[Uj]=U0S={U0}NODEUSE[U0]=OUk=U0NODEUSE[Ui]=1UiV-S2V-SUkUjD[Uj]=min{D[Uj]D[Uk]+F(UkUj)}F(UkUj)UkUj3D[Uj]UiD[Ui]=min{D[Uj]Uj}UjV-SUiNODEUSE[Ui]=04Uk=Ui2Dijkstra342.A*2.1DijkstraDijkstraDijkstraA*2.2A*A*ABJ(AB)ABACBACLJ(CB)CBA*1(a)Dijkstra(b)A*1?J(AB)=K*SQRT((BA)2+(BA)2)KK=1DijkstraDijkstra2.3A*2.3.12G(V,E,f)VGEff(e)eeEGe(u,v)ff(u,v)2GGG=(V,E,F)V={v1,v2,v3,v4,v5}vi=(Xvi,Yvi)i=1,2,3,4,5E={e1,e2,e3,e4,e5,e6,e7,e8}f:f(e1)=f(v1,v2)f(e2)=f(v2,v3)f(e3)=f(v1,v3)f(e4)=f(v3,v4)f(e5)=f(v2,v4)f(e6)=f(v4,v5)f(e7)=f(v1,v5)f(e8)=f(v2,v5)352G[4]u0v0u0v0u0v0G1Guvd(uv)u0v0d(u0v0)2UVJ(UV)=SQRT((UV)2+(UV)2)u0v0u0v0J(u0v0)=SQRT((u0v0)2+(u0v0)2)J(u0,v0)d(u0,v0)33u0v0uu0v0J(u0,v0)d(u0,u)+J(u,v0)d(u0,v0)3uu0v04Gu0u0u(uV)v0(d(u0,u)+J(u,v0))v0Au0S={u0}d(u0,u0)+J(u0,v0)=J(u0,v0)BV-Sud(u0,u)+J(u,v0)=min{d(u0,v)+J(v,v0)vV-S}S=S+{u}CBu=v0Sd(u0,v0)+J(v0,v0)=d(u0,v0)3u0v0u0v0S2.3.2d(u0,u)[4]vVL(v)u0vL(u0)=d(u0,u0)=0L(v)=(vV{u0})(u,v)uvL(v)4(u,v)L(v)L(u)+f(u,v)L(v)=L(u)+f(u,v)(L(u)L(v))(a)L(v)L(u)+f(u,v)L(v)(b)L(v)L(u)+f(u,v)L(v)A*S3.A*VU0V0SL(Ui)U0UiJ(Ui,V0)UiV036RESULTNO[Uj]U0UjUjUjVNODEUSE[Ui]Ui01F(Ui,Uj)UiUjU0L(U0)=0L(Ui)=UiVNODEUSE[U0]=0U0-UiI=0{Ui}-SNODEUSE[Uj]=1UjV-SS={U0}UiUi-XHCSUj1L(Uj)L(Ui)+F(Ui,Uj)L(Uj)=L(Ui)+F(Ui,Uj)RESULTNO(Uj)=UiF(UiUj)UiUjUiUjUjU0UjL(Uj)UjUi2J(Uj,V0)=J(Uj,V0)SQRT((UjV0)2+(UjV0)2)UjV0L(Uj)+J(Uj,V0)UjV-S-UiS+{Ui}-SL(Uj)+J(Uj,V0)UiNODEUSE[Ui]=0Ui=V0?62-5L(V0)U0V0RESULTNO(V0)U051(00)2(4-2)3(80)4(42)5(100)6(162)7(18-2)8(260)518Dijkstra1-4-2-3-7-5-6-8A*1-3-5-84.A*A*DijkstraDijkstramsDijkstraA*2.71.5322.51.931.5-21.2-2.51.4-21.23.52.5-31.5-1.41-2.52-32A*DijkstraDijkstra37126()6DijkstraABS31A*AB13A*[1],,:,1995.[2],,Dijkstra,,2001.[3],,(2),:,1997:pp.159-281.[4],,.ImprovementontheShortestPathAlgorithmofDigitalTrafficMapLinZhou1(1SchoolofCommunicationandElectronicsofWujiangVocationalTechnologyCollege,NanjingUniversityofPost&Telecommunications,Wujiang215200,China)Abstract:Thispaperdiscussestheproblemsonthedesignandtherealizationofthesystem.Itemphasizesonthemeansofgatheringdata,storingdataandthedesignoftheshortestpathalgorithm.BasedOnthis,thepaperoffersusthewaytoimprovethealgorithm,andgivesusanoptimizedalgorithmcalledA*algorithm.ItcomparestheDijkstraalgorithmwiththeA*algorithmonefficiencyfinally.Keywords:ShortestPath;DijkstraAlgorithm;A*AlogrithmBrickIvan