Bellman-Ford and negative edges

Topics: algorithm
Jun 5, 2010 at 4:48 AM

I am relatively new to QuickGraph, and so far I have found very useful.

I am trying to understand a change to the Bellman-Ford algorithm that added the lines: 

                if (edgeWeight < 0)                    

throw new InvalidOperationException("non negative edge weight");



It was introduced in change 32649

and appears to prevent negative edges (in general? and not just as part of checking against a negative cycle?).

But this seems to be going against what is stated in the intro to ShortestPath algorithm section, as to when to use Bellman-Ford (i.e. negative edges).

"Depending on the properties of the weights and the graph, different algorithms can be applied:

I am in the process of understanding exactly the scope of that change, but it seems to definitely prevent negative edges, even for DAGs.

Any help in understanding this issue is greatly appreciated.