A near linear shortest path algorithm for weighted undirected graphs

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

*Corresponding author for this work

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


This paper presents an algorithm for Shortest Path Tree (SPT) problem. The presented algorithm is an improvement over a previously published work of the authors. The effort is put in to improve the running/execution time of the SPT problem. Introduced improvement is simple and easy to incorporate in to the existing algorithm. This algorithm uses Depth First Search (DFS) like graph traversal during a BFS like traversal i.e. combines and take advantage of the inherent properties of the two heuristic graph search techniques so that vertex weights can be kept balanced. The need of improvement is discussed in detail and the expected improvement in overall processing time is shown with the example.

Original languageEnglish
Title of host publicationProceedings of the ISCI 2011 - 2011 IEEE Symposium on Computers and Informatics
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781612846910
ISBN (Print)9781612846897
Publication statusPublished - 21 Jul 2011
Event2011 IEEE Symposium on Computers and Informatics, ISCI 2011 - Kuala Lumpur, Malaysia
Duration: 20 Mar 201122 Mar 2011


Conference2011 IEEE Symposium on Computers and Informatics, ISCI 2011
CityKuala Lumpur


  • algorithm
  • graph theory
  • shortest path problem
  • theoretical computer science (TCS)

Cite this