N
N
NightFantom2015-05-11 17:13:39
Algorithms
NightFantom, 2015-05-11 17:13:39

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:
009a58ebe9f343439b7ed8e5d07af5aa.png
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

2 answer(s)
D
Dmitry Filimonov, 2015-05-11
@DmitryPhilimonov

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.

T
throughtheether, 2015-05-11
@throughtheether

After executing the algorithm, we get that the shortest distance to the second vertex is 10.
This is not clear, please explain your point.
Initially (we start from vertex 1), vertex 1 has an associated number (path length, d[1]) 0, it is also in the set of visited vertices. The length of the path to other vertices is infinity.
For all edges connecting the sets of visited and unvisited vertices (i.e. for edges 1-2 and 1-3) consider the sums d[u]+w(u,v), where d[u] is the length of the shortest path to the vertex u, w(u,v) - weight (length) of the corresponding edge. The minimum sum is observed for the edge 1-3 corresponding to the path 1,3. Add 3 to visited.
Again, for all edges connecting the sets of visited and unvisited vertices (i.e., for edges 1-2, 3-2), we consider the corresponding sums (10 and 2), choose the minimum, i.e. add vertex 2 to the path (and to the set of visited vertices) that looks like 1,3,2. Since there are no unvisited vertices left, we terminate the algorithm.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question