Is there any difference in time complexity for mean shortest path length and diameter algorithms for a graph?

For an undirected, unweighted graph, is there any difference in the time complexity of the algorithm to compute its开发者_开发问答 average shortest path length vs, the complexity of the algorithm which computes the diameter of the graph, ie, the longest shortest path between two vertices?

---

According to Wikipedia, to calculate the diameter of the graph, you should first find the all-pairs shortest path. After calculating the all-pairs shortest path, both algorithms reduce down to a O(V^2) calculation so their complexities are the same.

---

I haven't read much literature on the subject but I suspect that the two are the same. However if there is a discrepancy, I'd say calculating the diameter of a graph might be asymptotically faster.

My algorithm for both would be to calculate all-pairs shortest path using Dijkstra's algorithm which runs in V*(E+V*log(V)). Then for the mean you would take the arithmetic average over all these values. I don't see a way you could speed this up.

However for calculating the diameter of a graph, there might be some clever tricks you can use to speed up this process. But as an upper bound, you can simply take the supremum over the all-pairs shortest path to get the diameter, which has the same run-time complexity as calculating the mean shortest path.

---

No there should not be any difference in the time complexity between the two.

You can find the longest path between two vertices by tweaking the shortest path algo.