# Is there a better than brute-force solution to the shortest simple path problem?

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, 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?

• 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 Mar 31 '17 at 18:12
• @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 Apr 2 '17 at 14:41