15
$\begingroup$

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the Bellman-Ford algorithm.

However, I'm interested in finding the shortest-path between two vertices that doesn't involve cycling (ie. under the constraint that you may not visit the same vertex twice). Is this problem well studied? Can a variant of the Bellman-Ford algorithm be employed, and if not is there another solution?

I'm also interested in the equivalent all-pairs problem, for which I might otherwise apply Floyd–Warshall.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
28
$\begingroup$

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is a beautiful answer. I've asked several people this IRL without any solutions and when I explained this to them their reaction was the same as mine - "of course, I feel so stupid now". $\endgroup$
    – jleahy
    May 2, 2013 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.