A Path-Compression Approach for Improving Shortest-Path Algorithms

Abstract

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.