2

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?

Community
  • 1
Benno
  • 121
  • 3
  • 2
    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 02 '17 at 14:41

0 Answers0