14

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 ?

How to efficiently find the red path ?

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 ? enter image description here

Improve this question
1
  • 1
    mad paint skillz! – Adam Feb 1 '17 at 0:15
7

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.

Improve this answer
1
  • 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
8

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.

Improve this answer
2
  • thnks for the answer, already + 1 because of the information. However, I am looking for the longest OF THE SHORTEST PATH in a network (in my example, no detour toward B or H). Therefore your solution is not exactly what I am looking for, even if it hints that "brute force" is probably the only solution. – radouxju Jan 27 '17 at 14:04
  • @radouxju, ah I see. Well, let's see if gene will notice this, he has a lot of experience with graphs, maybe he has some bright ideas. – Alex Tereshenkov Jan 27 '17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.