Optimizing Dijkstra’s Algorithm: Enhancing Pathfinding Efficiency Through Heuristics and Structural Techniques

摘要

Dijkstra’s shortest path algorithm is a fundamental graph search method widely used in domains such as navigation, robotics, gaming, and network routing. However, its performance can degrade on large, complex graphs. This paper summarizes and evaluates several optimization techniques that enhance Dijkstra’s algorithm, including heuristic-guided search (Greedy Best-First and A<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup>), hierarchical preprocessing (Contraction Hierarchies), and a hybrid Genetic Algorithm approach. We describe the integration of each technique with the base algorithm and conduct comparative efficiency analysis using a real-world road network dataset. Performance is evaluated through key metrics: runtime, memory usage, and vertices explored for each algorithm. Our results show that heuristic methods drastically reduce search exploration time, while a Contraction Hierarchies approach achieves millisecond query speeds. The genetic algorithm finds high-quality paths but incurs significantly higher computational cost. We discuss the trade-offs of each enhancement in terms of optimality, speed, and resource usage. While our optimizations were tested on road networks, we discuss their potential application to different graph types and problem domains. Future research should explore these optimizations in dynamic environments with real-time graph changes, such as traffic updates. These findings provide practical guidance on choosing appropriate pathfinding optimizations for various applications and graph sizes.