Hello folks,
I am trying to understand the dijkstras algorithm from long time, I referred to many tutorial(Including top coder) but I am not getting its concept.
Can any one explain it from the scratch.
Please explain it’s proof of correctness also.
These videos sum it up pretty well
As for the code, i use the algorithm using an std::set instead of an std::priority_queue(you can use either).
The topcoder tutorials mention both the ways(using set and priority_queue).
TopcoderTutorials (this tutorial assumes that you use C++)
you can also refer to CLRS chapter of shortest path graph algorithms where the proofs are explained really well.
@tanmay_sachan Initially array d hold the infinity for all the vertices, so what basis we insert this vertices in priority queue.
Hey, know a non C++ 11 way to erase an element of a set of pairs?
Say, in a set of pairs called s, I want to erase the pair (2,5)
We could write s.erase({2,5}) but that’s a feature specific to C++11.
Thanks a lot sarvagya3943 
@sandy999
How does that pair thing came into picture, I was asking something else. I didn’t get you.
@arpit728 We initialise the source distance to zero and push it first . Then we pop the node with least distance from the source till now and visit its neighbours and push those neighbours which we could update(distance[neighbour]>distance[node]+1) . Read the topcoder tutorials mentioned above.
@sarvagya I have referred CLRS book, in the clrs book they added all the vertices to the priority queue first then popped the minimum one, and updated the d’s if it can be improved.
But I am not getting that initially d values are infinite for every vertex except the source vertex, now after this, when in first iteration when the source will be popped after that d’s of its adjacent will be updated if possible. But now how heap ordering will be maintained.