Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

Decades ago, the Dutch computer scientist Edsger Dijkstra developed a greedy algorithm that finds shortest paths between points on a graph with positive weights. But if the weights are negative, the algorithm fumbles.

Read more »