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


correctness of dijkstra's algorithm

Can anyone explain the correctness of dijkstra's algorithm in detail, I referred to some sources for it's proof but I didn't understand.

asked 10 Jan '16, 15:42

arpit728's gravatar image

accept rate: 10%

See dijkstra's algorithm explanation and help yourself for it's proof


answered 10 Jan '16, 20:44

raja44ever's gravatar image

accept rate: 15%

I have already understood this.

(10 Jan '16, 21:53) arpit7281★

The only think where we can apply dijkstra's algorithm is where the weights of the edges are positive. To minimise the sum of x positive integers from a set of n positive integers is same as choosing the set of smallest x numbers form the set of n numbers. This technique is used for dijkstra's algorithm where we first greedily assign the smallest weight possible to any vertex from the source first and then build on from there repeating the algorithm till checking is done by all nodes.

Actually, if the edge weights were negative also, we apply Bellman ford algorithm which actually is and DP algorithm.


answered 10 Jan '16, 22:38

likecs's gravatar image

accept rate: 9%

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: 10 Jan '16, 15:42

question was seen: 910 times

last updated: 10 Jan '16, 22:38