You are not logged in. Please login at www.codechef.com 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

1★arpit728
6831562
accept rate: 10%


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

link

answered 10 Jan '16, 20:44

raja44ever's gravatar image

3★raja44ever
126128
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.

link

answered 10 Jan '16, 22:38

likecs's gravatar image

6★likecs
3.7k2279
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,197
×164
×125

question asked: 10 Jan '16, 15:42

question was seen: 910 times

last updated: 10 Jan '16, 22:38