Terminate BFSShortestPath#getPath early

[Elewyth]

 * JGraphT version: 1.5.2
 * Java version (java -version)/platform:  17.0.6

Issue
The current BFSShortestPath implementation of getPath simply calls getPaths and then retrieves the desired path from the SingleSourcePaths. This causes the BFS algorithm to calculate the shortest path to all other (reachable) vertices in the graph, regardless of whether we have already found the shortest path to the desired sink.

For very large graphs this causes a significant overhead, especially if the sink is close to the source. Imagine a graph like:

A -> B -> (huge subgraph)

Using the BFSShortestPath to find the shortest path from A to B would continue to traverse the entire subgraph after B.

Steps to reproduce (small coding example)

var graph = new SimpleDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);

graph.addEdge(1, 2);
graph.addEdge(2, 3);

var alg = new BFSShortestPath<>(graph);
var result = alg.getPath(1, 2); // also calculates the shortest path from 1 to 3 (1 -> 2 -> 3), even though we already found 2

Expected behaviour
BFSShortestPath#getPath should terminate as soon as the shortest path from source to sink was found.

Other information
E.g. DijkstraShortestPath#getPath has an implementation that terminates early as soon as the shortest path to the sink vertex was found.

[jkinable]

That sounds reasonable. Would you be willing to submit a pull request with the suggested code change?

[Pratyushgoyal66]

Hi @jkinable, I see the issue is still open, can I work on this?