This question already has an answer here:
I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.
For the given below graph
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.
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.
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.