A complete compressing sparse graphs in dijkstra’s shortest path algorithm

Abstract

Dijkstra algorithm is one of the prominent algorithms to find the shortest path from the source node to a destination node. It uses the greedy approach to find the shortest path. The concept of the Dijkstra algorithm is to find the shortest distance (path) starting from the source point and to ignore the longer distances while doing an update. One of the problems that arises from the continuously growing amount of data is that it slows down and limits the uses of large graphs in real world situations. Because of this, studies are being done to investigate the possibility of compressing data in large graphs. This report presents an investigation on the usefulness of compressing sparse graphs and then applying Dijkstra’s shortest path algorithm. A minimal spanning tree algorithm was used to compress a graph and compared with a self-implemented compression algorithm. The minimal distances and how long time it takes for Dijkstra's algorithm to find the shortest path between nodes are investigated. The results show that it is not worth compressing the type of sparse graphs used in this study. It is hard to compress the graph without losing too much of the edges that preserve the shortest paths. The time gained when running Dijkstra's algorithm on the compressed graphs is not enough to compensate for the lack of getting a good shortest path solution.