15

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.

jleahy
  • 253
  • 1
  • 2
  • 8

1 Answers1

28

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.

BlueRaja - Danny Pflughoeft
  • 1,591
  • 3
  • 13
  • 19
  • 1
    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". – jleahy May 02 '13 at 09:24