What question did this study set out to answer?

This research aims to compare Dijkstra's algorithm against various metaheuristic methods for the shortest path problem in real transportation networks.

May 17, 2026Open Access

A Comparative Performance Analysis of Dijkstra and Metaheuristic Algorithms for the Shortest Path Problem in Inter-District Transportation Networks

Key Points

This research aims to compare Dijkstra's algorithm against various metaheuristic methods for the shortest path problem in real transportation networks.
Used real distance data from 13 districts in Muğla province, Türkiye.
Compared Dijkstra with Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization, and Simulated Annealing.
Evaluated path length optimization, computational efficiency, and convergence across multiple independent runs.
Dijkstra consistently produced the optimal solution of 200 km, while ACO matched this performance.
GA had a mean of 621 km, PSO 734 km, and SA 759 km, with varying convergence stability.
DS-SA improved to a mean of 689 km, while DS-GA and DS-PSO showed slight deterioration.

Abstract

This study addresses the classical shortest path problem, a fundamental challenge in graph theory with critical applications in transportation networks. Using real inter-district distance data from southwestern Türkiye, particularly covering 13 districts of Muğla province, the region frequently affected by forest fires during summer, this study also emphasizes the importance of shortest path analyses for routing firefighting vehicles and emergency logistics. We compare the deterministic Dijkstra algorithm with four metaheuristic approaches: Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Simulated Annealing (SA). The evaluation focuses on path length optimization, computational efficiency, and convergence behavior across multiple independent runs. Experimental findings confirm that Dijkstra consistently produces the optimal solution (200 km), while ACO achieves the same performance despite its stochastic nature. In contrast, GA (mean 621 km), PSO (mean 734 km), and SA (mean 759 km) exhibited significant deviations from the optimal solution, with varying convergence stability and computation times. These results highlight the robustness of Dijkstra in small-scale static problems, while also demonstrating the potential of ACO as a competitive metaheuristic for dynamic and large-scale applications. Furthermore, Dijkstra-Seeded (DS) hybrid variants of the three underperforming algorithms (DS-GA, DS-PSO, DS-SA) were developed to investigate whether informed initialization could improve solution quality. Experimental results revealed that Dijkstra-based seeding within a permutation-based encoding yielded mixed results, with DS-SA showing meaningful improvement (689 km mean, 9.22% better than original SA), while DS-GA (645 km mean, -3.86%) and DS-PSO (754 km mean, -2.72%) slightly deteriorated. These findings underscore the fundamental challenges of adapting continuous-space metaheuristics to discrete graph problems and highlight the importance of encoding-aware hybridization strategies.

KI fragen

Bookmark

View Full Paper