×

# correctness of dijkstra's algorithm

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

 0 See dijkstra's algorithm explanation and help yourself for it's proof answered 10 Jan '16, 20:44 126●1●2●8 accept rate: 15% I have already understood this. (10 Jan '16, 21:53) arpit7281★
 0 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 6★likecs 3.7k●22●79 accept rate: 9%
 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: 10 Jan '16, 15:42

question was seen: 910 times

last updated: 10 Jan '16, 22:38