Thema der Dissertation:
Optimization Algorithms for the Flight Planning Problem Thema der Disputation:
Algorithms for the Shortest Path Problem
Optimization Algorithms for the Flight Planning Problem Thema der Disputation:
Algorithms for the Shortest Path Problem
Abstract: The Shortest Path Problem (SPP) is one of the classical problems in discrete optimization. It plays a crucial role in numerous fields, such as transportation, logistics, telecommunications, and robotics. In this talk, we provide a short overview of some of the most relevant algorithms for solving the SPP.
Dijkstra's algorithm, developed in 1956, represents a fundamental landmark in shortest path computations. Despite its age, it is still widely used for benchmarking new algorithms, as well as for many applicaions. It operates on weighted graphs and guarantees finding the shortest paths from a single source to all other nodes.
A*, an extension of Dijkstra's algorithm, incorporates heuristics to guide the search towards the destination. This informed search algorithm has gained popularity due to its efficiency in pathfinding for applications like robotics, video games, and map navigation systems. By intelligently estimating the remaining cost, A* algorithm effectively balances accuracy and speed, making it a go-to choice in many real-world scenarios.
In recent years, Contraction Hierarchies (CH) have emerged as a highly efficient approach for computing shortest paths. CH exploits the hierarchical structure of road networks, precomputing shortcuts and contracting less essential nodes. By leveraging this technique, CH achieves remarkable speed and memory improvements, making it well-suited for large-scale routing applications, such as online map services and transportation planning systems.
In this talk, we describe the underlying principles of these (and possibly other) algorithms. We explore their advantages and limitations, and present a short overview of the current direction of state-of-theart research.
Dijkstra's algorithm, developed in 1956, represents a fundamental landmark in shortest path computations. Despite its age, it is still widely used for benchmarking new algorithms, as well as for many applicaions. It operates on weighted graphs and guarantees finding the shortest paths from a single source to all other nodes.
A*, an extension of Dijkstra's algorithm, incorporates heuristics to guide the search towards the destination. This informed search algorithm has gained popularity due to its efficiency in pathfinding for applications like robotics, video games, and map navigation systems. By intelligently estimating the remaining cost, A* algorithm effectively balances accuracy and speed, making it a go-to choice in many real-world scenarios.
In recent years, Contraction Hierarchies (CH) have emerged as a highly efficient approach for computing shortest paths. CH exploits the hierarchical structure of road networks, precomputing shortcuts and contracting less essential nodes. By leveraging this technique, CH achieves remarkable speed and memory improvements, making it well-suited for large-scale routing applications, such as online map services and transportation planning systems.
In this talk, we describe the underlying principles of these (and possibly other) algorithms. We explore their advantages and limitations, and present a short overview of the current direction of state-of-theart research.
Zeit & Ort
13.09.2023 | 10:00
Seminarraum 032
(Fachbereich Mathematik und Informatik, Arnimallee 6, 14195 Berlin)
UND
WebEx