[HN Gopher] Negative-weight single-source shortest paths in near...
___________________________________________________________________
Negative-weight single-source shortest paths in near-linear time
Author : Anon84
Score : 110 points
Date : 2023-01-22 16:41 UTC (6 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| gregfjohnson wrote:
| How does this compare to the classic Bellman-Ford algorithm and
| subsequent improvements by Yen and Bannister&Eppstein?
| Sniffnoy wrote:
| I mean, the runtimes are right there in the abstract; this is
| pretty easy to compare. Bellman-Ford takes time Theta(|V||E|),
| and as best I can tell the improvements you mention don't
| change that, they're just constant-factor improvements. As
| opposed to this algorithm being O(|E|*log(|V|)^8*log(W)), where
| W is the largest absolute value of a negative edge.
|
| The abstract of this paper even compare the runtime to the
| state of the art, and what it compares to isn't Bellman-Ford or
| the improvements you mention; there had already been asymptotic
| improvements on those.
| xiphias2 wrote:
| Another paper with no open source implementation :(
|
| I loved it that it's possible (just like the min cost flow
| improvements), but it's just too long for me to understand and
| implement it.
| vsskanth wrote:
| Not very knowledgeable but are there any implications for path
| planning for self driving cars ?
| extropy wrote:
| For most use cases shortest path is super simple and fast
| problem on modern PCs. So might be useful on extra large
| synthetic networks. Neural nets?, Trading logs?, Image
| processing?
|
| Also negative weights are rare in real life applications. And
| def not in what you would consider normal path planning.
| repsilat wrote:
| For path finding heuristic methods give "sub-linear" time
| usually (if you have a pre-processed unchanging network with
| random access and amortize its construction over many queries).
| A-star is the old school one, but folks use fancier methods
| today. In a server farm linear time is too slow, basically.
|
| Interestingly, on a vehicle just doing Dijkstra's for within-
| city pathfinding is probably fine though if you've optimised
| the constant factors down. Likely no negative costs.
| throw827474737 wrote:
| None, very irrelevant and where it applies very minor problem
| vs all the others ;)
| dataflow wrote:
| What are some applications of this problem (SSSP with negative-
| weight edges)? This looks awesome but I'm not sure where I would
| want to use it.
| DropPanda wrote:
| One application of negative weights in a cost graph could be
| energy consumption for battery electric vehicles. Downhill,
| regenerative breaking can result in a net increase of battery
| charge.
| bertman wrote:
| Quanta article about the paper, discussion from 3 days ago:
|
| https://news.ycombinator.com/item?id=34439701
| [deleted]
| oh_sigh wrote:
| Is there an intuitive explanation for how a log^8 ends up in the
| algorithm? Why not log^4 or 16?
| sitkack wrote:
| Can someone ELI12? How big of a deal is this for real world
| applications?
|
| Presentation by Aaron Bernstein (coauthor) on the paper
| https://www.youtube.com/watch?v=Bpw3yqWT_d0
|
| Presentation by Danupon Nanongkai (coauthor) on the paper
| https://www.youtube.com/watch?v=awvBpvlbG1M
|
| Implementation in Java https://github.com/nevingeorge/Negative-
| Weight-SSSP
| tylerhou wrote:
| No comment on how useful this is for real world applications.
| But here is a technique of the algorithm. Most of my knowledge
| is from CS 270, where this was taught last week. (The course
| notes are public, the lecture is not.)
| https://cs270.org/spring23/lec/
|
| A naive attempt at adapting Dijkstra's to graphs with negative
| weight edges is to add a constant bias to every edge weight to
| make all weights positive, then run Dijkstra's. But that
| doesn't work because it changes the ordering of paths (wrt.
| cost) if their lengths differ. A path with length one will have
| its cost increased by B, while a path with length 100 will have
| its length increased by 100 * B. If the length-100 path was
| cheaper before adding the bias, after adding it bias it can be
| more expensive. So path ordering is not preserved.
|
| But that idea, modified slightly, is not too far off a
| technique that works. Instead of adding a weight to each edge,
| the technique is to add a weight to each vertex (call this
| phi(v)) and modify each edge (u, v)'s weight to w(u, v) +
| phi(u) - phi(v). It turns out that modifying each edge's weight
| in this way preserves the ordering of paths that start from s
| and end at t. Consider a path s -> a -> b -> t; its new weight
| under w_phi is: w(s, a) + phi(s) - phi(a) +
| w(a, b) + phi(a) - phi(b) + w(b, t) + phi(b) - phi(t)
| = phi(s) + w(s, a) + w(a, b) + w(b, t) - phi(t)
|
| Notice how phi(a) and phi(b) cancel each other out. In other
| words, any path from s to t's weight will be changed by
| _exactly_ phi(s) - phi(t), which is a constant! Therefore, the
| ordering of paths under cost is preserved under this new weight
| function (weights modified by phi).
|
| This technique, called "price functions" is not novel -- it has
| been known from the 70's. The paper's main contribution is how
| to discover price functions very efficiently. The main way the
| paper does this as follows: first, decompose the graph into
| smaller strongly connected components (SCCs) whose paths have a
| "low" number of negative edge weight graphs by removing some
| small subset of edges (low diameter decomposition, or LDD).
| Second, recursively find a phi function that makes all edges in
| the interiors of these SCCs have positive weight. Third, modify
| that phi (since phis compose additively) for the DAG induced by
| the SCC decomposition: "fixup" weights of edges that cross from
| one SCC into another. Finally, modify that phi again to account
| for the edges that were removed from the graph. (This last part
| is usually "slow," but it turns out that it is fast because of
| the LDD algorithm tends to only remove a small number of edges
| in any path.)
|
| Glossed over a lot of things, and probably not completely
| accurate -- see the lecture notes or the paper for the real
| analysis.
| hammock wrote:
| This article helped me (I'm not a math guy at all, just a quick
| learner)
|
| https://algs4.cs.princeton.edu/44sp/
|
| Read the top section then the first answer in the Q&A at the
| bottom.
|
| Basically the problem is to find the least-cost (shortest) path
| across a graph of nodes from point a to point b, but the best
| algorithm we have (Djikstra's) runs in exponential time in the
| worst case when there are some negative edge weights (see
| context below). This guy found an algorithm that runs must
| faster, in near-linear time.
|
| Context that is helpful is to think of edge weights not as
| distances, but as time or cost (this allows negative weights).
| Imagine a process workflow or something.
|
| Another helpful context that emerges from this is "negative
| cycle" which is an endless loop of negative weight edges
| (therefore asking an algorithm to find the "shortest" lowest
| weight path from one point to another that includes that cycle
| will fail). You can have negative weights without negative
| cycles though
| ithinkso wrote:
| > but the best algorithm we have (Djikstra's) runs in
| exponential time in the worst case
|
| Dijkstra doesn't handle negative weights so in that case you
| can use Ford-Bellman. It's slower than Dijkstra but far from
| exponential - O(VE) or something like that.
| [deleted]
| hammock wrote:
| > Dijkstra doesn't handle negative weights
|
| I took this straight from the Q&A I referenced in my link:
|
| _Q. Does Dijkstra 's algorithm work with negative weights?
| A. Yes and no. There are two shortest paths algorithms
| known as Dijkstra's algorithm, depending on whether a
| vertex can be enqueued on the priority queue more than
| once. When the weights are nonnegative, the two versions
| coincide (as no vertex will be enqueued more than once).
| The version implemented in DijkstraSP.java (which allows a
| vertex to be enqueued more than once) is correct in the
| presence of negative edge weights (but no negative cycles)
| but its running time is exponential in the worst case. _
| thaumasiotes wrote:
| > The version implemented in DijkstraSP.java (which
| allows a vertex to be enqueued more than once) is correct
| in the presence of negative edge weights (but no negative
| cycles)
|
| This is a strange parenthetical. No shortest-path
| algorithm can be correct in the presence of a negative
| cycle; the concept of "shortest path" does not apply to
| such a graph.
| ghusbands wrote:
| I suspect it's to make clear to the peanut gallery that
| there is indeed a valid shortest path in the tests they
| were doing.
| munchler wrote:
| Wouldn't a negative cycle be a good thing? You could drive
| the total cost down as low as you want before exiting the
| loop.
| londons_explore wrote:
| Yes, but the 'lowest' cost path is then travel to cycle, go
| round loop infinity times, and then go to destination.
| vecter wrote:
| Negative cycles are bad for the exact reason you said. Not
| "bad" from the perspective of "let's lower the cost as much
| as possible", but "bad" from the perspective that it
| violates certain assumptions of Dikjstra's algorithm which
| leads it to produce incorrect results.
|
| When have a negative weight cycle, you can drive down the
| cost to be arbitrarily low by running through that cycle as
| many times as you'd like. What does "shortest path" or
| "lowest cost path" mean in this context then?
|
| More info:
| https://stackoverflow.com/questions/13159337/why-doesnt-
| dijk...
| sitkack wrote:
| I have seen this in video games where there is some
| resource that respawns too quickly and the players just
| end up cycling back to the powerup every n-seconds. Easy
| to get stuck in a local minimum.
| kzrdude wrote:
| It creates a new situation you'll have to handle. If it's
| assumed the shortest path is finite, how many steps should
| it maximally take, etc? In many problem settings a negative
| cycle would indicate the model is broken, and you'd want to
| know that.
| sitkack wrote:
| The video presentation from the author is approachable even
| for a non-domain expert. It looks like this has pretty broad
| applicability to applications in chemical processes,
| scheduling, logistics (pick ups and drop offs along the
| route), re-fueling, etc.
|
| I think @DropPanda gave a great example of regenerative
| charging in an EV.
|
| In the video the author does use cost/price-function
| terminology.
|
| Djikstra doesn't handle negative weights, Bellman-Ford is
| optimal for positive edge only. This apparently is also
| easier to parallelize.
|
| The Quanta article mentioned below is _excellent_
| https://www.quantamagazine.org/finally-a-fast-algorithm-
| for-...
| spritefs wrote:
| > Bellman-Ford is optimal for positive edge only.
|
| ???
|
| CLRS says it takes negative weight edges (just no negative
| cycles) and does it in O(VE). I have no idea where you're
| getting this from
| rhn_mk1 wrote:
| What are negative weights good for?
| hammock wrote:
| Imagine a step in a process that saves you cost/time
| (negative edge weight) if you do it at one point, but adds
| cost/time (positive edge weight) if you do it at a
| different point
| wjholden wrote:
| An interesting use case is if you want to need to apply
| graph algorithms to a problem where edges multiply instead
| of adding. Just take the log of the multiplier and now your
| multiplication problem is addition.
|
| For example, suppose you cannot exchange the US dollar for
| the Russian ruble. You have to go through some path such as
| USD -> EUR -> RUB. Of all possible paths, which one gives
| you the most favorable exchange? You can use Bellman-Ford
| to find out.
| thaumasiotes wrote:
| > For example, suppose you cannot exchange the US dollar
| for the Russian ruble. You have to go through some path
| such as USD -> EUR -> RUB. Of all possible paths, which
| one gives you the most favorable exchange?
|
| Why is it necessary to assume I can't exchange dollars
| directly for rubles? If that is possible, wouldn't I
| still want whatever path has the most favorable exchange
| rate?
| [deleted]
| rcme wrote:
| It doesn't seem like the shortest path on a graph with
| negative cycles would be defined for any algorithm.
| hammock wrote:
| Right
| tejtm wrote:
| "single source shortest acyclic path" would be the
| closest term that could make sense
| rhelz wrote:
| If you want to interview for any job at an FPGA company, please
| read this paper first :-). I majorly blew an interview question
| which this paper would have helped me ace.
| jldugger wrote:
| Interesting, I'm not sure I see the link. Is SSSP relevant in
| programming FPGAs optimally?
| gigatexal wrote:
| I really do need to up my maths game so I can take advantage of
| all these papers and their new and novel solutions to things like
| this. Otherwise I'll have to wait until someone throws it into a
| library :(
| bee_rider wrote:
| They look to have distilled things down to a pair of Algorithms
| in pseudocode, if you want to take a swing at implementation-
| for-understanding.
| evouga wrote:
| Well, this is a very interesting theoretical breakthrough, but
| it remains to be seen how it benchmarks in practice. The
| constant and log factors might be steep for practical inputs.
___________________________________________________________________
(page generated 2023-01-22 23:00 UTC)