-
Title:
Simulate this Algorithm - Intro to Algorithms
-
Description:
-
If you did this a little bit carelessly, you might say that
-
the first number that goes into E is the length of the shortest hot path from A to E,
-
which in this case would be, well there's two ways to get
-
the distance 11 to here in two hops and then another seven.
-
You might have said 18, but in fact, it won't expand D into E until it knows the shortest distance to D,
-
and the shortest distance is going to be 10 because we can go this way.
-
four plus one is five and five is 10 so it should be 17,
-
but let's actually simulate and see what happens.
-
We expand out A into C and B and once we've done that,
-
the shortest non-completed distance is the one to C so we're going to lock that down
-
and then we expand from that node C
-
There is two edges to incomplete nodes, C to D and C to B.
-
The C to B has a length of one plus length of four, we already had
-
that actually improves this one to five and a new node joins the picture, D
-
and C to D is seven on top of the four we already had for a total of 11.
-
Alright, of the non-completed nodes, B and D,
-
the one with the smallest distance is B with distance of five.
-
We can lock that down and look at the outgoing edges from B,
-
which is just this one that goes to D which had the length of five
-
plus the five we already had for a length of 11 in D, which improves D, 10
-
and this the only node hit that we can read at this point that we haven't completed yet
-
so we can lock it down, expand out its neighbors, which are F and E.
-
F gets 20 and E gets the 17 and not only is that the first number written in E but it is the final one
-
because the very next thing we lock down is E's distance.
-
We don't lock down F's distance until we actually discover that
-
there is a shorter path, the 19-length path.
-
All right, so I think you understand this well enough that we can try to code it up