Dr Robert Tarjan on the Enduring Power of Dijkstra’s Algorithm
As we celebrate 50 years of computing education at NUS, the School of Computing welcomed Dr Robert Tarjan, Turing Award laureate and one of the most influential theorists in computer science, for a special Distinguished Speaker Seminar titled “Is Dijkstra’s Algorithm Optimal?”
In his talk, Dr Tarjan revisited one of the most iconic algorithms in computing – Dijkstra’s shortest-path algorithm – and shared new insights from recent research that tackles a long-standing open question in the field: Can one algorithm be optimal for all graphs?
His answer, based on collaborative work published in 2024–2025, is both elegant and surprising:
Dijkstra’s algorithm is universally optimal for determining the order in which distances are discovered.
This means that across all types of graphs, no comparison-based algorithm can consistently outperform Dijkstra’s method. The result has attracted international attention, including coverage by Quanta Magazine, and was recognised with a Best Paper Award at a leading theory conference.
Dr Tarjan also reflected on the enduring appeal of “simple but powerful” algorithms – solutions that remained clear for practitioners to implement, even when the underlying analysis is complex.
Post-Talk Q&A Highlights
After the seminar, we spoke briefly with Dr Tarjan to gather his reflections.
On emerging frontiers in computer science
“We’re seeing beautiful progress where continuous methods – like linear programming and interior-point techniques – give strong results for problems we’ve traditionally treated as discrete. Understanding how these two worlds interact is a fascinating frontier.”
On what he hopes researchers and students took away
“Don’t be afraid to explore interesting problems. And when you don’t know the answer, consider both possibilities. Look at the problem from more than one angle.”
On advice for NUS Computing students
“Learn as much mathematics as possible.”
Celebrating 50 Years of Computing Education
Dr Tarjan’s visit offered a timely reminder of how far computing has come, and how foundational ideas continue to shape the field’s future. As NUS commemorates 50 years of computing education, his message serves as both inspiration and challenge: to stay curious, think broadly, and pursue clarity.
