search

FubarDevelopment / QuickGraph

Fork of https://quickgraph.codeplex.com/
Microsoft Public License
9 stars 2 forks source link

CP-21586: Bug Report: Bellman-Ford shortest path algorithm implementation does not accept negative weights. #119

Closed fubar-coder closed 6 years ago

fubar-coder commented 6 years ago

From unknown CodePlex user on Wednesday, 28 September 2011 23:42:12

I intend to use the Bellman-Ford algorithm to perform negative cycle detection. It appears to me that there is something wrong in the implementation of the algorithm (source revision quickgraph-60730). In BellmanFordShortestPathAlgorithm.cs, line 229:230   if (edgeWeight < 0) throw new InvalidOperationException("non negative edge weight");   It is not clear to me why the algorithm should fail on non-negative edge weights, since the main use of the Bellman-Ford algorithm is for shortest path in the presence of negative weights.   There is also something strange with the description:   /// true if successful, false if there was a negative cycle. protected override void InternalCompute()   The documentation suggests a boolean return, but the implementation is for void.

fubar-coder commented 6 years ago

Form unknown CodePlex user on Saturday, 19 November 2011 20:23:29

Resolved with changeset 63893.