Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

In algorithms, as in life, negativity can be a drag. Consider the problem of finding the shortest path between two points on a graph — a network of nodes connected by links, or edges. Often, these edges aren’t interchangeable: A graph could represent a road map on which some roads are slower than others or have higher tolls. Computer scientists account for these differences by pairing each edge…

Source