Comparing the Approaches of Graph Reduction and Landmark Shortest-Paths

Abstract

We study the different recent improvements on shortest path algorithms. We suggest improvements to the classical path computing algorithms and we implement them using random generated graphs with various sizes. Many attempts exist for improving shortest path techniques. Computing shortest path is one of the most important and recent issues in combinatorial optimization, emergency routs, NoSQL data graph representation, road and public transportation networks, and other applications. One of the big obstacles in such real-word applications is the size of the graphs that motivates the attempts of enhancing the path finding procedures. Given a weighted graph G={V,E,w}, a heuristic method to improve conventional shortest-path for a given source node <s> is provided. In this paper, we address the complexity of shortest paths in large graphs and we present a graph structure and enhancement process of finding the shortest path in the given graph. We study the current improving algorithms and highlights the improvements over the classical ones. We evaluate our implemented techniques using randomly generated weighted graphs. The main procedure is compressing the graph without losing the graph properties. We then, compare our technique with the approach of using landmark optimization. We discuss the performance, storage, error rate in our approach compared to landmark. Our experiments show that the new technique of graph compression performs with better speedup and no path mistakes compared to fast landmark approach which leads to high overhead in most situations.