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.