Computer science pioneer Edsger Dijkstra’s algorithms are widely used due to their efficiency, but they can fail to provide accurate answers when requirements change. Negative weights in a network can confound Dijkstra’s shortest-path algorithm, which does not consider the potential benefit of high weights combined with negative weights. In a recent breakthrough, researchers developed a combinatorial solution to the single-source, shortest-path problem with negative weights. By dividing the graph into clusters of low-diameter subgraphs and reworking the weights using price functions, they were able to process the graph using Dijkstra’s algorithm, resulting in near-linear performance. The technique may also be applicable to other directed-graph problems.
https://cacm.acm.org/news/275684-historic-algorithms-help-unlock-shortest-path-problem-breakthrough/fulltext