Answer the question
In order to leave comments, you need to log in
Why is Dijkstra's algorithm correct?
Hello. Guys, I'm not catching up with the correctness of Dijkstra's algorithm. There is such a graph:
After executing the algorithm, we get that the shortest distance to the second vertex is 10. Although the shortest path is 2. How so?
Answer the question
In order to leave comments, you need to log in
At the first iteration, the weight of vertex 1 is equal to 0. From it we go to the neighbors. Up to vertex 3, the weight is 1. Up to vertex 2, the weight is 10. We don’t go to vertex 1 anymore, it has a minimum weight. The next one with the smallest neighbor is 3. Choose it. The path is only one way - to 2 - and the weight is 2 (the previous weight is summed). Previously, there was a weight of 10, but since our new weight is smaller, we replace it with a smaller one. We select peak 2, and there is nowhere to go from it.
The total shortest path to vertex 2 is 2 and goes through neighbor 3 (if we remembered this during iterations). On an edge with a weight of 10, nothing will go at all in this case.
After executing the algorithm, we get that the shortest distance to the second vertex is 10.This is not clear, please explain your point.
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question