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

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

doi:10.1109/ICCSN.2010.97

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

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

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 2010 Second International Conference on Communication Software and Networks
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	223-227
Number of pages	5
ISBN (Electronic)	9781424457274
ISBN (Print)	9781424457267
DOIs	https://doi.org/10.1109/ICCSN.2010.97
Publication status	Published - 25 Mar 2010
Event	2nd International Conference on Communication Software and Networks, ICCSN 2010 - Singapore, Singapore Duration: 26 Feb 2010 → 28 Feb 2010

Conference

Conference	2nd International Conference on Communication Software and Networks, ICCSN 2010
Country/Territory	Singapore
City	Singapore
Period	26/02/10 → 28/02/10

Keywords

algorithm
component
linear time
shortest path
theoretical computer science
undirected graphs

Access to Document

10.1109/ICCSN.2010.97

Cite this

@inproceedings{3315427945ec4564909e0d484b781f7f,

title = "Two phase shortest path algorithm for non-negative weighted undirected graphs",

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",

keywords = "algorithm, component, linear time, shortest path, theoretical computer science, undirected graphs",

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

year = "2010",

month = mar,

day = "25",

doi = "10.1109/ICCSN.2010.97",

language = "English",

isbn = "9781424457267",

pages = "223--227",

booktitle = "Proceedings of the 2010 Second International Conference on Communication Software and Networks",

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

address = "United States",

note = "2nd International Conference on Communication Software and Networks, ICCSN 2010 ; Conference date: 26-02-2010 Through 28-02-2010",

}

Qureshi, MA, Hassan, MF, Safdar, S & Akbar, R 2010, Two phase shortest path algorithm for non-negative weighted undirected graphs. in Proceedings of the 2010 Second International Conference on Communication Software and Networks., 5437599, Institute of Electrical and Electronics Engineers Inc., pp. 223-227, 2nd International Conference on Communication Software and Networks, ICCSN 2010, Singapore, Singapore, 26/02/10. https://doi.org/10.1109/ICCSN.2010.97

Two phase shortest path algorithm for non-negative weighted undirected graphs. / Qureshi, Muhammad Aasim; Hassan, Mohd Fadzil; Safdar, Sohail et al.
Proceedings of the 2010 Second International Conference on Communication Software and Networks. Institute of Electrical and Electronics Engineers Inc., 2010. p. 223-227 5437599.

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

TY - GEN

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

AU - Qureshi, Muhammad Aasim

AU - Hassan, Mohd Fadzil

AU - Safdar, Sohail

AU - Akbar, Rehan

PY - 2010/3/25

Y1 - 2010/3/25

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

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

KW - algorithm

KW - component

KW - linear time

KW - shortest path

KW - theoretical computer science

KW - undirected graphs

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

U2 - 10.1109/ICCSN.2010.97

DO - 10.1109/ICCSN.2010.97

M3 - Conference contribution

AN - SCOPUS:77952409513

SN - 9781424457267

SP - 223

EP - 227

BT - Proceedings of the 2010 Second International Conference on Communication Software and Networks

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2nd International Conference on Communication Software and Networks, ICCSN 2010

Y2 - 26 February 2010 through 28 February 2010

ER -

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

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this