Why does Dijkstra's algorithm work?
I understand what Dijkstra's algorithm is, but I don't understand why it works.
When selecting the next vertex to examine, why does Dijkstra's algorithm select the one with the smallest weight? Why not just select a vertex arbitrarily, since the algorithm visits all vertices anyway?
Solution 1:
You can think of Djikstra's algorithm as a water-filling algorithm (i.e. a pruned breadth-first search). At each stage, the goal is to cover more of the whole graph with the lowest-cost path possible. Suppose you have vertices at the edge of the area you've filled in, and you list them in terms of distance:
v0 <= v1 <= v2 <= v3 ...
Could there possibly be a cheaper way to get to vertex v1? If so, the path must go through v0, since no untested vertex could be closer. So you examine vertex v0 to see where you can get to, checking if any path through v0 is cheaper (to any other vertex one step away).
If you peel away the problem this way, you're guaranteed that your distances are all minimums, because you always check exactly that vertex that could lead to a shortest path. Either you find that shortest path, or you rule it out, and move on to the next vertex. Thus, you're guaranteed to consume one vertex per step.
And you stop without doing any more work than you need to, because you stop when your destination vertex occupies the "I am smallest" v0 slot.
Let's look at a brief example. Suppose we're trying to get from 1 to 12 by multiplication, and the cost between nodes is the number you have to multiply by. (We'll restrict the vertices to the numbers from 1 to 12.)
We start with 1, and we can get to any other node by multiplying by that value. So node 2 has cost 2, 3 has cost 3, ... 12 has cost 12 if you go in one step.
Now, a path through 2 could (without knowing about the structure) get to 12 fastest if there was a free link from 2 to 12. There isn't, but if there was, it would be fastest. So we check 2. And we find that we can get to 4 for cost 2, to 6 for 3, and so on. We thus have a table of costs like so:
3 4 5 6 7 8 9 10 11 12 // Vertex
3 4 5 5 7 6 9 7 11 8 // Best cost to get there so far.
Okay, now maybe we can get to 12 from 3 for free! Better check. And we find that 3*2==6 so the cost to 6 is the cost to 3 plus 2, and to 9 is plus 3, and 12 is plus 4.
4 5 6 7 8 9 10 11 12
4 5 5 7 6 6 7 11 7
Fair enough. Now we test 4, and we see we can get to 8 for an extra 2, and to 12 for an extra 3. Again, the cost to get to 12 is thus no more than 4+3 = 7:
5 6 7 8 9 10 11 12
5 5 7 6 8 7 11 7
Now we try 5 and 6--no improvements so far. This leaves us with
7 8 9 10 11 12
7 6 8 7 11 7
Now, for the first time, we see that the cost of getting to 8 is less than the cost of getting to 7, so we had better check that there isn't some free way to get to 12 from 8. There isn't--there's no way to get there at all with integers--so we throw it away.
7 9 10 11 12
7 8 7 11 7
And now we see that 12 is as cheap as any path left, so the cost to reach 12 must be 7. If we'd kept track of the cheapest path so far (only replacing the path when it's strictly better), we'd find that 3*4 is the first cheapest way to hit 12.
Solution 2:
Dijkstra's algorithm picks the vertex with the least path cost thus far, because a path through any other vertex is at least as costly as a path through the vertex with the least path cost.
Visiting any other vertex, therefore, if it is more costly (which is quite possible) would necessitate visiting not only that other vertex, but also the one with the least path cost thus far, so you would have to visit more vertices before finding the shortest path. In fact, you would end up with the Bellman-Ford algorithm if you did that.
I should also add that the vertex doesn't have a weight, it is the edge that has a weight. The key for a given vertex is the cost of the shortest path found thus far to that vertex from the source vertex.
Solution 3:
The reason why Dijsktra's algorithm works the way it does is in part because it exploits the fact that the shortest path between node u and w that includes point v also contains the shortest path from u to v and from v to w. If there existed something shorter between u to v, then it wouldn't be the shortest path.
To really understand why Dijkstra's algorithm works, look into the basics of dynamic programming, sounds hard but it's really pretty easy to understand the principles.