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?

Improve this question
$\endgroup$
2
  • 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, 2017 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, 2017 at 14:41

0

Reset to default

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.