Hacker News Reader

> 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.

> 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.

> 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.

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.

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-...

> 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

>Bellman-Ford is optimal for positive edge only

What do you mean “optimal”? The Bellman-Ford algorithm gives you the shortest path, period.

What are negative weights good for?

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

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.

> 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?

It’s not. That’s the problem he’s defining. It’s a real world problem

> 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.

I don't see what this has to add over just using the weights as they are. Dijkstra's algorithm tracks the distance from a source node to a target node. There's nothing about the algorithm that says that distance must be the sum of all the edge weights along a path; if it's the product, the algorithm will work without any changes.[1] The only requirement on the distance function is that you know how to calculate d(s,t) from the two values d(s, t') and d(t', t).

[1] You'll still have problems [with Dijkstra's algorithm] if some weights are greater than 1 and some aren't, which is the exact analog of the problems that occur when distance is additive and some weights differ in sign. But that has no bearing on whether you can use multiplication directly or you need to convert it to addition.

>There's nothing about the algorithm that says that distance must be the sum of all the edge weights along a path

I think it relies on the assumption that d(a, c) >= d(a, b) + d(b, c). You could relax this of course, but then you're just back to bellman-ford algorithm.

When your distance aggregation is instead multiplicative and you allow multipliers < 1, this no longer holds.

Edit: I see your footnote already mentions this. I agree, the key point here isn't really whether things add or not, it's whether your aggregate distances are monotonically increasing or not. If they are, you can use dijkstra. If not, you have to use bellman ford or the fancier algorithms like the one in the arxiv.

You're right about the difference between Dijkstra and Bellman-Ford. But I thought the question was "why would you want negative edge weights?", and this doesn't seem like an answer to that.

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.

Yes, but the 'lowest' cost path is then travel to cycle, go round loop infinity times, and then go to destination.

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...

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.

Nit: It's not negative weight cycles that mess up Dijkstra's, it's negative weights in general.

Dijkstra's is effectively a greedy algorithm for finding shortest paths. By their very nature greedy algorithms cannot "look ahead." If there is a negative weight edge locked behind a expensive edge, Dijkstra's won't be able to see the negative weight edge until it's too late.

             10
    A -----------------> C
     \                  ^
      \  11        -15 /
       \-----> B -----/

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.

It doesn't seem like the shortest path on a graph with negative cycles would be defined for any algorithm.

Right

"single source shortest acyclic path" would be the closest term that could make sense

Nit: In a graph with negative cycles, shortest paths are still well-defined for vertices s to t if there is no path from s to a negative cycle or if there is no path from a negative cycle to t.

In the simplest case, suppose you have a graph with exactly one negative cycle that is completely isolated from the rest of the graph. The shortest paths between vertices in the negative cycle are not well-defined, but the shortest paths in the rest of the graph are well-defined.

In general, look at the meta-DAG induced by the SCC decomposition of the graph. Mark any meta-vertices whose SCC contains some negative cycle. For s, t in the original graph, the distance from s to t is well-defined iff there exists no path from s's meta-vertex to t's meta-vertex in the meta-graph that traverses through a marked meta-vertex. (Proof left to the reader.)