Distinguished Speaker Seminar with Prof Robert Tarjan: “Is Dijkstra’s Algorithm Optimal?”
Distinguished Speaker Seminar with Prof Robert Tarjan: “Is Dijkstra's Algorithm Optimal?”
NUS Computing is pleased to host Prof Robert Tarjan, one of the world’s most influential computer scientists and a foundational figure in algorithms research, as part of our CS50 anniversary.
Prof Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a Turing Award laureate recognised for seminal contributions that shaped modern data structures and graph theory. His work continues to influence generations of researchers and practitioners in computing and beyond.
Seminar Details
Topic: Is Dijkstra’s Algorithm Optimal?
Date: Wednesday, 26 November 2025
Time: 1:00 PM – 2:00 PM
Venue: LT15, Block AS6
Chair: Prof Seth Gilbert (Head, Computer Science)
RSVP: Please register by 25 November, 11:59 PM at https://forms.cloud.microsoft/pages/responsepage.aspx?id=Xu-lWwkxd06Fvc_rDTR-gm5x1Sp8M6RGscGRMyuul5JUQkRJQ1lTTlRJTzhGOFNHN0gwT1FWM09KQS4u&route=shorturl
(Only for NUS Faculty,Staff & Students)
About the Seminar
Dijkstra’s algorithm is one of the most enduring and widely taught algorithms in computer science. Beyond identifying shortest paths, it produces them in increasing order of length—a feature that has shaped decades of research in route planning and optimisation.
In this seminar, Prof Tarjan will discuss recent work he and his collaborators have undertaken that revisits a long-standing question: Is Dijkstra’s algorithm best possible? He will present findings that argue “yes”, alongside a brief look at alternative perspectives that suggest otherwise. The talk offers a rare window into the evolving landscape of algorithmic theory, guided by one of its most influential pioneers.
About the Speaker
Prof Robert Tarjan has held academic appointments at Cornell, Berkeley, Stanford, and NYU, and research roles at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies. He is known for pioneering many of the most efficient data structures and graph algorithms used today.
His accolades include:
- Nevanlinna Prize (1982)
- Turing Award (1986)
- Paris Kanellakis Theory and Practice Award (1999)
He is a member of the U.S. National Academy of Sciences, National Academy of Engineering, American Academy of Arts and Sciences, and the American Philosophical Society.
This seminar is part of NUS Computing’s 50th anniversary celebrations, marking five decades of academic excellence, research leadership, and contributions to Singapore’s digital future.