English subtitles

← All Pairs Shortest Paths - Intro to Algorithms

Get Embed Code
3 Languages

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

  1. As we discussed in the previous Unit, to find the most central node in a social network,
  2. it's useful to be able to take each node in a graph and find out how far it is
  3. from all the other nodes in the graph to get a square for a particular node and then to repeat
  4. that operation essentially to find out the distance from every other node to every other node.
  5. Really what we want to know is the shortest distance between any pair of nodes.
  6. So all pairs we would like to know the distance--the length of the shortest path.
  7. Now, given that we can execute a shortest path from any given node, then m*logn time.
  8. We can just repeat than algorithm, just one at a time for each node run Dijkstra--
  9. here's a node run Dijkstra--here's a node run Dijkstra--so you repeat it for all the nodes.
  10. So we get n the number of vertices times nlogn for the total time--
  11. to get the distance between all pairs of nodes.
  12. This quantity can have a range of values depending on how dense the connect to the graph is.
  13. If the graph is connected but very sparse, m is the same as n--so we get n²logn.
  14. If the graph is very densely connected, then the number of edges is roughly the square
  15. of the number of vertices and so the running time, at least in terms
  16. of the number of vertices, now becomes nÂłlog n.
  17. Now, you can do a little bit better than this using the Fibonacci heap idea
  18. that I was mentioning before but may be this is the best that you can do
  19. in terms of practically implementable code.
  20. This on the other hand now we can beat this.