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

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 ?

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.:

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.

• thanks, graph diameter was exactly what I am looking for, and the pseudo-diamter heuristic works in my case. I've just learnt new words there ! – radouxju Feb 1 '17 at 6:36

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.