A near linear shortest path algorithm for weighted undirected graphs

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

doi:10.1109/ISCI.2011.5958895

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

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Proceedings of the ISCI 2011 - 2011 IEEE Symposium on Computers and Informatics
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	119-124
Number of pages	6
ISBN (Electronic)	9781612846910
ISBN (Print)	9781612846897
DOIs	https://doi.org/10.1109/ISCI.2011.5958895
Publication status	Published - 21 Jul 2011
Event	2011 IEEE Symposium on Computers and Informatics, ISCI 2011 - Kuala Lumpur, Malaysia Duration: 20 Mar 2011 → 22 Mar 2011

Conference

Conference	2011 IEEE Symposium on Computers and Informatics, ISCI 2011
Country/Territory	Malaysia
City	Kuala Lumpur
Period	20/03/11 → 22/03/11

Keywords

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

Access to Document

10.1109/ISCI.2011.5958895

Cite this

@inproceedings{5baac0f6962c4d3a99c59f4e13e9210c,

title = "A near linear shortest path algorithm for weighted undirected graphs",

abstract = "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.",

keywords = "algorithm, graph theory, shortest path problem, theoretical computer science (TCS)",

author = "Qureshi, {Muhammad Aasim} and Hassan, {Mohd Fadzil} and Sohail Safdar and Rehan Akbar",

year = "2011",

month = jul,

day = "21",

doi = "10.1109/ISCI.2011.5958895",

language = "English",

isbn = "9781612846897",

pages = "119--124",

booktitle = "Proceedings of the ISCI 2011 - 2011 IEEE Symposium on Computers and Informatics",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "2011 IEEE Symposium on Computers and Informatics, ISCI 2011 ; Conference date: 20-03-2011 Through 22-03-2011",

}

Qureshi, MA, Hassan, MF, Safdar, S & Akbar, R 2011, A near linear shortest path algorithm for weighted undirected graphs. in Proceedings of the ISCI 2011 - 2011 IEEE Symposium on Computers and Informatics., 5958895, Institute of Electrical and Electronics Engineers Inc., pp. 119-124, 2011 IEEE Symposium on Computers and Informatics, ISCI 2011, Kuala Lumpur, Malaysia, 20/03/11. https://doi.org/10.1109/ISCI.2011.5958895

A near linear shortest path algorithm for weighted undirected graphs. / Qureshi, Muhammad Aasim; Hassan, Mohd Fadzil; Safdar, Sohail et al.
Proceedings of the ISCI 2011 - 2011 IEEE Symposium on Computers and Informatics. Institute of Electrical and Electronics Engineers Inc., 2011. p. 119-124 5958895.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A near linear shortest path algorithm for weighted undirected graphs

AU - Qureshi, Muhammad Aasim

AU - Hassan, Mohd Fadzil

AU - Safdar, Sohail

AU - Akbar, Rehan

PY - 2011/7/21

Y1 - 2011/7/21

N2 - 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.

AB - 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.

KW - algorithm

KW - graph theory

KW - shortest path problem

KW - theoretical computer science (TCS)

UR - http://www.scopus.com/inward/record.url?scp=80052112331&partnerID=8YFLogxK

U2 - 10.1109/ISCI.2011.5958895

DO - 10.1109/ISCI.2011.5958895

M3 - Conference contribution

AN - SCOPUS:80052112331

SN - 9781612846897

SP - 119

EP - 124

BT - Proceedings of the ISCI 2011 - 2011 IEEE Symposium on Computers and Informatics

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2011 IEEE Symposium on Computers and Informatics, ISCI 2011

Y2 - 20 March 2011 through 22 March 2011

ER -