The first question about the correctness of your code is more appropriate for http://codereview.stackexchange.com.
Either of Bellman-Ford or Floyd-Warshall is appropriate for this problem. A comparison of performance follows:
- Bellman-Ford (Wikipedia)
- Time-complexity:
O(|V|*|E|)
- Space-complexity:
O(|V|)
- The section on "Finding negative cycles" is what you want
- Time-complexity:
- Floyd-Warshall (Wikipedia)
- Time-complexity:
O(|V|^3)
- Space-complexity:
O(|V|^2)
- Time-complexity:
Since |E|
is bounded by |V|^2
, Bellman-Ford is the clear winner and is what I would advise you use.
If graphs without negative cycles is the expected normal case, it might be appropriate to do a quick check as the first step of your algorithm: does the graph contain any negative edges? If not, then it of course does not contain any negative cycles, and you have a O(|E|)
best case algorithm for detecting the presence of any negative cycles.