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.


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.



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);




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.



All Articles