Bellman-Ford and negative edges

Topics: algorithm
Jun 5, 2010 at 5: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

http://quickgraph.codeplex.com/SourceControl/diff/file/view/32649?fileId=280997

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.

Regards,

Hugo.