Networking and Communication Engineering

R. Kalpana ¹, P. Thambidurai ², H. Shahul Hamead ¹

Affiliations
1 Department of Computer Science & Engineering, Pondicherry Engineering College, Pondicherry-605 014, IN
2 Perunthalaivar Kamarajar Institute of Engineering and Technology (PKIET), Karaikal–609 603, KZ

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.

Keywords

Arc Flag, Land Mark, Speedup, Graph, Shortest Path.

Full Text