bellman_ford shortest paths returns incorrect results

[dgleich]

The bellman_ford shortest path function doesn't return an error when called with a negative weight cycle even though this means the output is incorrect.

It should throw an error in this case.

[sehe]

I fear the general answer here is: it's a precondition and adding explicit checks would penalizing all usage of the algorithm.

Does the return value satisfy your expectations?

If there is a negative cycle, then there will be edges in the graph that were not properly minimized. That is, there will be edges (u,v) such that w(u,v) + d[u] < d[v]. The algorithm loops over the edges in the graph one final time to check if all the edges were minimized, returning true if they were and returning false otherwise?

Perhaps a concrete example would help if not.

[dgleich]

I'm not really doing much on this library anymore. Sorry.