By Chris Edwards

Communications of the ACM,
September 2023,
Vol. 66 No. 9, Pages 10-12
10.1145/3607866
Comments

Computer science pioneer Edsger Dijkstra’s algorithms form the backbone of many computer subroutines, thanks to their elegant efficiency. However, seemingly subtle changes in requirements can lead to these often conceptually simple formulations failing to provide an accurate answer. The replacement algorithms provide the correct answers but are frequently orders of magnitude slower.

A recent breakthrough in combinatorial techniques has shown how these early algorithms can be revived.

Shortest-path problems provide good examples of the sensitivity of an algorithm to the specifics of their requirements. The underpinning for many applications from navigation to chip layout, these problems present a simple, basic proposition: Find the path through a network of directed paths that offers the lowest cost based on the weights applied to each hop. That weighting may reflect distance or delay, properties that are always positive in the physical world.

Problems start when you encounter a similar network where paths can have negative weights. “When you’re dealing with the situation when edge weights correspond to cost, negative weights are natural,” says Aaron Bernstein, assistant professor of computer science at Rutgers University, New Brunswick, NJ.

In finance, for example, there may be situations in currency or options trading where buying and selling in one sequence is more profitable than taking a different path, and these can be modeled using negative weights as long as the search algorithm is fast enough. But those negative weights can throw Dijkstra’s shortest-path algorithm for a loop.

The issue lies in the efficient greediness of the algorithm developed in the mid-1950s: It will often remove negative-weight paths from consideration. It processes each vertex in turn and does not return, so the algorithm may not consider whether a high weight combined with one that carries a negative weight might result in a lower cost than a single hop with a low weight.

A revised approach, often known as the Bellman-Ford algorithm, handles the negative-weight connections correctly, but because it relies on the ability to process nodes, it lacks the raw efficiency of Dijkstra’s technique, which completes in a time based on the sum of the number of nodes and connections. Bellman-Ford instead needs many more steps: The total is based on the product of the number of nodes and vertices.

Though computer scientists have attempted to find more efficient solutions to the problem using similar combinatorial techniques to those used in these longstanding algorithms, they failed to narrow the computational gap between them by a significant amount. Over the past few decades, greater advances were made by representing the graph as coefficients in a matrix and using the tools of linear algebra. Such techniques have proven successful for a wide range of path-related problems, not just for identifying the shortest route but for applications such as maximizing flow through a network of pipes or transportation routes, as demonstrated in a paper presented at last year’s Symposium on Foundations of Computer Science (FOCS).

Georgia Institute of Technology Ph.D. student Li Chen, working with mathematicians at Switzerland’s ETH Zurich, Stanford University, and the University of Toronto, developed a mechanism based on gradient desce