For nearly seven decades, Dijkstra’s algorithm has reigned supreme as the gold standard for finding shortest paths in graphs. Born from a 20-minute mental exercise at an Amsterdam café in 1956, Edsger Dijkstra’s creation has been the backbone of everything from GPS navigation to network routing protocols. But that reign just ended.
Press enter or click to view image in full size
A research team led by Ran Duan at Tsinghua University has achieved what many considered impossible: they’ve broken the fundamental “sorting barrier” that has limited shortest-path algorithms for 40 years. Their new deterministic O(m log^(2/3) n)-time algorithm for single-source shortest paths represents a breakthrough that challenges textbook assumptions about algorithmic limits.
The Foundation That Held for 70 Years
Dijkstra’s algorithm works by maintaining a sorted priority queue of vertices, always selecting the closest unvisited vertex next. This greedy approach guarantees optimality because it processes vertices in order of their distance from the source.
def dijkstra(graph, source):distances = {vertex: float('infinity') for vertex in graph}
distances[source] = 0
priority_queue = [(0, source)]
visited = set()
while priority_queue…