CODEWITHSUNDEEP
c++algorithmdata-structuresgraphgraph-algorithm
user1330217
user1330217

Reputation: 243

How do you find the path that traverses the largest number of nodes in an undirected graph?

Given a an undirected graph and two arbitrary nodes (A and B) in the graph, how do I find the path that passes through the most number of unique nodes in order to navigate between nodes A and B?

I know that you can just depth search it and compare all the lengths, but is there a better way?

Upvotes: 1

Views: 783

Answers (2)

steffen
steffen

Reputation: 8968

This problem makes only sense if we are talking about acyclic graphs, so I assume you you mean that.

You will have to brute-force-try all possible paths.

To see why, imagine a graph in which you know the longest path of the two node and you add one node. You now have to test every path that contains the new node, including the ones that you already tested, if the node somehow connect to them.

Upvotes: 1

Keldon Alleyne
Keldon Alleyne

Reputation: 2130

That's an NP complete problem. All you can really do is try every possibility.

Upvotes: 9

Related Questions