-3

This is not another duplicate of question, trying to understand, why Dijkstra can't work with negative weights. I know why, but in some special case's, it will work with negative weights and I'm trying to found them.

So, in some case, Dijkstra can work correctly with graphs with negative weights, but I can't find example. Does anyone know graph, that will working?

TheColloto
  • 31
  • 8
  • Well Dijkstra if implemented in a straightforward way (everytime a node is relaxed, it is added to the PQ) will always work, unless there is a negative cycle reachable from the source. But the runtime guarantees for the non-negative case do not hold because a node can be processed more than once and the algorithm essentially becomes bellmand-ford – Niklas B. Jan 29 '16 at 20:57
  • @NiklasB. using Dijkstra each node is processed only once. Negative weight edges can throw off the calculation even when there are no negative cycles. That's why, in general, negative weights don't work. Perhaps you're thinking of Johnson's algorithm? https://en.wikipedia.org/wiki/Johnson%27s_algorithm – Erick G. Hagstrom Jan 29 '16 at 21:19
  • @ErickG.Hagstrom There's different formulations of the algorithm. In practice, if you use a priority queue, it makes sense to not explicitly keep track of what nodes you already finalized, so you can *in theory* relax finalized nodes again, but that will never happen on non-negative graphs. It can happen with negative weights, but that doesn't hurt correctness (if there is no negative cycle). Maybe I'm stretching the notion of "Dijkstra's algorithm" a bit here – Niklas B. Jan 29 '16 at 21:24
  • @NiklasB. Ok, sure, but I'd argue that is no longer Dijkstra. It's something else. In particular, you lose the big-O associated with Dijkstra since you can visit each vertex an arbitrary number of times. – Erick G. Hagstrom Jan 29 '16 at 21:28
  • Yep, but only with negative weights, which was my point. You could call it "Bellman-Ford with priority queue", but really it's just Dijkstra at heart, and it's pretty fast in real-world scenarios where you don't have the worst kind of input but maybe only a few negative edges – Niklas B. Jan 29 '16 at 21:31
  • Ah, ok, I understand where you're coming from now. Essentially you're saying that, using an appropriate priority queue formulation, the algorithm should _work (i.e. find the shortest path)_ with negative weights, but without Dijkstra's big-O. Gotcha. – Erick G. Hagstrom Jan 29 '16 at 21:35
  • Possible duplicate of [Negative weights using Dijkstra's Algorithm](http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm) – Erick G. Hagstrom Jan 29 '16 at 21:38

2 Answers2

3

In fact any graph which has negative weights only on the edges originating at start will work. The problem with negative weights is that they can cause the algorithm to "miss" a lowest-weight vertex because it gets its lower weight "later". So

| begin | end | weight |
|   s   |  1  |   -1   |
|   s   |  2  |   -2   |
|   1   |  3  |    1   |
|   2   |  3  |    1   |
|   3   |  t  |    1   |

should present no practical trouble to a Dijkstra.

One can generalize that to a stronger statement: any graph that correctly computes the weight of a vertex prior to it being evaluated by Dijkstra will be correctly handled by Dijkstra retaining Dijkstra's time performance.

Erick G. Hagstrom
  • 4,873
  • 1
  • 24
  • 38
0

A trivial example such that Dijkstra works fine with negative weight would simply be:

s -(-1)-> t

If you run Dijkstra's algorithm on this graph from source s, it will discover t as the closest neighbor and choose that one, and then we constructed the right shortest path tree.

Andrew Au
  • 812
  • 7
  • 18