Find the longest shortest-path between any two points in a graph

Given a graph, G, with edges E with weights W and vertices V.  You will have a path between two connected vertices.  Of the multiple paths between two vertices there should be one of the path that has the minimum weight.  Take the shortest path between every two points and return the one that has the maximum value.

This is a classic case of Floyd-Warshall algorithm.  The algorithm finds the shortest path between every two vertices in a graph.  We can use this to find all distances and then finally, find the maximum path.

Floyd-Warshall algorithm takes every pair of vertices in a graph and computes the distance of path through a third vertex.  This gives shortest path between any two vertices.  The complexity of the algorithm is O(|V|3)

A more efficient solution: We can calculate the path from a vertex V1 such that it is shortest path between V1 and one of the vertex and is longer than shortest path between any other vertex.  See this post for an algorithm.  Then, we can iterate through every vertex and find the longest path with every vertex as the root.  Once we have the list of all longest shortest-path, we can find the one that has the max value and return it.


find maxDepthInGraph(G)
{
  V <- G.vertices()
  E <- G.edges()

  for every vertex v in V:
    depth[v]=do breadth-first-search(v) and get the longest-  shortest-path

  maxDepth = -1
  for every vertex v in V:
    if maxDepth < depth[v]:
      maxDepth = depth[v]

  return maxDepth
}