Re: [Boost-users] Bellman-Ford shortest paths

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-05-29 10:29:42

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