Showing Revision 3 created 05/25/2016 by Udacity Robot.

1. Title:
   Simulate this Algorithm - Intro to Algorithms
2. Description:

3. 0 0:00 - 0:03
   If you did this a little bit carelessly, you might say that

   ¶

4. 3000 0:03 - 0:09
   the first number that goes into E is the length of the shortest hot path from A to E,
5. 9000 0:09 - 0:13
   which in this case would be, well there's two ways to get
6. 13000 0:13 - 0:16
   the distance 11 to here in two hops and then another seven.
7. 16000 0:16 - 0:23
   You might have said 18, but in fact, it won't expand D into E until it knows the shortest distance to D,
8. 23000 0:23 - 0:26
   and the shortest distance is going to be 10 because we can go this way.
9. 26000 0:26 - 0:30
   four plus one is five and five is 10 so it should be 17,
10. 30000 0:30 - 0:32
    but let's actually simulate and see what happens.
11. 32000 0:32 - 0:36
    We expand out A into C and B and once we've done that,
12. 36000 0:36 - 0:41
    the shortest non-completed distance is the one to C so we're going to lock that down
13. 41000 0:41 - 0:43
    and then we expand from that node C
14. 43000 0:43 - 0:46
    There is two edges to incomplete nodes, C to D and C to B.
15. 46000 0:46 - 0:50
    The C to B has a length of one plus length of four, we already had
16. 50000 0:50 - 0:54
    that actually improves this one to five and a new node joins the picture, D
17. 54000 0:54 - 1:00
    and C to D is seven on top of the four we already had for a total of 11.
18. 60000 1:00 - 1:03
    Alright, of the non-completed nodes, B and D,
19. 63000 1:03 - 1:07
    the one with the smallest distance is B with distance of five.
20. 67000 1:07 - 1:09
    We can lock that down and look at the outgoing edges from B,
21. 69000 1:09 - 1:13
    which is just this one that goes to D which had the length of five
22. 73000 1:13 - 1:19
    plus the five we already had for a length of 11 in D, which improves D, 10
23. 79000 1:19 - 1:23
    and this the only node hit that we can read at this point that we haven't completed yet
24. 83000 1:23 - 1:27
    so we can lock it down, expand out its neighbors, which are F and E.
25. 87000 1:27 - 1:33
    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
26. 93000 1:33 - 1:36
    because the very next thing we lock down is E's distance.
27. 96000 1:36 - 1:39
    We don't lock down F's distance until we actually discover that
28. 99000 1:39 - 1:42
    there is a shorter path, the 19-length path.
29. 102000 1:42 - 1:45
    All right, so I think you understand this well enough that we can try to code it up