YouTube

Got a YouTube account?

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

English subtitles

← Floyd-Warshall Intro - Intro to Algorithms

Get Embed Code
3 Languages

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

  1. I'm going to talk about an algorithm called Floyd Warshall
  2. after two of the inventors of this algorithm back in the early 60s,
  3. and it uses an idea called dynamic programming, which sounds so much cooler than its actually is.
  4. That means, it actually is a very cool idea.
  5. I have a professor friend who believes that I am predispose
  6. to see all problems at dynamic programming problems because it an algorithm design technique
  7. that I have been able to use successfully in a bunch of occasion,
  8. but it really is just an algorithm design technique.
  9. Its not particularly dynamic and it doesn't really change the way you think about programming.
  10. It just have to do with optimizing using tables. Alright.
  11. Let me start up by explaining this algorithm in terms of simple but possibly strange idea.
  12. First just for simplicity, let's imagine all the nodes in our graph are numbered from 0 to n-1,
  13. and lots of graph have exactly have their structure, but for example for our marvel data set,
  14. we have to all our characters be assigned numbers from 0 to n-1,
  15. but that's an easy thing to do, let's imagine that's already been done.
  16. What we're going to imagine now is that someone has given us matrix.
  17. Square matrix D of k and the entries of this matrix, just a big table like a spread sheet
  18. and is filled in with values as follows.
  19. The ij element of the i row, j column is filled in with the number
  20. and that number is the length of the shortest path from i to j
  21. hopping only all nodes numbered less than k.
  22. So I don't know about you but I used to play a game like this when I was younger,
  23. if I was in a building where the tiles were different colors, I'd sometimes declare
  24. let's say, the blue tiles are alligators, so I'm not going to step on any of the blue tiles
  25. and I'd try to walk stepping only on the tiles that I was allowed to use,
  26. so that the analogue of this in the graph is imagine we've got our graph,
  27. and we're trying to get a path from i to j, and some of the nodes are colored pink.
  28. Those are the okay nodes because they are numbered less than k and some of the nodes
  29. maybe including j itself are numbered higher than k, and we're not allowed to step on those.
  30. We're trying to get from i to j, we're allowed to step on j opposite
  31. but only the intermediate nodes that are pink.
  32. We only consider making paths along pink nodes and there's only one in this case.
  33. But there's some pink nodes that we don't use and their maybe multiple different pink paths,
  34. but we want to know the distance of the shortest path using only the pink nodes.
  35. Only the ones that are numbered less than k.
  36. So let's imagine, some very hopefully, has done this for us and filled in the matrix with all those values.
  37. There's big Πof n² values that have to get filled in, but someone has does that for us. That's all great.
  38. Our mission should we choose to accept it. Is to fill in Dk + 1.
  39. So this will be a new matrix just like the old matrix,
  40. but now when your going on a path from i to j, you're allowed to use node k.
  41. You don't have to use it but your allowed so that's all we have to do right now.
  42. Let's try to figure out if someone gives use Dk, how do we figure out Dk+1.