Two phase shortest path algorithm for non-negative weighted undirected graphs

Muhammad Aasim Qureshi, Mohd Fadzil Hassan, Sohail Safdar, Rehan Akbar

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

Abstract

Breadth First Search (BFS) can calculate the shortest path for un-weighted graphs very efficiently but when it comes to non-negative weighted graphs it fails at a point when a successor updates a predecessor. Such nodes are being referred as Culprit nodes in this research. These Culprit nodes are the ones that cause error in shortest path in an algorithm that traverses like BFS. This research targets on recognizing and marking Culprit nodes to disengage them until they are properly and completely updated. Processing through such nodes is postponed until all possible updates are made on these nodes nullifying all possible chances of errors. As nodes are being traversed in BFS fashion with few violations and additions promising a O(k(|V| + |E|)) time algorithm where 0<k<<log n. More over this algorithm does not need any complex data structure.

Original languageEnglish
Title of host publicationProceedings of the 2010 Second International Conference on Communication Software and Networks
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages223-227
Number of pages5
ISBN (Electronic)9781424457274
ISBN (Print)9781424457267
DOIs
Publication statusPublished - 25 Mar 2010
Event2nd International Conference on Communication Software and Networks, ICCSN 2010 - Singapore, Singapore
Duration: 26 Feb 201028 Feb 2010

Conference

Conference2nd International Conference on Communication Software and Networks, ICCSN 2010
Country/TerritorySingapore
CitySingapore
Period26/02/1028/02/10

Keywords

  • algorithm
  • component
  • linear time
  • shortest path
  • theoretical computer science
  • undirected graphs

Cite this