'Is Dijkstra's Algorithm Optimal?' - A Basser-SMRI Joint Seminar by Robert Tarjan
2025-12-01 14:00 - 16:00 (Australia/Sydney)
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.”

Join us for the first Basser-SMRI Joint Seminar, to be given by Robert Tarjan (Princeton). Basser Seminars highlight the best of computer science research. Feel free to distribute to others that may be interested. After the seminar, please join us for a special afternoon tea, held at 3 pm.

Robert Tarjan, Princeton University

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.

Key event details

Date & time:

Monday 1 December 2025

Seminar: 2 — 3 pm

Afternoon tea 3 pm — 4 pm

Cost:

This is a free event

Location:

The Quad General Lecture Theatre K2.05

University of Sydney, Camperdown Campus
