Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex.
How do I prove that for every vertex $v$ in $G$, there is a shortest $s-v$ path with $<= n - 1$ edges?
Where $n$ is the number of vertices in $G$.
If there is a path $P$ from $s$ to $v$, there is one where no vertex occurs more than once, with a weight that is less or equal to $P$. Indeed, if a vertex $x$ occurs twice, there is necessarily a loop from $x$ to itself. This loop cannot have a negative weight by hypothesis. So by removing it, we get a path that is no heavier. This can be repeated until we obtain a path where no vertex occurs more than once. Hence there are at most $n$ vertices on such a path, which means that the path has at most $n-1$ edges.
Thus we can consider only paths with at most $n-1$ edges, with each edge occurring at most once, since any other path is no lighter than a path in that set.
Since this set is finite, the number of edge conbinations to be used for a path is necessarily finite too (further limited by the constraint or forming a path from $s$ to $v$). Thus the set of weights has a minimum corresponding to some path(s) wich is (are) the minimum /shortest path(s).
Basically you have not much options here – do relaxation on each vertex peeking them from the list like Bellman-Ford does and you'll end up with a shortest path to one vertex, and move on.
