Is Dijkstra’s Algorithm Optimal?

Robert Tarjan, Princeton University

Dijkstra’s algorithm is a classic algorithm for doing route planning. Given a starting location it finds shortest paths from to all other reachable locations using the greedy method. Not only does it find shortest paths, it finds these in increasing order by length. A natural question is whether this algorithm is best possible. The answer depends on exactly how one poses the question. The talk will cover recent work by the speaker and his colleagues that gives the answer “yes” and briefly examine work by others that gives the answer “no.”

About the speaker: Robert Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies. He has invented or co-invented many of the most efficient known data structures and graph algorithms. He was awarded the first Nevanlinna Prize from the International Mathematical Union in 1982 for “for outstanding contributions to mathematical aspects of information science,” the Turing Award in 1986 with John Hopcroft for “fundamental achievements in the design and analysis of algorithms and data structures,” and the Paris Kanellakis Award in Theory and Practice in 1999 with Daniel Sleator for the invention of splay trees. He is a member of the U.S. National Academy of Sciences, the U. S. National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society.

This seminar was a Basser-SMRI seminar run in conjunction with the School of Computer Science

Monday 1st December, 2025