Finding the path with the most nodes in a directed graph
What would be a good way to find the path in a directed graph that has the most nodes?
I am guessing that I could traverse the plot in depth for each node and figure out which path has the most nodes, but I am wondering if there are more efficient approaches.
Mention: It is guaranteed that the schedule has no cycles.
+3
source to share
3 answers
You have a directed acyclic graph (DAG) and you want to find a path with a lot of nodes. This means that it detects longest path
in the DAG.
This problem is solvable for DAGs in polynomial time. More on this here: - Wikipedia.
+4
source to share
If the graph has a cycle, then there is an "infinite" path of length.
If the graph is acyclic: You must run a topological sort. Then:
foreach(node in topological_sort_order) {
foreach(prev_node in neibhours[node]) {
// there is edge from prev_node to node
// since vertices are sorted in topological order than
// value for longest_path[prev_node] is already computed
longest_path[node] = max(longest_path[node], longest_path[prev_node] + 1);
}
}
+2
source to share