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
.