
As we discussed in the previous Unit, to find the most central node in a social network,

it's useful to be able to take each node in a graph and find out how far it is

from all the other nodes in the graph to get a square for a particular node and then to repeat

that operation essentially to find out the distance from every other node to every other node.

Really what we want to know is the shortest distance between any pair of nodes.

So all pairs we would like to know the distancethe length of the shortest path.

Now, given that we can execute a shortest path from any given node, then m*logn time.

We can just repeat than algorithm, just one at a time for each node run Dijkstra

here's a node run Dijkstrahere's a node run Dijkstraso you repeat it for all the nodes.

So we get n the number of vertices times nlogn for the total time

to get the distance between all pairs of nodes.

This quantity can have a range of values depending on how dense the connect to the graph is.

If the graph is connected but very sparse, m is the same as nso we get nÂ˛logn.

If the graph is very densely connected, then the number of edges is roughly the square

of the number of vertices and so the running time, at least in terms

of the number of vertices, now becomes nÂłlog n.

Now, you can do a little bit better than this using the Fibonacci heap idea

that I was mentioning before but may be this is the best that you can do

in terms of practically implementable code.

This on the other hand now we can beat this.