Faculty Spotlight: “Beating Bellman-Ford: Faster Single-Source Shortest Paths with Negative Weights” (Jeremy Fineman)
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 results 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 talk will give an overview of the algorithm with the aim of highlighting the key insights. It also serves as an example of what research on graph algorithms looks like today.
A reception will follow the talk.
This work received a best paper award at the 2024 ACM Symposium on Theory of Computing (STOC).