Purdue researchers advance classic graph algorithms problem with concise approach
10-20-2025
From left to right: Purdue CS Ph.D. student Yufan Huang, Professor Kent Quanrud and undergraduate student Peter Jin
A team from Purdue University is contributing new insight to one of computer science’s most enduring problems: finding single-source shortest paths in graphs with negative edge weights.
The researchers have built on decades of work to push the boundaries of what is possible. Their 4.5-page paper, accepted to the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA), presents a randomized algorithm that improves the best-known running time for the problem, long considered a staple of theoretical computer science.
The paper was authored by Ph.D. student Yufan Huang, undergraduate student Peter Jin, and assistant professor Kent Quanrud, from Purdue’s Department of Computer Science.
For more than half a century, the Bellman-Ford algorithm, running in roughly m·n time, where m is the number of edges and n is the number of vertices, stood as the standard approach for handling negative weights. In 2024, work by Fineman reduced that runtime to approximately m·n.888, sparking renewed interest in the problem and reframing it as a deeper graph-structural challenge.
The Purdue team’s contribution improves the runtime further to roughly m·n^.8 (ignoring lower-order terms). Their main conceptual idea is the notion of proper hop distances, which highlights walks containing many distinct negative-length edges and supports more effective sampling.
Quanrud credits prior work for making new progress possible. “Fineman showed there’s something nontrivial happening here,” he said. “We’re still stumbling in the dark, but we’re uncovering structure and hints. Proper hop distances are one piece of a bigger puzzle.”
Beyond the research itself, the discovery provided a memorable moment in the classroom.
“In spring 2025, I was teaching undergraduate algorithms and Peter was a teaching assistant,” he said. “When I covered Bellman-Ford, I got to tell the students that the fastest known approach was now from Purdue, and their own TA was one of the authors. The students really enjoyed it.”
The work has already continued beyond the SODA paper. In June, the team released a new preprint improving the runtime again to roughly m·n^3/4 + n·m^4/5 using a new technique they call bootstrapping hop reducers.
Their results come amid broader momentum in graph algorithms. For shortest paths with nonnegative weights, researchers have recently developed an instance-optimal variant of Dijkstra’s algorithm and an O(m log^{2/3} n) algorithm that outperforms Dijkstra on sparse graphs. In just the past five years, the field has also seen almost-linear time algorithms for maximum flow and for negative-length shortest paths with integer edge weights — many recognized with best paper awards at major theory conferences.
“It’s an exciting time for graph algorithms,” Quanrud said. “We’re just starting to see what’s possible.”
About the Department of Computer Science at Purdue University
Founded in 1962, the Department of Computer Science was created to be an innovative base of knowledge in the emerging field of computing as the first degree-awarding program in the United States. The department continues to advance the computer science industry through research. U.S. News & World Report ranks the department No. 8 in computer engineering and No. 16 overall in undergraduate and graduate computer science. Additionally, the program is ranked No. 6 in cybersecurity, No. 8 in software engineering, No. 13 in systems, No. 15 in programming languages and data analytics, and No. 18 in theory. Graduates of the program are able to solve complex and challenging problems in many fields. Our consistent success in an ever-changing landscape is reflected in the record undergraduate enrollment, increased faculty hiring, innovative research projects, and the creation of new academic programs. The increasing centrality of computer science in society, academic disciplines and new research activities — centered around foundations and applications of artificial intelligence and machine learning, such as natural language processing, human computer interaction, vision, and robotics, as well as systems and security — are the future focus of the department. Learn more at cs.purdue.edu.