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.
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.
I have already understood this.