CODEWITHSUNDEEP
calgorithmgraphpath-findinglongest-path
user8400129
user8400129

Reputation: 213

Longest acyclic path from A to B in a graph

I'm learning C language. And I want to find the longest acyclic path in a graph from A to B.

For example, I have a graph like this:

             0
             |
             1 
           /   \
          2 --- 3
          |    / \
          5---6---4

Now I want to write a function which can find the longest acyclic path from node A to node B.

input: longestPath(node A, node B) output: the longest length is x, node_a -> ... -> node_b

for example:

input: longestPath(0, 6) output: the longest length is 6, 0 -> 1 -> 2 -> 3 -> 4 -> 6 (the output answer may not unique, but one of the right answer)

But I have no idea how to implement a suitable algorithm to find it.

Should I use BFS or DFS to find all possible paths and compare them? (but it seems slow)

Could you please give me some advice? Thanks!

Upvotes: 0

Views: 265

Answers (0)

Related Questions