How can I find the shortest path between two nodes if there might be negative cycles in the graph?

You can use Bellman Ford algorithm for finding shortest path. Bellman-Ford Algorithm G - Graph s - source vertex V - vertices in the graph E - Edges in the graph (u,v)  - Edge from u to v distance[i] - shortest distance from source to vertex i w(u,v) - weight on the edge from u to v Step 1: Initialize distances from source to all vertices:     distance[s] = 0     distance[u] = Integer.MAX_VALUE for all vertices other than s Step 2: Relax Edges- Repeat following steps V-1 times:     For every edge E, repeat following steps:         If distance[v] > distance[u] + weight(u,v) then             set distance[v] = distance[u] + weight(u,v) Step 3: Detect negative cycle- Check if there exists an edge (u,v) for which,     distance[v] > distance[u] + weight(u,v), then graph has a negative cycle.     So, return true Step 4: If there is no negative cycle, return false Time Complexity is O(VE) Space Complexity is O(V) Source: http://www.ideserve.co.in/learn/bellman-ford-shortest-path-algorithm This explains the algorithm with dry run option and java code. Hope this helps.

" But what if I add an aditional clause that guarantees that even though there might be a negative cycle in the graph, there exists a path that doesn't go through the negative cycle? " -> This still doesn't guarantee you anything, unless and until you can specifically prove that this path is shorter than (or is the) the shortest-simplest path (http://cstheory.stackexchange.com/questions/19483/shortest-simple-path-with-minimum-edge-cost-minus-node-reward). If you find that, then you have to compare to all other possible paths. Your clause doesn't make the problem easier in anyway whatsoever. And the Bellman-Ford Algorithm will relax the vertices. By virtue of repetitive crosses to the Negative Cycle, you'll have incorrectly memoized comparisons. If you now want to make the claim that you'll memorize each relaxation, then you're just enumerating all possible combinatorial options, which is what leads to the NP-Hard-ness in the first place. I'm sorry, but even given your clause, the problem is still NP-Hard!

Basic Implementation of http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm O(nm) or http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm O(n^3) can easily solve your problem. You can read about them in more detail.