Finally, a Fast Algorithm for Shortest Paths on Negative Graphs - Quanta Magazine

The story begins in 1956, when the Dutch computer scientist Edsger Dijkstra developed a fast algorithm to find shortest paths on a graph with only positive weights.

In the summer of 2021, two computer scientists who’d become colleagues at the University of Copenhagen — Danupon Nanongkai and Christian Wulff-Nilsen — were searching for a topic for a joint research project.

Inspired by past work in which Bernstein and Wulff-Nilsen had collaborated with Probst Gutenberg, they developed a fracturing procedure for directed graphs analogous to low-diameter decomposition.

So the fracturing technique enabled the three researchers to reduce any directed graph to a combination of two special cases — DAGs and tight clusters — that were each easy to handle.

That algorithm, developed by Probst Gutenberg and five other researchers, addressed a more general problem called minimum-cost flow, in which the goal is to optimize transport through many paths in parallel, and each edge has a maximum capacity as well as an associated cost.

The team working on minimum-cost flow developed their general-purpose fast algorithm using an intricate synthesis of combinatorial and continuous optimization techniques that makes it unwieldy in practice, at least currently.