How do you find the shortest path between two points?
Consider the problem of finding the shortest path from location A to location B.
To solve this task, we could simply list all the paths that would allow us to reach point B starting from A and finally select the shortest one. While this is a valid solution, the computational cost of this proposal grows exponentially as more roads and locations connect A and B. This means that if a better solution to this problem has not been found, Tom-Toms such as we know that today would never have existed.
Fortunately, mathematicians like Dijkstra already solved this problem in the 1950’s. In fact, if we imagine a graph where the vertices represent the various cities and the edges represent the streets. In addition, the weights of the edges are represented by the tolls/distances. There are several algorithms that allow us to solve this problem with a much lower computational cost than the exponential one.
Dijkstra’s algorithm, despite being greedy, is able to obtain the optimal solution with the lowest possible computational cost. This is true, however, only under certain conditions.
In fact, Dijkstra’s algorithm returns:
- The optimal solution only in the absence of negative weight edges
- A solution (maybe not the optimal one) in the presence of edges with negative weight
- No solution with a negative weight cycle in the graph
The Bellman-Ford algorithm is able to overcome the limitations of Dijkstra’s algorithm.
As a result of applying relaxation (i.e. a temporary relaxation of constraints) more than once on each edge, but the computational cost increases significantly.
Thus, until now, there was no-algorithm capable of finding the shortest path on graphs with negative weights with a computational cost close to the theoretical optimum.
Finally, a group of researchers discovered a very simple but super-efficient algorithm for shortest paths on negative graphs.
The idea is mainly based on a variant of the technique called low-diameter decomposition. This approach splits the graphs into a set of strongly connected clusters using a random process to eliminate just a bunch of edges. This procedure repeats until the clusters at the innermost level become connected as closely as possible.
With the graph completely broken down, it was possible to identify clusters without much concentrated negativity and quickly find the shortest paths through each part of the graph. Finally, the algorithm adds the removed edges back and recalculates the shortest paths.
This new algorithm almost matches the speed that positive-weight algorithms achieved so long ago.
That said, I highly recommend you take a look at the paper (2203.03456.pdf (arxiv.org)) detailing how they solved this problem. If (like me) you are not super familiar with these concepts, I recommend reading the article (Finally, a Fast Algorithm for Shortest Paths on Negative Graphs | Quanta Magazine) from which I took inspiration.