Beating Bellman-Ford: Faster Single-Source Shortest Paths with Negative Weights

Abstract: Shortest-path problems concern finding shortest routes through a network or graph. A common application of shortest paths in our daily lives is computing driving directions, but graphs and shortest paths have wider usage. Perhaps the best studied version of the problem is the so-called single-source shortest-path (SSSP) problem. Here the input comprises (1) a directed graph with weights on edges (modeling time, distance, cost, etc.), and (2) a specified starting or source vertex. The goal is to find shortest paths from the source to all other vertices in the graph. This talk considers the most general version of the problem, where the weights on edges can be arbitrary real numbers, including both positive and negative numbers.

The classical solution for general weights, often called the Bellman-Ford algorithm, was first published in the 1950s. The Bellman-Ford algorithm is simple and easy to implement, but it is slow. There has thus been significant effort in producing faster algorithms, but those improvements all involve restricting the problem in some way. For example, there are faster algorithms for acyclic graphs, planar graphs, nonnegative weights, and integer weights. The general case of real weights on arbitrary directed graphs, however, remains a challenge. Despite the fact that Bellman-Ford dates back to the 1950s, no asymptotically faster algorithms had been discovered.

This talk presents the first asymptotically faster SSSP algorithm for real edge weights. This work received a best paper award at the 2024 ACM Symposium on Theory of Computing (STOC).

Bio: Jeremy Fineman is a Professor and the Wagner Chair of Computer Science at Georgetown University. His main research interest is in algorithm design and analysis, with a focus on data structures, parallel algorithms, memory-efficient algorithms, and scheduling. He received his Ph.D. from MIT in 2009 and did a postdoc at CMU before starting at Georgetown in 2011.