[Perf] Optimize DijkstraManyToManyShortestPaths.getPaths(V) to run one source search

[Shai Eilat]

Hi all,

Heads-up before opening a small performance PR. Strictly a behaviour-preserving fix on an existing class; no new API.

The issue

DijkstraManyToManyShortestPaths inherits the default getPaths(V source) implementation from BaseManyToManyShortestPaths, which calls getPath(source, v) for every vertex v in the graph. Each of those calls dispatches through getManyToManyPaths(singleton(source), singleton(v)), which in this subclass runs a fresh DijkstraClosestFirstIterator from source.

So a single getPaths(source) call runs |V| separate Dijkstras from the same source, turning what should be a single O(V log V + E) query into O(|V| · (V log V + E)).

The fix

Override getPaths(V) on DijkstraManyToManyShortestPaths only with:

return getShortestPathsTree(graph, source, graph.vertexSet());

Both ListSingleSourcePathsImpl (the historical return type) and TreeSingleSourcePathsImpl honor the same SingleSourcePaths contract on every externally-visible method, including unreachable-target (null path / +∞ weight) and source==target (singleton walk, weight 0).

The override lives on the concrete subclass, not the abstract base. Two other subclasses extend BaseManyToManyShortestPaths and have different getPaths(V) semantics that must be preserved:

• DefaultManyToManyShortestPaths accepts a user-supplied Function<Graph, ShortestPathAlgorithm> and is expected to consult it on every shortest-path query. Routing getPaths(V) through getShortestPathsTree would silently bypass that algorithm function.

• CHManyToManyShortestPaths uses a precomputed contraction hierarchy. Routing getPaths(V) through plain Dijkstra over the original graph would silently bypass that preprocessing.

Both behaviours are preserved by specialising only on the concrete subclass.

Benchmark

JMH bench at jgrapht-core/src/test/java/org/jgrapht/perf/shortestpath/DijkstraManyToManyShortestPathsGetPathsPerformance.java, two @Benchmark methods in the same JVM:

• testBaseClassLoop replicates the historical |V|-Dijkstra default.

• testOptimizedGetPaths calls the override.

GnpRandomGraphGenerator p=0.1, 5 sources/op, JDK 21, @Fork 1, @Warmup 3×5s, @Measurement 5×5s:

Speedup grows with |V| as expected from the asymptotic improvement.

Tests

• DijkstraManyToManyShortestPathsTest (18 tests, all pass). New cases: oracle-match on a hand-built graph, vertex-not-in-graph rejection, single-vertex graph, source-with-no-outgoing-edges, disconnected graph, cyclic graph with self-loop on source, twice-called consistency, and a seeded fuzz suite comparing getPaths(source) against a fresh DijkstraShortestPath oracle on 10 random graphs.

• DefaultManyToManyShortestPathsTest: counting-spy test asserts the user-supplied algorithm function is still consulted by getPaths(V), guarding against an accidental future push of the override into the base class.

• CHManyToManyShortestPathsTest: pins getPaths(source) against a Dijkstra oracle on the contracted hierarchy.

Full mvn -pl jgrapht-core test is green (6885 pass, 15 unrelated upstream skips). mvn -pl jgrapht-core checkstyle:check -P checkstyle and mvn -pl jgrapht-core javadoc:javadoc clean.

I'll open a PR shortly unless someone wants me to hold for discussion.

Thanks, Shai Eilat