CODEWITHSUNDEEP
graph-theorydijkstra
Pol
Pol

Reputation: 325

Dijkstra and negative weights - does the miscalculated distance matter?

I'm reading a counterexample on why Dijkstra's algo doesn't work for Graphs with negative weight and the graph given for the counterexample is:

enter image description here

However, when you run the algorithm on this graph you get the following result, so for A->D we've miscalculated the actual shortest distance (we've concluded it's 4, while in actuality it's 2), however the nodes leading to it seem to be correct after all, so what do we care?

enter image description here

We start off by picking edge {A,B}, then {B,D} so {A,D} distance = 4 at this point and the parent of D is B. Afterwards we've only had 'C' left in the queue, therefore we pick {A,C} which has weight = 5 and we update as follows, C has A as its parent, also {C,B} has weight -4, therefore B's distance from A becomes 1 and C replaces A as B's parent. Therefore, if we want the actual vertices that lead up to D we get A->C->B->D (correct), it's just the distance of D is wrong, but does it matter if we actually get the right vertices?

Upvotes: 0

Views: 38

Answers (1)

rupinderg00
rupinderg00

Reputation: 189

Actually This statement is wrong.

C has A as its parent, also {C,B} has weight -4, therefore B's distance from A becomes 1 and C replaces A as B's parent.

The algorithm first finds the unvisited vertex having minimum distance from the source and visit it. Now It will update (if possible) the distances of all the unvisited nodes in the neighborhood of the selected node. These steps are repeated till all the nodes are visited.
As B was already visited, its parent won't get updated. And If you update the parent of B, then this isn't Dikjstra Algorithm.

Upvotes: 1

Related Questions