eprintid: 1257 rev_number: 2 eprint_status: archive userid: 1 dir: disk0/00/00/12/57 datestamp: 2023-11-09 15:49:25 lastmod: 2023-11-09 15:49:25 status_changed: 2023-11-09 15:39:20 type: conference_item metadata_visibility: show creators_name: Qureshi, M.A. creators_name: Hassan, M.F. creators_name: Safdar, S. creators_name: Akbar, R. title: Two phase shortest path algorithm for non-negative weighted undirected graphs ispublished: pub keywords: Breadth-first search; Complex data structures; Linear time; Shortest path; Shortest path algorithms; Theoretical computer science; Time algorithms; Two phase; Undirected graph; Weighted graph; Weighted undirected graph, Computer science; Computer software; Data structures; Graph theory; Graphic methods, Algorithms note: cited By 11; Conference of 2nd International Conference on Communication Software and Networks, ICCSN 2010 ; Conference Date: 26 February 2010 Through 28 February 2010; Conference Code:80255 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