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

Question

I have a large set of linear networks and I would like to find the two ends of each network that are the most distant from each other along the network (on the image below, it would be D to K). The brute force solution to this problem is to compute the shortest path along the network for each pair of origin, but I have hundreds of networks with thousands of ends, so computing each possible path is quite heavy.

Is there an optimal way to compute this without using the brute force ? Can I exclude some points based on some clever rules ?

EDIT: I've added an illustration of the longest path mentioned by @Alex Tereshenkov in order to clarify my question. The black path is the result of the longest path algorithm (longest path without repeating any vertices). In my case, imagine that you enter the network from any of the letters and you need to drive to another letter as fast as you can. Which two letters are the most difficult to join ?

Answer 1

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.

Answer 2

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.