You are not logged in. Please login at to post your questions!


Dijkstra's algorithm


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.

asked 09 Jan '16, 12:29

arpit728's gravatar image

accept rate: 10%

edited 10 Jan '16, 13:26

These videos sum it up pretty well

Youtube- Dijkstra's Algorithm

Youtube- MITOCW Dijkstra

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.


answered 09 Jan '16, 13:35

tanmay_sachan's gravatar image

accept rate: 9%

edited 09 Jan '16, 13:47

@tanmay_sachan Initially array d hold the infinity for all the vertices, so what basis we insert this vertices in priority queue.

(09 Jan '16, 21:08) arpit7281★

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.

(09 Jan '16, 22:14) sandy9992★

@sandy999 You could always do s.erase(make_pair(2,5))

(09 Jan '16, 22:29) sarvagya39434★

Thanks a lot sarvagya3943 :)

(09 Jan '16, 22:53) sandy9992★

@sandy999 How does that pair thing came into picture, I was asking something else. I didn't get you.

(09 Jan '16, 23:19) arpit7281★

@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.

(10 Jan '16, 00:05) sarvagya39434★

@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.

(10 Jan '16, 09:05) arpit7281★
showing 5 of 7 show all
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 09 Jan '16, 12:29

question was seen: 1,482 times

last updated: 10 Jan '16, 13:26