Menu
What algorithm can be used to find the longest path in an unweighted directed acyclic graph?
303
Acyclic graphsA 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.
Efficient Approach: An efficient approach is to use Dynamic Programming and DFS together to find the longest path in the Graph. Let dp[i] be the length of the longest path starting from the node i. Initially all positions of dp will be 0. We can call the DFS function from every node and traverse for all its children.
Unweighted graph is a type of graph with no edge weight. In an unweighted graph, the edges represent the connection between two nodes. If there is an edge between nodes u and v in an unweighted graph then u and v are adjacent to each other.
Dynamic programming. It is also referenced in Longest path problem, given that it is a DAG.
The following code from Wikipedia:
algorithm dag-longest-path is input: Directed acyclic graph G output: Length of the longest path length_to = array with |V(G)| elements of type int with default value 0 for each vertex v in topOrder(G) do for each edge (v, w) in E(G) do if length_to[w] <= length_to[v] + weight(G,(v,w)) then length_to[w] = length_to[v] + weight(G, (v,w)) return max(length_to[v] for v in V(G)) As long as the graph is acyclic, all you need to do is negate the edge weights and run any shortest-path algorithm.
EDIT: Obviously, you need a shortest-path algorithm that supports negative weights. Also, the algorithm from Wikipedia seems to have better time complexity, but I'll leave my answer here for reference.
41
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
