• JGraphT version: 1.5.1
• Java version (java -version)/platform: Java 11/NixOS (NixOS/nixpkgs@fdb42a7)

Issue

I may be missing something, but the heuristics introduced from #563, specifically number 4, introduce an assumption that I don't believe was there before, and therefore, causes a bug with a specific use-case of the FloydWarshall Algorithm. The underlying idea behind number 4 is that immediate neighbors will not affect the weights of the current shortest path, so it's safe to skip them. However, this only applies if there is not a negative weight cycle. Using the FW algorithm to detect negative cycles no longer works with these improvements.

I'm not sure what the right solution is, maybe I need to use a different algorithm for detecting negative cycles. For now, I've replicated the algorithm sans the number 4 improvements, which works for me. But I would much rather use something from jgrapht if I can, instead of copying and making mistakes.

Perhaps it's sufficient to update the docs for FW to say that it will not detect negative cycles?

Steps to reproduce (small coding example)

Graph<Local, DefaultEdge> g = new DefaultDirectedWeightedGraph<>(DefaultEdge.class);
this.graph.vertexSet().forEach(v -> g.addVertex(v));
this.graph.vertexSet().forEach(v1 -> {
        this.graph.vertexSet().forEach(v2 -> {
                DefaultEdge e;
                if (v1.equals(v2)) {
                    e = g.addEdge(v1, v2);
                    g.setEdgeWeight(e, 0.0);
                } else {
                    e = g.addEdge(v1, v2);
                    g.setEdgeWeight(e, Double.POSITIVE_INFINITY);
                }
            });
    });
this.graph.edgeSet().forEach(c -> {
        Local s = this.graph.getEdgeSource(c);
        Local t = this.graph.getEdgeTarget(c);
        DefaultEdge e = g.getEdge(s, t);
        g.setEdgeWeight(e, c.bound());
    });
FloydWarshallShortestPaths<Local, DefaultEdge> sps = new FloydWarshallShortestPaths<>(g);
for (Local l : g.vertexSet()) {
    if (sps.getPathWeight(l, l) < 0.0) {
        return false;
    }
}
return true;

this.graph is the graph I use for representing a weakly relational domain (static analysis). I translate the graph into a edge weighted graph, copying the constraint bounds as edge weights. From there, I attempt to compute all shortest paths using the FW algorithm.

Expected behaviour

The FW algorithm should be able to detect negative weight cycles, however, this is not happening.

Other information

I have used this minimal example for testing negative cycle detection.

[[0, -1],
 [0, 0]]