<p>Yes, the <a href="https://cstheory.stackexchange.com/questions/3666/time-complexity-of-bellman-held-karp-algorithm-for-tsp-take-2">Bellman-Held-Karp algorithm</a> is not a complete enumeration and can be modified easily enough to solve your problem.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-09T18:26:33.027Z
2010-12-09T18:26:33.027Z
2017-04-13T12:32:28.167Z
David Eppstein
<p>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.</p>

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

<ds.algorithms><graph-algorithms>
Max Non-overlapping Path in Weighted Graph
Nick Larsen
# Max Non-overlapping Path in Weighted Graph

(Asked by: username_0 on 2010-12-09)

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?

**Tags:** ds.algorithms, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2010-12-09. Score: 10 | Accepted answer

Yes, the [Bellman-Held-Karp algorithm](https://cstheory.stackexchange.com/questions/3666/time-complexity-of-bellman-held-karp-algorithm-for-tsp-take-2) 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.


---

