On Tue, 2007-05-29 at 14:37 +0100, Cigdem Gueler wrote:

Hi,

I have a little problem about Bellman Ford shortest paths algorithm. When I call this algorithm for the graphs with parallel edges, sometimes it fails to recognize the negative cycles. Doesn't it work for graphs with parallel edges? Or am I doing a mistake in my code? Well, the code is huge to send it to the mailing list. I am trying to find a little example for which this phenomenon occurs!

But I still would like to be confirmed that Bellman Ford should have actually worked for graphs with parallel edges. It is not really mentioned in the documentation if it works or not!!

My understanding of Bellman-Ford implies that it should work correctly in the presence of parallel edges. - Doug