CODEWITHSUNDEEP
algorithmgraph
Mihai Bişog
Mihai Bişog

Reputation: 1018

Finding a path with the biggest number of nodes in a directed graph

What would be a good way to find in a directed graph a path which has the biggest number of nodes?

I suppose I could traverse the graph in depth for each node and find out which path has the biggest number of nodes however I'm wondering if there are better approaches.

Mention: the graph is guaranteed to have no cycles.

Upvotes: 3

Views: 2349

Answers (3)

AJed
AJed

Reputation: 576

Since your input is a Directed Graph and not Directed Acyclic Graph then it is NP-Complete and the solutions mentioned do not work. But as logic_max said: it is the longest path problem, and you reduce that by giving each edge a cost one.

Upvotes: 0

Jarosław Gomułka
Jarosław Gomułka

Reputation: 4995

If graph has a cycle then there is "infinite" length path.

If graph is acyclic: You should run 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);
   }
}

Upvotes: 2

Priyank Bhatnagar
Priyank Bhatnagar

Reputation: 814

You have a directed acyclic graph(DAG) and you want to find the path with biggest number of nodes. This, is infact finding the longest path in DAG.

This problem is solvable for DAG in polynomial time. Read more about it here :- Wikipedia.

Upvotes: 4

Related Questions