Communications of the ACM
Finally, a Fast Algorithm for Shortest Paths on Negative Graphs
The new approach uses decades-old mathematical techniques, eschewing more sophisticated methods that have dominated modern graph theory research.
Credit: Samuel Velasco/Quanta Magazine
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. Consider, for instance, a delivery driver who must balance the cost of gas and tolls (represented by positive weights) against income from transporting packages (represented by negative weights). In such cases, the fastest known shortest-path algorithm doesn't work. For decades, fast algorithms for finding shortest paths on negative-weight graphs have remained elusive.
Now a trio of computer scientists has solved this long-standing problem. Their new algorithm, which finds the shortest paths through a graph from a given "source" node to every other node, nearly matches the speed that positive-weight algorithms achieved so long ago.
From Quanta Magazine
View Full Article
No entries found