YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Simulate this Algorithm - Intro to Algorithms

Get Embed Code
3 Languages

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

  1. If you did this a little bit carelessly, you might say that

  2. the first number that goes into E is the length of the shortest hot path from A to E,
  3. which in this case would be, well there's two ways to get
  4. the distance 11 to here in two hops and then another seven.
  5. You might have said 18, but in fact, it won't expand D into E until it knows the shortest distance to D,
  6. and the shortest distance is going to be 10 because we can go this way.
  7. four plus one is five and five is 10 so it should be 17,
  8. but let's actually simulate and see what happens.
  9. We expand out A into C and B and once we've done that,
  10. the shortest non-completed distance is the one to C so we're going to lock that down
  11. and then we expand from that node C
  12. There is two edges to incomplete nodes, C to D and C to B.
  13. The C to B has a length of one plus length of four, we already had
  14. that actually improves this one to five and a new node joins the picture, D
  15. and C to D is seven on top of the four we already had for a total of 11.
  16. Alright, of the non-completed nodes, B and D,
  17. the one with the smallest distance is B with distance of five.
  18. We can lock that down and look at the outgoing edges from B,
  19. which is just this one that goes to D which had the length of five
  20. plus the five we already had for a length of 11 in D, which improves D, 10
  21. and this the only node hit that we can read at this point that we haven't completed yet
  22. so we can lock it down, expand out its neighbors, which are F and E.
  23. 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
  24. because the very next thing we lock down is E's distance.
  25. We don't lock down F's distance until we actually discover that
  26. there is a shorter path, the 19-length path.
  27. All right, so I think you understand this well enough that we can try to code it up