Jgrapht: DeltaSteppingShortestPath unable to solve SSSP on a path with 3+ edges

[haerrel]

 * JGraphT version: 1.5.0 [also tested on 1.4.0]
 * Java version (java -version)/platform:  adopt-openjdk-15/windows [also tested on oracle 1.8.0_265/windows]

Issue
DeltaSteppingShortestPath cannot solve the Shortest Path Problem on a Graph where the target vertex is 3 or more edges away from the source vertex.

Steps to reproduce (small coding example)

DirectedWeightedMultigraph<String, DefaultWeightedEdge> graph = new DirectedWeightedMultigraph<>(DefaultWeightedEdge.class);
graph.addVertex("v0");
graph.addVertex("v1");
graph.addVertex("v2");
graph.addVertex("v3");
graph.addEdge("v0", "v1");
graph.addEdge("v1", "v2");
graph.addEdge("v2", "v3");
new DeltaSteppingShortestPath<>(graph).getPath("v0", "v3") // this returns null
new DijkstraShortestPath<>(graph).getPath("v0", "v3") // this returns a non-null result

Expected behaviour
DeltaSteppingShortestPath should find a similar solution to DijkstraShortestPath

Other information

[d-michail]

@SChudakov Could you take a look?

[SChudakov]

@d-michail Sure, I will.

[haerrel]

@SChudakov for me it looks like there is a problem with the computation of buckets

numOfBuckets = (int) (Math.ceil(maxEdgeWeight / delta) + 1);

https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/shortestpath/DeltaSteppingShortestPath.java#L312

When running the test from above the number of buckets is two, because the maxEdgeWeight in the graph is 1 (and delta=1).
This at least clarifies why it cannot solve a graph with more then 3 chained edges.

[SChudakov]

I`ve fixed the bug in my local branch. I will submit a PR after #972 gets merged since I made my changes on top of those commits.

Basically, the problem goes as follows: the computation of the number of buckets is correct. However, the iteration over the bucket structure during shortest path computation is incorrect because every bucket is traversed only once. For it to be correct, the number of buckets should be equal to ceil(L/delta) where L is the maximum weight of the shortest path in the graph.

In our implementation, we have the number of buckets computed as

numOfBuckets = (int) (Math.ceil(maxEdgeWeight / delta) + 1);

and vertices are getting assigned to buckets as

private int bucketIndex(double distance) {
    return (int) Math.round(distance / delta) % numOfBuckets;
}

therefore some buckets might be traversed multiple times. To fix this issue it is needed to start with the first non-empty bucket in every interaction, as shown here:

[SChudakov]

I guess we can close this now.