The need to find shortest paths in a graph from some fixed source vertex to all other vertices is quite obvious and therefore one of the most important problems in graph theory. For general graphs, the standard way to go is the Dijkstra algorithm. On planar graphs, this approach takes linearithmic time in the number of vertices. However, we present an algorithm published by Henzinger et al. in 1997 that accomplishes the task in linear time on planar graphs.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Prerequisites
- r-division
- Recursive r-division
- The Algorithm
- Priority queue data structure
- Algorithm structure
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This paper presents an algorithm for finding single-source shortest paths in planar graphs with nonnegative edge weights, achieving a linear runtime. The algorithm leverages the concept of recursive r-divisions to subdivide the graph into smaller regions, utilizing priority queues for efficient path calculation.
- Shortest Path Algorithms
- Planar Graphs
- Recursive r-divisions
- Priority Queues
- Linear-Time Algorithms
Zusammenfassung der Kapitel (Chapter Summaries)
- Introduction: This section introduces the problem of finding shortest paths in planar graphs, highlighting the need for efficient algorithms and the limitations of Dijkstra's algorithm in this context. It presents the algorithm proposed by Henzinger et al. [HKRS97] that achieves linear time complexity.
- Prerequisites: This chapter defines essential concepts like r-divisions and recursive r-divisions, which are crucial for understanding the algorithm's operation. It describes the properties of r-divisions and the use of recursive divisions to break down the graph into manageable components.
- The Algorithm: This chapter details the structure of the algorithm, emphasizing the use of priority queues to efficiently manage path calculations within the graph's regions. It describes the three procedures: sssp, update, and process, explaining their roles in the overall algorithm.
Schlüsselwörter (Keywords)
This paper focuses on the efficient computation of shortest paths on planar graphs with nonnegative edge weights using recursive r-divisions and priority queues. Key terms include shortest paths, planar graphs, recursive r-divisions, priority queues, and linear-time algorithms. The paper contributes to the field of graph algorithms by providing an optimized solution for the single-source shortest path problem on planar graphs.
- Citation du texte
- Anonym (Auteur), 2021, Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time, Munich, GRIN Verlag, https://www.grin.com/document/1001013
