why the Dijkstra Algoritm does not give reliable results if there are negative e

Question

why the Dijkstra Algoritm does not give reliable results if there are negative edges?

Paper must discuss how the Dijkstra algoritm works and include these items below

Paper must give an exmple of where the Dijkstra algorithm will fail to give the right answer for negative edges

Paper must discuss the two algorithms (Bellman-Ford, Johnson) as alternatives to the Dijkstra Algorithm.

Paper must discuss Big O of Dijkstra algorithm when it is using a queue.

Paper must include at least one example of Dijksta algorithm usage in games.

Explanation / Answer

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

But with negative weights - it might not be true. For example:

Note that this is important, because in each relaxation step, the algorithm assumes the "cost" to the "closed" nodes is indeed minimal, and thus the node that will next be selected is also minimal.

The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
Without the constraint on positive numbers - the above assumption is not true.

Since we do "know" each vertex which was "closed" is minimal - we can safely do the relaxation step - without "looking back". If we do need to "look back" - Bellman-Ford offers a recursive-like (DP) solution of doing so.

Dijkstra from A will first develop C, and will later fail to find A->B->C

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.