Menu
I have a DAG (with costs/weights per edge) and want to find the longest path between two sets of nodes. The two sets of start and target nodes are disjoint and small in size compared to the total number of nodes in the graph.
I know how to do this efficiently between one start and target node. With multiple, I can list all paths from every start to every target node and pick the longest one – but that takes quadratic number of single path searches. Is there a better way?
639
A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.
To find the longest path in a directed, cyclic graph, G = ( V , E ) G = (V, E) G=(V,E) (as asked in Coding Assignment 4 part e), I implemented an algorithm which generates a number of permutations of DAG reductions, G π G_{\pi} Gπ, of the graph G, and finds the longest path in each of these DAGs.
The answer is YES it is possible. The Dijkstra algorithm finds the shortest path in a graph. So if you want to modify this algorithm to find the longest path in a graph, then you just have to multiply the edge weight by "-1". With this change the shortest path will be actualy the longest path.
I assume that you want the longest path possible that starts in any of the nodes from the first set and ends in any of the nodes in the second set. Then you can add two virtual nodes:
The first node has no predecessors and its successors are the nodes from the first set.
The second node has no successors and its predecessors are the nodes from the second set.
All the newly added edges should have zero weight.
The graph would still be a DAG. Now if you use the standard algorithm to find the longest path in the DAG between the two new nodes, you’ll get the longest path that starts in the first set and ends in the second set, except that there will be an extra zero-weighted edge at the beginning and an extra zero-weighted edge at the end.
By the way, this solution is essentially executing the algorithm from all the nodes from the first set, but in parallel as opposed to the sequential approach your question suggests.
184
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
