1
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,
2
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
3
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
4
00:00:12,000 --> 00:00:17,000
that operation essentially to find out the distance from every other node to every other node.
5
00:00:17,000 --> 00:00:22,000
Really what we want to know is the shortest distance between any pair of nodes.
6
00:00:22,000 --> 00:00:27,000
So all pairs we would like to know the distance--the length of the shortest path.
7
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.
8
00:00:32,000 --> 00:00:36,000
We can just repeat than algorithm, just one at a time for each node run Dijkstra--
9
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.
10
00:00:40,000 --> 00:00:44,000
So we get n the number of vertices times nlogn for the total time--
11
00:00:44,000 --> 00:00:46,000
to get the distance between all pairs of nodes.
12
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.
13
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.
14
00:00:57,000 --> 00:01:02,000
If the graph is very densely connected, then the number of edges is roughly the square
15
00:01:02,000 --> 00:01:05,000
of the number of vertices and so the running time, at least in terms
16
00:01:05,000 --> 00:01:09,000
of the number of vertices, now becomes nÂłlog n.
17
00:01:09,000 --> 00:01:12,000
Now, you can do a little bit better than this using the Fibonacci heap idea
18
00:01:12,000 --> 00:01:16,000
that I was mentioning before but may be this is the best that you can do
19
00:01:16,000 --> 00:01:18,000
in terms of practically implementable code.
20
00:01:18,000 --> 00:01:20,000
This on the other hand now we can beat this.