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 distance--the 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 Dijkstra--here's a node run Dijkstra--so 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 n--so 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.