5
$\begingroup$

I have a sparse weighted graph, and I want to find the longest path from a given vertex to any other vertex which does not go through the same vertex twice. You can think of it as, I am here, and I want to take the longest walk possible in my graph without walking through the same place twice. Where ever that ends me up, I don't care, and I don't necessarily have to travel through every point on the graph, if those points do not lie on the longest path. All edges have positive weights.

Can anyone describe an algorithm for this that is not a complete enumeration of all paths?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

Yes, the Bellman-Held-Karp algorithm is not a complete enumeration and can be modified easily enough to solve your problem.

However, it still takes something over $2^n$ time (see question for details), and something exponential like that seems unavoidable since this is a variant of the traveling salesman problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.