Is there an optimal algorithm to find the longest shortest path in a network?

According to the Wikipedia page Longest path problem, this problem

... is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

If you work with (or can represent your graph as DAG), then networkx Python package will let you calculate it. Look for the function dag_longest_path.

Unless I am missing something, you will need to calculate the length between graph nodes and sort them which will, unfortunately, work only in linear time, that is there is no efficient algorithm for this.

I think you may be looking for the Graph Diameter of your network. There are a couple of questions on stackexchange that mention this topic, e.g.:

• The time complexity of finding the diameter of a graph
• Good algorithm for finding the diameter of a (sparse) graph?
• What is meant by diameter of a network?
• Difference between diameter of a graph vs longest path of the graph

Most of the algorithms suggest computing the "all-pairs shortest paths" first and selecting the longest of those, but I found a blog post by Koushik Narayanan that suggests an alternative approach which might be more optimal (I didn't check), which iterates over each vertex and finds its most distant pair:

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.