# 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