Shortest Paths: Dijkstra, PriorityQueue and a Brief Look at A*
Dijkstra finds the cheapest path in a graph with non-negative weights: with lazy deletion, since PriorityQueue has no decrease-key, in O((V + E) log V). We trace Dijkstra step by step on an intercity shipping network, reconstruct the path, show the wrong result with a negative weight and Bellman-Ford, and measure A* finding the same path on a 200 × 200 warehouse grid with 1,845 cells instead of 33,600.
8 Nov 2026
·
11 min
·
2
