WEBVTT
00:00:00.000 --> 00:00:05.000
As we discussed in the previous Unit, to find the most central node in a social network,
00:00:05.000 --> 00:00:09.000
it's useful to be able to take each node in a graph and find out how far it is
00:00:09.000 --> 00:00:12.000
from all the other nodes in the graph to get a square for a particular node and then to repeat
00:00:12.000 --> 00:00:17.000
that operation essentially to find out the distance from every other node to every other node.
00:00:17.000 --> 00:00:22.000
Really what we want to know is the shortest distance between any pair of nodes.
00:00:22.000 --> 00:00:27.000
So all pairs we would like to know the distance--the length of the shortest path.
00:00:27.000 --> 00:00:32.000
Now, given that we can execute a shortest path from any given node, then m*logn time.
00:00:32.000 --> 00:00:36.000
We can just repeat than algorithm, just one at a time for each node run Dijkstra--
00:00:36.000 --> 00:00:40.000
here's a node run Dijkstra--here's a node run Dijkstra--so you repeat it for all the nodes.
00:00:40.000 --> 00:00:44.000
So we get n the number of vertices times nlogn for the total time--
00:00:44.000 --> 00:00:46.000
to get the distance between all pairs of nodes.
00:00:46.000 --> 00:00:51.000
This quantity can have a range of values depending on how dense the connect to the graph is.
00:00:51.000 --> 00:00:57.000
If the graph is connected but very sparse, m is the same as n--so we get nÂ˛logn.
00:00:57.000 --> 00:01:02.000
If the graph is very densely connected, then the number of edges is roughly the square
00:01:02.000 --> 00:01:05.000
of the number of vertices and so the running time, at least in terms
00:01:05.000 --> 00:01:09.000
of the number of vertices, now becomes nÂłlog n.
00:01:09.000 --> 00:01:12.000
Now, you can do a little bit better than this using the Fibonacci heap idea
00:01:12.000 --> 00:01:16.000
that I was mentioning before but may be this is the best that you can do
00:01:16.000 --> 00:01:18.000
in terms of practically implementable code.
00:01:18.000 --> 00:01:20.000
This on the other hand now we can beat this.