Open AccessA Path-Compression Approach for Improving Shortest-Path Algorithms
Author(s) -
Nabil Arman,
Faisal Khamayseh
Publication year - 2015
Publication title -
international journal of electrical and computer engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.277
H-Index - 22
ISSN - 2088-8708
DOI - 10.11591/ijece.v5i4.pp772-781
Subject(s) - path graph , shortest path problem , computer science , algorithm , distance , butterfly graph , widest path problem , graph , strength of a graph , combinatorics , mathematics , graph power , dijkstra's algorithm , line graph , voltage graph , theoretical computer science
Given a weighted directed graph G=(V;E;w), where w is non-negative weight function, G’ is a graph obtained from G by an application of path compression. Path compression reduces the graph G to a critical set of vertices and edges that affect the generation of shortest trees. The main contribution of this paper is finding shortest path between two selected vertices by applying a new algorithm that reduces number of nodes that needs to be traversed in the graph while preserving all graph properties. The main method of the algorithm is restructuring the graph in a way that only critical/relevant nodes are considered while all other neutral vertices and weights are preserved as sub paths' properties. Our algorithm can compress the graph paths into considerable improved percentage especially when the graph is sparse and hence improves performance significantly.