Open Access Open Access  Restricted Access Subscription or Fee Access

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

R. Kalpana, Dr. P. Thambidurai, H. Shahul Hamead


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.


Arc flag, Land mark, speedup, graph, shortest path.

Full Text:



Rolf H. Mohring and Heiko Schilling, “Partitioning Graphs to Speedup Dijkstra’s Algorithm,” in ACM Journal of Experimental Algorithmics, Vol. 11, Article No. 2.8, 2006.

Andrew V.Goldberg, Chris Harrelson, “Computing the Shortest Path: A* Search Meets Graph Theory,” Microsoft Research 2005, 1065 La Avenida, Mountain View, CA 94062

Martin Holzer, Frank Schulz, Dorothea Wagner, and Thomas Willhalm,, “Combining Speed-up Techniques for Shortest-Path Computations,” in ACM Journal of Experimental Algorithmics, Vol. 10, Article No. 2.5, 2005.

Peter Sanders and Dominik Schultes , “Highway Hierarchies Hasten Exact Shortest Path Queries,” ESA 2005, LNCS 3669, pp. 568–579, Springer-Verlag Berlin Heidelberg 2005.

Dorothea Wagner and Thomas Willhalm , “Geometric Containers for Efficient Shortest-Path Computation”, ACM Journal of Experimental Algorithmics, Vol. 10, Article No. 1.3, 2005.

Dijkstra. E. W, “A note on two problems in connection with graphs,” In Numerische Mathematik. Vol. 1. Mathematisch Centrum, Amsterdam, The Netherlands, pp. 269–271, 1959.

Johnson. D. B, “Efficient algorithms for shortest paths in sparse networks,” Journal of the Association for Computing Machinery Vol. 24, 1, pp. 1–13, 1959.

Holzer. M, Tech, “Hierarchical speedup techniques for shortest path algorithms,” report submitted to Dept of Informatics, University of Konstanz, Germany, 2003.

Willhalm. T, Ph.D.thesis, submitted to Faculty of Informatics, “Engineering shortest paths and layout algorithms for large graphs,” University of Karlsruhe, 2005.

Gutman. R. J, “Reach-based routing: A new approach to shortest path algorithms optimized for road networks,” In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004.

Frederikson. G. N, Siam, “ Fast algorithms for shortest paths in planar graphs with applications,” Journal on Computing Vol. 16, pp. 1004–1022, 1987.

Agrawal. R. and Jagadish. H. V, “Algorithms for searching massive graphs,” IEEE Transactions on Knowledge and Data Engineering Vol.6, Issue 2, pp. 225–238, 1994.

Car. A and Frank. A. U, “Modelling a hierarchy of space applied to large road networks,” In IGIS ’94: Geographic Information Systems, 1994.

Schulz. F, Wagner. D and Weihe. K, “Dijkstra’s algorithm on-line: An empirical case study from public railroad transport,” in ACM Journal of Experimental Algorithms, Vol. 5, 2000.

Lauther. U, “An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background,” in Geoinformation und Mobilit ¨at-von der For schung zurpraktischen Anwendung, Vol 22, pp. 219–230, 2004

Kohler. E, Mohring. R. H., and Schilling. H, “Acceleration of shortest path and constrained shortest path computation,” In Experimental and Efficient Algorithms, 4th International Workshop, WEA 2005, S. E. Nikoletseas, Ed. Lecture Notes in Computer Science, vol. 3503. Springer, Heidelberg, pp. 126–138, 2005.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.