Return to Video

All Pairs Shortest Paths - Intro to Algorithms

  • 0:00 - 0:05
    As we discussed in the previous Unit, to find the most central node in a social network,
  • 0:05 - 0:09
    it's useful to be able to take each node in a graph and find out how far it is
  • 0:09 - 0:12
    from all the other nodes in the graph to get a square for a particular node and then to repeat
  • 0:12 - 0:17
    that operation essentially to find out the distance from every other node to every other node.
  • 0:17 - 0:22
    Really what we want to know is the shortest distance between any pair of nodes.
  • 0:22 - 0:27
    So all pairs we would like to know the distance--the length of the shortest path.
  • 0:27 - 0:32
    Now, given that we can execute a shortest path from any given node, then m*logn time.
  • 0:32 - 0:36
    We can just repeat than algorithm, just one at a time for each node run Dijkstra--
  • 0:36 - 0:40
    here's a node run Dijkstra--here's a node run Dijkstra--so you repeat it for all the nodes.
  • 0:40 - 0:44
    So we get n the number of vertices times nlogn for the total time--
  • 0:44 - 0:46
    to get the distance between all pairs of nodes.
  • 0:46 - 0:51
    This quantity can have a range of values depending on how dense the connect to the graph is.
  • 0:51 - 0:57
    If the graph is connected but very sparse, m is the same as n--so we get n²logn.
  • 0:57 - 1:02
    If the graph is very densely connected, then the number of edges is roughly the square
  • 1:02 - 1:05
    of the number of vertices and so the running time, at least in terms
  • 1:05 - 1:09
    of the number of vertices, now becomes nÂłlog n.
  • 1:09 - 1:12
    Now, you can do a little bit better than this using the Fibonacci heap idea
  • 1:12 - 1:16
    that I was mentioning before but may be this is the best that you can do
  • 1:16 - 1:18
    in terms of practically implementable code.
  • 1:18 - 1:20
    This on the other hand now we can beat this.
Title:
All Pairs Shortest Paths - Intro to Algorithms
Video Language:
English
Team:
Udacity
Project:
CS215 - Intro to Algorithms
Duration:
01:21

English subtitles

Revisions Compare revisions