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

1. Title:
   Code for Dijkstra - Intro to Algorithms
2. Description:

3. 0 0:00 - 0:03
   So here's my attempt at translating that description of an algorithm
4. 3000 0:03 - 0:06
   into actual Python code ended up using helpful structures
5. 6000 0:06 - 0:09
   maybe a little different than before so I've got a Dijkstra's algorithm.
6. 9000 0:09 - 0:12
   Dijkstra is the name of the individual who first described
7. 12000 0:12 - 0:16
   and analyzed this algorithm for a single-source shortest path.
8. 16000 0:16 - 0:19
   So we give it a single source. We give it a single node in the network.
9. 19000 0:19 - 0:22
   Then we ask for the distance to all the other nodes in the network in graph G.
10. 22000 0:22 - 0:27
    So the distance so far is a structure that's going to represent a mapping
11. 27000 0:27 - 0:32
    from nodes to what we think the distance might be from V to that node.
12. 32000 0:32 - 0:37
    And in our hand simulated algorithm, these are the numbers in the non-locked circles.
13. 37000 0:37 - 0:39
    Some nodes might not have any numbers yet,
14. 39000 0:39 - 0:42
    and the ones that have numbers are represented in that mapping.
15. 42000 0:42 - 0:48
    So then we start structure off by saying well, the distance that we know of so far from V to the V,
16. 48000 0:48 - 0:53
    the node that we started at, is zero, and we do that in the hand simulation as well.
17. 53000 0:53 - 0:56
    Alright, now, there's an additional data structure, which I call final dist,
18. 56000 0:56 - 0:59
    which is once we actually figured out what the real distance is,
19. 59000 0:59 - 1:03
    we stick in this structure and so that's basically the numbers that are in the heavy circles here.
20. 63000 1:03 - 1:06
    When a circle becomes heavy because I'm locking it down,
21. 66000 1:06 - 1:11
    I moved that number into the final dist mapping, and I deleted it from the dist so far
22. 71000 1:11 - 1:15
    so that number doesn't exist anymore in the dist so far mapping.
23. 75000 1:15 - 1:18
    Now, we're going to iterate as long as the set of nodes
24. 78000 1:18 - 1:21
    for which we've computed the distance is less than the total number of nodes.
25. 81000 1:21 - 1:23
    Now, this is a little risky. I probably shouldn't have done this.
26. 83000 1:23 - 1:28
    Because if the graph is disconnected, what this is going to do is this is how we're going to die.
27. 88000 1:28 - 1:32
    Well, let's see where it's going to die, but it will keep trying to add nodes
28. 92000 1:32 - 1:35
    in their final distances even though they aren't final distances to add.
29. 95000 1:35 - 1:38
    So there's probably other test that might be better to determine
30. 98000 1:38 - 1:41
    when everything that's reachable has actually been assigned value.
31. 101000 1:41 - 1:46
    In general, this test isn't quite the right test, but it will suffice for a connected graph
32. 106000 1:46 - 1:48
    and that's we're going to try it on.
33. 108000 1:48 - 1:52
    What do we do as long as there's more nodes that we need to analyze,
34. 112000 1:52 - 1:57
    Take the node that has the shortest distance of all the ones so far, call that w, and lock it down.
35. 117000 1:57 - 2:01
    Locking it down in this case involves need printing a debugging message
36. 121000 2:01 - 2:06
    saying that the final distance for w is whatever we computed the distance so far as.
37. 126000 2:06 - 2:12
    We now know that this is the final distance and then we delete that from the dist so far structure.
38. 132000 2:12 - 2:14
    Then we go through its neighbors.
39. 134000 2:14 - 2:21
    All of the neighbors of w in the graphs called an x, and for each one, we'll say,
40. 141000 2:21 - 2:26
    well, if we completely solved that neighbor then we don't have to do anything,
41. 146000 2:26 - 2:33
    but if we haven't then see if it has a distance so far, and if it doesn't then give it one
42. 153000 2:33 - 2:35
    by saying, well, our best guess is the distance.
43. 155000 2:35 - 2:40
    It's going to be the distance that it took to get to w plus the distance from w to x.
44. 160000 2:40 - 2:43
    On the other hand, if it already has the distance, check if the new distance,
45. 163000 2:43 - 2:46
    the distance to w plus the distance from w to x, is better than the distance
46. 166000 2:46 - 2:48
    that we had so far, and if it is, replace it.
47. 168000 2:48 - 2:52
    This is sometimes called relaxation. It doesn't seem very relaxing but that's what it is.
48. 172000 2:52 - 2:54
    And so now we've handled that node.
49. 174000 2:54 - 2:58
    We handle all the nodes for the neighbors of w and that means we've handled w.
50. 178000 2:58 - 3:00
    We've locked it down, and we can move on.
51. 180000 3:00 - 3:04
    We go back up and handle the next node closest to the start state.
52. 184000 3:04 - 3:07
    And once we've gone through all of the nodes and assigned them all their final distances
53. 187000 3:07 - 3:09
    then we return that structure and we're done.
54. 189000 3:09 - 3:12
    This is the Dijkstra's algorithm in a nutshell. Let's analyze this.