An edge-wise linear shortest path algorithm for non negative weighted undirected graphs

M. Aasim Qureshi*, Mohd Fadzil Hassan, Sohail Safdar, Rehan Akbar, Rabia Sammi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In most of the shortest path problems like vehicle routing problems and network routing problems, we only need an efficient path between two points-source and destination, and it is not necessary to calculate the shortest path from source to all other nodes. This paper concentrates on this very idea and presents an algorithm for calculating shortest path for nonnegative weighted undirected graphs. The algorithm completes its execution in O(|E|) for all targeted graphs-where no successor node updates predecessor node. The main advantage of the algorithms is its simplicity and it does not need complex data structures for implementations.

Original languageEnglish
Title of host publicationFIT '09: Proceedings of the 7th International Conference on Frontiers of Information Technology
PublisherAssociation for Computing Machinery, Inc
Number of pages4
ISBN (Print)9781605586427
DOIs
Publication statusPublished - 16 Dec 2009
EventFIT '09: 7th International Conference on Frontiers of Information Technology - Abbottabad, Pakistan
Duration: 16 Dec 200918 Dec 2009

Publication series

NameFIT '09: Proceedings of the 7th International Conference on Frontiers of Information Technology
PublisherACM

Conference

ConferenceFIT '09: 7th International Conference on Frontiers of Information Technology
Country/TerritoryPakistan
CityAbbottabad
Period16/12/0918/12/09

Keywords

  • algorithms
  • shortest path
  • theoretical computer science

Cite this