 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
#include <bidirectional_dijkstra.h>
Classes | |
| struct | NodeDistance |
| struct | Path |
Public Types | |
| typedef GraphType::NodeIndex | NodeIndex |
| typedef GraphType::ArcIndex | ArcIndex |
Public Member Functions | |
| BidirectionalDijkstra (const GraphType *forward_graph, const std::vector< DistanceType > *forward_arc_lengths, const GraphType *backward_graph, const std::vector< DistanceType > *backward_arc_lengths) | |
| std::string | PathDebugString (const Path &path) const |
| std::vector< NodeIndex > | PathToNodePath (const Path &path) const |
| Path | SetToSetShortestPath (const std::vector< NodeDistance > &sources, const std::vector< NodeDistance > &destinations) |
| Path | OneToOneShortestPath (NodeIndex from, NodeIndex to) |
Run a bi-directional Dijkstra search, which can be much faster than a typical Dijkstra, depending on the structure of the underlying graph. It should be at least 2x faster when using 2 threads, but in practice it can be much faster. Eg. if the graph represents 3D points in the space and the distance is the Euclidian distance, the search space grows like the cubic power of the search radius, so the bi-directional Dijkstra can be expected to be 2^3 = 8 times faster than the standard one.
Definition at line 42 of file bidirectional_dijkstra.h.
| GraphType::ArcIndex operations_research::BidirectionalDijkstra< GraphType, DistanceType >::ArcIndex |
Definition at line 45 of file bidirectional_dijkstra.h.
| GraphType::NodeIndex operations_research::BidirectionalDijkstra< GraphType, DistanceType >::NodeIndex |
Definition at line 44 of file bidirectional_dijkstra.h.
| operations_research::BidirectionalDijkstra< GraphType, DistanceType >::BidirectionalDijkstra | ( | const GraphType * | forward_graph, |
| const std::vector< DistanceType > * | forward_arc_lengths, | ||
| const GraphType * | backward_graph, | ||
| const std::vector< DistanceType > * | backward_arc_lengths ) |
IMPORTANT: Both arguments must outlive the class. The arc lengths cannot be negative and the vector must be of the correct size (both preconditions are CHECKed). Two graphs are needed, for the forward and backward searches. Both graphs must have the same number of nodes. If you want to perform the search on a symmetric graph, you can simply provide it twice here, ditto for the arc lengths.
Quickly verify that the arc lengths are non-negative.
Definition at line 182 of file bidirectional_dijkstra.h.
|
inline |
Shortcut for the common case when there is a single source and a single destination: in that case, source and destination cost don't matter.
Definition at line 120 of file bidirectional_dijkstra.h.
| std::string operations_research::BidirectionalDijkstra< GraphType, DistanceType >::PathDebugString | ( | const Path & | path | ) | const |
Returns a very nice debug string of the bidirectional path, eg: 0 –(#4:3.2)--> 1 –(#2:1.3)--> [5] <–(#8:5.6)– 9 <–(#0:1.3)– 3 where the text in () is an arc's index followed by its length. Returns "<NO PATH>" for empty paths.
Definition at line 211 of file bidirectional_dijkstra.h.
| std::vector< typename GraphType::NodeIndex > operations_research::BidirectionalDijkstra< GraphType, DistanceType >::PathToNodePath | ( | const Path & | path | ) | const |
Converts the rich 'Path' structure into a simple node path, where the nodes go from the source to the destination (i.e. the backward path is reversed).
Definition at line 229 of file bidirectional_dijkstra.h.
| BidirectionalDijkstra< GraphType, DistanceType >::Path operations_research::BidirectionalDijkstra< GraphType, DistanceType >::SetToSetShortestPath | ( | const std::vector< NodeDistance > & | sources, |
| const std::vector< NodeDistance > & | destinations ) |
Finds the shortest path between two sets of nodes with costs, and returns a description of it as two half-paths of arcs (one in the forward graph, one in the backward graph) meeting at a "meeting point" node.
When choosing the shortest path, the source and destination "initial distances" are taken into account: the overall path length is the sum of those and of the arc lengths. Note that this supports negative initial distances, as opposed to arc lengths which must be non-negative.
Corner case: if a node is present several times in "sources" or in "destinations", only the entry with the smallest distance is taken into account.
Disable thread safety analysis in this function, because there's no multi-threading within its body, per se: the multi-threading work is solely within PerformHalfSearch().
Initialize the fields that must be ready before both searches start.
If we're here, we have a new best distance for the current source. We also need to re-push it in the queue, since the distance changed.
Start the Dijkstras!
Wait for the two searches to finish.
Clean up the rest of the search, sparsely. "is_settled" can't be cleaned in PerformHalfSearch() because it is needed by the other half-search (which might be still ongoing when the first half-search finishes), so we have to do it when both searches have ended. So we also clean the auxiliary field "reached_nodes" and the sibling field "is_reached" here too. Ditto for "is_source".
Extract the shortest path from the meeting point.
Definition at line 246 of file bidirectional_dijkstra.h.
1.12.0