search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
78 stars 24 forks source link

Bidirectional: path joining algorithm #21

Closed torressa closed 4 years ago

torressa commented 4 years ago

Is your feature request related to a problem? Please describe. The BiDirectional Algorithm does not terminate until either all the forward or backward labels have been processed. It would be good if a path joining algorithm would identify if/when two paths can be joined, hence terminating faster.

Describe the solution you'd like Implementation of the path joining algorithm Righini and Salani (2006).

Describe alternatives you've considered

Additional context

torressa commented 4 years ago

Use halway point to reduce the number of label comparisons:

https://github.com/torressa/cspy/blob/2b424ea4e90c6d98f6e6c645b323cbcb4d5637ed/cspy/algorithms/bidirectional.py#L423