I am able to use this algorithm to find the longest path in a weighted DAG (using topological sort and then relaxing each edge). My question now is if there is an algorithm to find the top 3 longest paths of the DAG? Or, is there any javascript or java library that implements this algorithm?
2
votes
I may be incorrect, but I believe the only algorithm to do this would be to generate all possible paths, sort by path length, and then select your desired paths. The alternative would be to find the longest path, and then modify the graph in some way that makes that path no longer exist in the top 3, but doesn't modify any other paths and then iterate - this is likely not possible in general, although there might be a certain subclass of graphs where it could be possible.
- twalberg
I don't have enough time to tell my idea right now but I explain it more in three days, the main idea is that you have to find the longest path that doesn't share one or more edges with the main longest longest path, so you just have to run the algorithm for the graph minus each one of the edges of the main longest path.
- FazeL
1 Answers
0
votes
You can easily compute first longest path, and you can use following algorithm for finding the next longest path:
Delete each edge of the main longest path one by one and the run the algorithm again to find the longest path on the modified graph then put back the deleted edge and delete one other edge.
Why this works?
You need a path the is not exactly the first longest path, so the second longest path must be different in at least one edge, so if you ignore one edge and find the longest path for each of the edges you eventually find a longest path that don't share at least one edge with the main longest path.
The third longest path is a path that is a longest path and doesn't share at least one edge with the first and the second longest path.
