1
$\begingroup$

The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford algorithm can work with and detect -negative edge cycles.

However I feel a bit different, especially after coming across problem asking to build shortest path tree from node $a$ in following graph:

enter image description here

My shortest path tree after running Dijkstra came like this:

enter image description here

Then why texts say that Dijkstra need all non negative edge weights? I feel that it should be no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

Then why texts say that Dijkstra need all non negative edge weights?

Because it has to work for all cases, not only a few examples.

I feel that it should be no -ve edge weight cycle reachable from source node.

Try proving that claim and see where it leads. If you're successful, great; if not, trying to prove the opposite will fix your intuition.

See also here for a high-level argument.

The smallest example where Dijsktra fails has four nodes, no (directed) cycle at all, and no negative-value cycle:
example graph

Improve this answer
$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Raphael
    Commented Mar 24, 2018 at 10:58
  • 2
    $\begingroup$ "The smallest example where Dijkstra fails has three nodes" $s\stackrel{4}{\longrightarrow}p$, $p\stackrel{-3}{\longrightarrow}q$, $s\stackrel{2}{\longrightarrow}q$ $\endgroup$
    – Hendrik Jan
    Commented Jan 6, 2019 at 2:42
2
$\begingroup$

Raphael's answer is spot on, but let me offer some additional perspective as well.

Then why texts say that Dijkstra need all non negative edge weights?

Because we've been unable to prove it works otherwise.

In fact, imagine that negative edge-weights were allowed. In one extreme, this means that all edge weights can be negative. So we could take any graph that we want, make all weights equal to -1, and give it to the algorithm and find a shortest path between $s$ and $t$. This shortest path maximizes the length of the path (in terms of the number of edges), so we'll get a Hamiltonian path between $s$ and $t$ if it exists. But as far as we know, there is no polynomial-time algorithm for solving the problem!

Improve this answer
$\endgroup$
4
  • $\begingroup$ Came across surprising fact when watching a video. At 10:43, it shows graph with -ve edge on which Dijkstra works. At 12:01, it shows graph with -ve edge on which Dijkstra does not works. Surprising fact is: in all cases shortest path tree is formed, but the incorrectness lies in the fact that, in 2nd graph, node gets relaxed again after the iteration in which it is extracted from Q, which is not desired and considered incorrect in Dijkstra!!! This is explained at 12:54 $\endgroup$
    – RajS
    Commented Feb 2, 2018 at 9:27
  • $\begingroup$ Can you confirm that this is indeed what I was missing: shortest path tree will be formed in all graphs without -ve edge cycles, but might be that a node will get relaxed after it has been extracted from Q which is considered wrong in Dijkstra? $\endgroup$
    – RajS
    Commented Feb 2, 2018 at 9:29
  • $\begingroup$ @anir No, Dijkstra (as quoted by you never does this. Whoever does this is using the algorithm wrong. $\endgroup$
    – Raphael
    Commented Feb 2, 2018 at 10:21
  • $\begingroup$ @anir It's not at all surprising that Dijkstra will work on some graphs with negative edge weights. $\endgroup$
    – Raphael
    Commented Feb 2, 2018 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.