forked from lingeringsocket/jgrapht
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Terminate BFSShortestPath#getPath early #1158
Comments
That sounds reasonable. Would you be willing to submit a pull request with the suggested code change? |
Hi @jkinable, I see the issue is still open, can I work on this? |
Pratyushgoyal66
added a commit
to Pratyushgoyal66/jgrapht
that referenced
this issue
May 19, 2024
Sure, that would be great. |
6 tasks
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Issue
The current
BFSShortestPath
implementation ofgetPath
simply callsgetPaths
and then retrieves the desired path from theSingleSourcePaths
. 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:
Using the
BFSShortestPath
to find the shortest path fromA
toB
would continue to traverse the entire subgraph afterB
.Steps to reproduce (small coding example)
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.The text was updated successfully, but these errors were encountered: