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 -
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
 Udacity Robot edited English subtitles for All Pairs Shortest Paths - Intro to Algorithms Gundega edited English subtitles for All Pairs Shortest Paths - Intro to Algorithms Amara Bot added a translation

English subtitles

Revisions Compare revisions

• API
Udacity Robot
• Gundega
• Amara Bot