<story><title>Historic algorithms help unlock shortest-path problem breakthrough</title><url>https://cacm.acm.org/news/275684-historic-algorithms-help-unlock-shortest-path-problem-breakthrough/fulltext</url></story><parent_chain><item><author>ozarker</author><text>What’s an application where you’d absolutely have to have a graph with negative weights? Couldn’t you just preprocess the edges and normalize their weights?</text></item></parent_chain><comment><author>klyrs</author><text>A prototypical example today is to take battery range into account in navigation.  You charge your battery going downhill, corresponding to a negative edge weight.  If you&amp;#x27;re driving from the top of a mountain, through a valley, to the top of a hill, many of the available routes might end up with a negative cost!&lt;p&gt;Preprocessing is certainly possible, but the result is to densify the graph.  That densification can turn a sparse graph with O(n) edges into a dense graph with O(n^2) edges.  When the goal is to keep pathfinding to a nearly-linear (roughly O(vertices + edges) with log factors) runtime in the presence of negative weight edges, naive preprocessing blows the budget before you even start pathfinding.&lt;p&gt;The article at hand presents long-sought after algorithms which hit the near-linear runtime goal at the cost of a combination of clever preprocessing and a novel divide&amp;amp;conquer approach.  So yes, preprocessing, no, not &amp;quot;just&amp;quot; preprocessing.</text></comment>
<story><title>Historic algorithms help unlock shortest-path problem breakthrough</title><url>https://cacm.acm.org/news/275684-historic-algorithms-help-unlock-shortest-path-problem-breakthrough/fulltext</url></story><parent_chain><item><author>ozarker</author><text>What’s an application where you’d absolutely have to have a graph with negative weights? Couldn’t you just preprocess the edges and normalize their weights?</text></item></parent_chain><comment><author>bhl</author><text>The issue with negative weighted edges is that a cycle would result in an infinite loop when finding shortest path, compared to when all edges are non-negative, cycles can be safely skipped.&lt;p&gt;Compared to Dijkstra&amp;#x27;s original algorithm of E + V log V, naively pre-processing edges would require V^2 work assuming an edge can exist between each vertex.&lt;p&gt;Edit: the algorithm you’re describing exists btw &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.m.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Johnson%27s_algorithm&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.m.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Johnson%27s_algorithm&lt;/a&gt;</text></comment>