The lecture will be delivered by Robert Tarjan, one of the most influential figures in modern computer science and a recipient of the prestigious Turing Award.
Dijkstra’s algorithm is a cornerstone of algorithmic theory and practice, widely used for route planning and network optimisation. Given a starting point, it efficiently determines shortest paths to all reachable locations using a greedy approach, producing results in order of increasing distance. A fundamental question arises: is this algorithm optimal?
In this lecture, Professor Tarjan will present recent advances addressing this question. Drawing on joint work with Bernhard Haeupler, Richard Hladík, Václav Rozhoň, and Jakub Tětek, he will explore formulations under which the answer is affirmative, as well as contrasting perspectives demonstrating inherent limitations. The talk offers both deep theoretical insight and a broader reflection on the nature of optimality in algorithm design.
Professor Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. Over the course of his career, he has held leading academic positions at institutions including Cornell, Berkeley, Stanford, and NYU, as well as research roles in major industrial laboratories such as Bell Labs, NEC, HP, and Microsoft. His pioneering contributions to data structures and graph algorithms have profoundly shaped the field.
Among numerous honours, he was awarded the Nevanlinna Prize by the International Mathematical Union and the Turing Award (shared with John Hopcroft) for fundamental achievements in the design and analysis of algorithms and data structures. He is a member of several of the world’s most prestigious academies, including the U.S. National Academy of Sciences and the American Academy of Arts and Sciences.
This lecture offers a rare opportunity to engage with cutting-edge research presented by a world-leading scientist whose work continues to define the foundations of computer science.
To register for the lecture, please complete the application form by April 26!
