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

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

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

Since your input is a direct graph and not a direct acyclic graph, it is NP-Complete and the solutions mentioned do not work. But as logic_max said: this is the longest path problem, and you reduce that by giving each edge a cost.

0

source

All Articles