COAL: Combination of Arc Flag and Land Mark Speedup Techniques for Shortest Path queres

Abstract

Computing shortest path from one node to another node in a directed graph is a more general job. This problem was originally sorted by Dijkstra’s algorithm. Many heuristic algorithms were proposed to speedup the standard Dijkstra’s algorithm. The focus of this work is combination of two speed-up techniques called Arc Flag Method and Landmark Approach for Dijkstra’s algorithm. In the arc-flag approach, the entire network is preprocessed to generate additional information is allowed and stored, which is then used to speedup shortest-path queries. In Landmark approach, the identified landmarks are fixed at different intervals, which possess the distance between landmark node and other nodes present in the graph. This paper combines the above two approaches and stores landmark information on arc flags which in turn would generate greater speedup factor. The main objective of this paper is to increase the speedup factor of shortest path algorithm by performing combination of two reach based heuristic techniques such as arc flag and landmark that suits good for practical approach and to reduce down the space consumed by the algorithm by introducing start pointers.