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 with a "weight" that quantifies the cost of moving across that segment -- whether that cost represents time, money or something else. Since the 1970s, they've known how to find shortest paths essentially as fast as theoretically possible, assuming all weights are positive numbers. But on some graphs weights can be negative -- traveling along one segment can offset the cost of traversing another.