Breaking Dijkstra's Algorithm
O(m + n log n) → O(m log2/3 n)
Legend:
Source
Settling
Pivot / block
Frontier
Complete / visited
Queue (Dijkstra)
Path
Discovered
Undiscovered
Dijkstra's Algorithm
Not Started
Tsinghua's Algorithm
Not Started
O(m + n log n) → O(m log2/3 n)