English subtitles

← Code for Dijkstra - Intro to Algorithms

Get Embed Code
3 Languages

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

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