1

The following is an example of a directd graph with negative-weight edges for which Dijkstra's algorithm produces incorrect answers:

enter image description here

Applying the Dijkstra's algorihm, we get the following:

enter image description here

The path that we get from s to w is not the shortest. Therefore, we don't get right results.

How could we justify for the general case why we cannot apply the Dijkstra's algorithm on directed graphs with negative-weight edges?

Mary Star
  • 375
  • 7
  • 27
  • move to math.stackexchange.com : not a programming question – ivan_pozdeev Jan 19 '15 at 17:36
  • Dijkstra's algorithm works only on graphs with non-negative edge weights. Use bellman ford for graphs that have negative edge weights. – Nikunj Banka Jan 19 '15 at 17:37
  • 1
    To justify, why an algorithm is not applicable, one example instance, that makes the algorithm fail, is enough. – Sirko Jan 19 '15 at 17:39
  • There are about 5 questions in the "related questions" that ask this exact question. But you seem to have already justified it by finding a counter-example, so what is your question? – Mark Peters Jan 19 '15 at 17:39
  • @MarkPeters I wanted to know how it could be justified, without the use of a counter-example. – Mary Star Jan 19 '15 at 17:57

0 Answers0