摘要
Heuristicisanimportantmethodtosolvetheshortestpathproblems.Itindicatesliterallylearningbyexperience,ormoregenerallyintheartificialintelligenceliterature,aheuristicisa“ruleofthumb”andassuchistheapproachusedbyalmostanyhumaninconductingasearch［1］。Inthecontextofcomputersearchalgorithms,heuristicimpliessimplesearchthroughspecificknowledge.Un_deraspecialfunction,ateverystepthesealg_orithmssearchthenodewithhighestscoreasthenextnodetobeextended.Themajoreffectofheuristicsearchisthatinsomewayitconstrainsthesearchspace.Theshortestpathalgorithmsbasedonheuristicincludescostingalgorithm［1］，branch_and_boundalgorithm［2，3］，greedyalgorithms［4～11］，hill_climbingalgorithms［1～3］，andA*algorithm［12～14］,etc. Amongtheknownshortestpathalgorithms,manyofthemusethegreedystrategiesasthesearchstrategiesandexplorehowtodesigndelicaterunningdatastructuresandsearchingalgorithms,soastoimprovetherunningefficiencyofsequentialshortestpathalgorithmsundertheuniformtimecomplexity.Forthetwobranchesoflosslessshortestpathalgorithms：labelsettingandlabelcorrectingalgorithms，expertshavesetforwardvariousrunningdatastructuresandrelatedliteraturesemergeendlessly.Refs.［15～19］havemadedetailedanalysisandcomparisonfortheshortestpathalgorithmspresentedbefore.Becausetherealnetworks,suchastransportationnetworks,telecommunicationnetworks,facilitynetworksandhydrographicnetworksdonotconcernnegativeweights,afamouslabelsettingalgorithmadoptinggreedystrategy,namelyDijkstra'salgorithm,hasattractedwideattentionandgotwidedisseminationandapplications.Dijkstra'salgorithmisthemostmatureshortestpathalgorithmtheoreticallyuptodate［8,16,20］andhasbecomethecrucialalgorithmforthenetworkanalysismodulesofmanylargeGISplatforms.Differentimplementationmethodshaveformedalargefami
出版日期
2000年04月14日（中国期刊网平台首次上网日期，不代表论文的发表时间）
