Shortest paths on undirected graphs with negative weights

[pnevyk]

Bellman-Ford algorithm currently works only on directed graphs (although this is not enforced by the type constraints nor algorithm selection at runtime). It can be adapted to undirected graphs by treating every edge as two directed edges going in the other directions, but then every edge with negative weight becomes a negative cycle. This may be a problem for any algorithm supporting negative weights, including #38 (but I did not investigate this proper).

If there isn't an algorithm that would handle undirected graphs with negative weights, I think the proper solution is to use Dijkstra. Because any algorithm would fail in some way if there is a negative edge, but Dijkstra will be faster in the happy cases.