2
$\begingroup$

I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.

For the given below graph

enter image description here

What should be the Cost to reach Node G from Source Vertex A?

I was getting 2, as vertex E is the last processed vertex and when it was being processed

$E.d=9,(E,G)=-7$ so $G.d=2$ changed.

Some implementation of Dijkstra says that once a vertex v has been relaxed, then it's estimated $v.d$ is never changed.

Like here

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Here $v.d$ is changed only when sptSet[v] for that vertex is false, means that vertex was not processed before.

But CLRS says that for each vertex U that belongs to queue and results from U=EXTRACT_MIN(Q), we relax all edges leaving U.

enter image description here

So, If I follow the implementation of Dijsktra of what is given in CLRS, I get cost of 2 to reach node G from source Vertex A.

Please guide what should be correct.I am really confused about it.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

The article on Dijkstra's algorithm at GeekForGeeks say "Dijkstra’s algorithm doesn’t work for graphs with negative weight edges in general."

Introduction to Algorithms by Corman et al. says "Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph for the case in which all edge weights are nonnegative."

As explained in the linked question and answer and as OP has found, the general proof of the correctness of Dijkstra's algorithm will fail if there are negative edges, hence discussing Dijkstra on graphs with negative weight edges doesn't make sense.

I would advise you to stay away from Dijkstra’s algorithm when a graph that has negative weights appears. It might work in some cases, but it may lead you into troubles that will be avoided if you apply Bellman–Ford algorithm or Floyd–Warshall algorithm.

By the way, the shortest distance from $A$ to $G$ is 2.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The shortest path is indeed two, but the question is - what will be the cost calculated if we run Dijkstra on it? Multiple sources say that once the cost to a path is updated, it's never changed again. However, CLRS doesn't say anything about it - it simply says that once we reach a node, we relax all the edges going out from it. So in this case, when we reach $E$, the cost till that point is two and if we use the edge $EG$, we'll get the shortest path as two. $\endgroup$
    – Gokul
    Commented Nov 19, 2018 at 18:32
  • $\begingroup$ Let us make it clear first, in general, Dijkstra's algorithm is NOT defined in the case when there is an edge with a negative weight. So a discussion on its behavior on such graphs is not considered much meaningful. $\endgroup$
    – John L.
    Commented Nov 19, 2018 at 18:36
  • $\begingroup$ Okay, if I understood it clearly - the proof of Dijkstra relies on the fact that once we have found the shortest path to a node, there exists no other path which is shorter than the one we've found. This proof will fail if there are negative edges, hence discussing Dijkstra on graphs with negative weight edges doesn't make sense? $\endgroup$
    – Gokul
    Commented Nov 19, 2018 at 18:39
  • $\begingroup$ In the case of graphs with nonnegative weights, both "once the cost to a path is updated, it's never changed again" and "once we reach a node, we relax all the edges going out from it" are right. They complement each other. There is no contradiction between them. $\endgroup$
    – John L.
    Commented Nov 19, 2018 at 18:39
  • 1
    $\begingroup$ "This proof will fail if there are negative edges, hence discussing Dijkstra on graphs with negative weight edges doesn't make sense." Exactly! $\endgroup$
    – John L.
    Commented Nov 19, 2018 at 18:40

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