<p>Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex more than once)</p>

<p>As explained in <a href="https://cstheory.stackexchange.com/questions/17462/finding-the-shortest-path-in-the-presence-of-negative-cycles">Finding the shortest path in the presence of negative cycles</a>, this problem is NP-hard. But I couldn't find any concrete upper bound anywhere.</p>

<p>Is there an algorithm that improves over the brute-force way of enumerating all simple paths and keeping the one with the minimum weight?</p>

CC BY-SA 3.0
2017-03-31T18:12:25.137Z
Dynamic programming can be used to obtain an algorithm with a running time that is $O(2^n poly(n))$. You will find this if you search for exact algorithms for TSP.
Chandra Chekuri
CC BY-SA 3.0
2017-04-02T14:41:21.810Z
@chandra-chekuri, could you tell me which algorithm you're referring to? The best-known seems to be Held-Karp, but usually TSP is defined for non-negative edge weights, and I wasn't able to find a source that definitely confirms that Held-Karp will work correctly with negative edge weights.
Benno
<graph-algorithms><upper-bounds>
Is there a better than brute-force solution to the shortest simple path problem?
Benno
# Is there a better than brute-force solution to the shortest simple path problem?

(Asked by: username_0 on 2017-03-31)

Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex more than once)

As explained in [Finding the shortest path in the presence of negative cycles](https://cstheory.stackexchange.com/questions/17462/finding-the-shortest-path-in-the-presence-of-negative-cycles), this problem is NP-hard. But I couldn't find any concrete upper bound anywhere.

Is there an algorithm that improves over the brute-force way of enumerating all simple paths and keeping the one with the minimum weight?

**Tags:** graph-algorithms, upper-bounds

> **Comments:**
> **username_1**: Dynamic programming can be used to obtain an algorithm with a running time that is $O(2^n poly(n))$. You will find this if you search for exact algorithms for TSP.  
> **username_0**: @chandra-chekuri, could you tell me which algorithm you're referring to? The best-known seems to be Held-Karp, but usually TSP is defined for non-negative edge weights, and I wasn't able to find a source that definitely confirms that Held-Karp will work correctly with negative edge weights.  

---

## 0 answers

