2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Mar 31 '17 at 18:12
  • $\begingroup$ @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. $\endgroup$ – Benno Apr 2 '17 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.