×

# Dijkstra's algorithm

 0 1 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 1★arpit728 683●15●62 accept rate: 10%

 0 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 42●4 accept rate: 9% @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) 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) @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 community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×1,197
×164
×125

question asked: 09 Jan '16, 12:29

question was seen: 1,482 times

last updated: 10 Jan '16, 13:26