File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A shortest path algorithm based on limited search heuristics

TitleA shortest path algorithm based on limited search heuristics
Authors
KeywordsHeuristic
Road Network
Shortest Path Algorithm
Issue Date2006
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 1st International Computer Science Symposium in Russia (CSR 2006), St. Petersburg, Russia, 8-12 June 2006. In Lecture Notes In Computer Science, 2006, v. 3967, p. 487-497 How to Cite?
AbstractDijkstra's algorithm is arguably the most popular computational solution to finding single source shortest paths. Increasing complexity of road networks, however, has posed serious performance challenge. While heuristic procedures based on geometric constructs of the networks would appear to improve performance, the fallacy of depreciated accuracy has been an obstacle to the wider application of heuristics in the search for shortest paths. The authors presented a shortest path algorithm that employs limited search heuristics guided by spatial arrangement of networks. The algorithm was tested for its efficiency and accuracy in finding one-to-one and one-to-all shortest paths among systematically sampled nodes on a selection of real-world networks of various complexity and connectivity. Our algorithm was shown to outperform other theoretically optimal solutions to the shortest path problem and with only little accuracy lost. More importantly, the confidence and accuracy levels were both controllable and predictable. © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/159111
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorLu, Fen_US
dc.contributor.authorLai, PCen_US
dc.date.accessioned2012-08-08T09:08:04Z-
dc.date.available2012-08-08T09:08:04Z-
dc.date.issued2006en_US
dc.identifier.citationThe 1st International Computer Science Symposium in Russia (CSR 2006), St. Petersburg, Russia, 8-12 June 2006. In Lecture Notes In Computer Science, 2006, v. 3967, p. 487-497en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/159111-
dc.description.abstractDijkstra's algorithm is arguably the most popular computational solution to finding single source shortest paths. Increasing complexity of road networks, however, has posed serious performance challenge. While heuristic procedures based on geometric constructs of the networks would appear to improve performance, the fallacy of depreciated accuracy has been an obstacle to the wider application of heuristics in the search for shortest paths. The authors presented a shortest path algorithm that employs limited search heuristics guided by spatial arrangement of networks. The algorithm was tested for its efficiency and accuracy in finding one-to-one and one-to-all shortest paths among systematically sampled nodes on a selection of real-world networks of various complexity and connectivity. Our algorithm was shown to outperform other theoretically optimal solutions to the shortest path problem and with only little accuracy lost. More importantly, the confidence and accuracy levels were both controllable and predictable. © Springer-Verlag Berlin Heidelberg 2006.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.subjectHeuristicen_US
dc.subjectRoad Networken_US
dc.subjectShortest Path Algorithmen_US
dc.titleA shortest path algorithm based on limited search heuristicsen_US
dc.typeConference_Paperen_US
dc.identifier.emailLai, PC:pclai@hkucc.hku.hken_US
dc.identifier.authorityLai, PC=rp00565en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/11753728_49en_US
dc.identifier.scopuseid_2-s2.0-33745909423en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33745909423&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume3967en_US
dc.identifier.spage487en_US
dc.identifier.epage497en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridLu, F=9040432300en_US
dc.identifier.scopusauthoridLai, PC=7202946446en_US
dc.customcontrol.immutablesml 160224 - amend-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats