
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 noncompleted 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 noncompleted 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 19length path.

All right, so I think you understand this well enough that we can try to code it up