Why Dijkstra's Algorithm is slow, and when we can do better

Alexis Beingessner

Single Source Shortest Path is an important problem in its own right, and as a tool for solving other problems. However Dijkstra's Algorithm, the most famous general-purpose solution to the problem, runs in super-linear time in general. We look at why Dijkstra's algorithm works like it does, and why this leads to a suboptimal running time. We then examine Henzinger et al's linear time solution for planar graphs to determine how it overcomes Dijkstra's issues, and when the techniques are applicable.