The longest path between two peaks

Question

I have a directed graph with weighted edges (weights are all positive).

Now I am looking for an efficient algorithm or code (specifically C #) to find the longest path between two given vertices.

Answer 1

This is exactly equivalent to the shortest path algorithm with all negative weights. To do this, you need to make sure that there are no negative weight cycles (which in your original case are probably equivalent to checking for positive weight cycles). It is best to take a weight inverting supplement and run Bellman-Ford, then take the inverse of the result.

Answer 2

David Berger's answer is correct if you do not mean a simple path where each vertex can meet no more than once, in which case Bellman-Ford will not give the longest path. Since you are saying that the weights are positive, it is not possible for the longest path to exist when the graph has a cycle (reachable from the source) unless you mean a simple path. The longest easy-path problem is NP-complete. See Wikipedia .

So let's say you mean a directed acyclic graph (DAG). In linear time, you can calculate the longest path to each vertex v from the initial vertex s, given that you know the longest path from s → * u for each u, where u-> v directly. This is easy - you can do the first depth search on your oriented graph and calculate the longest path for the vertices in the reverse order of their visits. You can also detect the trailing edges of the entire DFS using 3-color marking (open but not finished vertices are gray). See Wikipedia for more details. The longest / shortest path to the DAG is sometimes called the Viterbi algorithm (although it was specified taking into account a specific type of DAG).

At first I tried to use a linear dynamic programming solution. If you have cycles, then Bellman-Ford still will not solve your problem.

Answer 3

Refer to the QuickGraph project as it provides .NET data structures that implement graphs and also provides algorithms for working with such data structures. I am sure that the algorithm you are looking for is implemented in the library.

Answer 4

Just in case, this helps anyone, since I searched for this for a while, but could not find it, I used QuickGraph to solve the problem when I had to find the longest path that also matches a certain rule. This is not very elegant, because I did it a little brute force when I got the first result, but here it is.

https://github.com/ndsrf/random/blob/master/LongestSkiPath/LongestSkiPath/SkiingResolver.cs#L129-L161

To get the longest path, you use an algorithm to find the shortest path with lengths = -1. And then, to find the next longest paths, I start to remove the edges from this longest path to see if I can get the “best” (based on the problem conditions) longest path.