<p>Paths with no repeated vertices are called <a href="http://en.wikipedia.org/wiki/Path_%28graph_theory%29#Different_types_of_paths">simple-paths</a>, so you are looking for the shortest simple-path in a graph with negative-cycles.</p>

<p>This can be reduced from the <a href="http://en.wikipedia.org/wiki/Longest_path_problem">longest-path problem</a>.  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.</p>

<p>Thus your problem is NP-Hard.</p>

CC BY-SA 3.0
2013-05-02T09:24:14.813Z
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
CC BY-SA 3.0
2013-05-01T20:40:19.947Z
2013-05-01T20:40:19.947Z
BlueRaja - Danny Pflughoeft
<p>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.</p>

<p>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?</p>

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

<ds.algorithms><graph-algorithms><shortest-path>
Finding the shortest path in the presence of negative cycles
jleahy
# Finding the shortest path in the presence of negative cycles

(Asked by: username_0 on 2013-05-01)

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.

**Tags:** ds.algorithms, graph-algorithms, shortest-path

---

## 1 answers

### Answer by username_1 on 2013-05-01. Score: 32 | Accepted answer

Paths with no repeated vertices are called [simple-paths](http://en.wikipedia.org/wiki/Path_%28graph_theory%29#Different_types_of_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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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".  

---

