operations_research::BidirectionalDijkstra< GraphType, DistanceType >::Path Struct Reference

#include <bidirectional_dijkstra.h>

Public Attributes
NodeIndex	meeting_point
	The node where the two half-paths meet. -1 if no path exists.
std::vector< ArcIndex >	forward_arc_path
std::vector< ArcIndex >	backward_arc_path

Detailed Description

template<typename GraphType, typename DistanceType>
struct operations_research::BidirectionalDijkstra< GraphType, DistanceType >::Path

Represents a bidirectional path. See SetToSetShortestPath() to understand why this data structure is like this.

Definition at line 76 of file bidirectional_dijkstra.h.

Member Data Documentation

backward_arc_path

template<typename GraphType , typename DistanceType >

std::vector<ArcIndex> operations_research::BidirectionalDijkstra< GraphType, DistanceType >::Path::backward_arc_path

Ditto, but those are arcs in the backwards graph, from a destination to the meeting point.

Definition at line 89 of file bidirectional_dijkstra.h.

forward_arc_path

template<typename GraphType , typename DistanceType >

std::vector<ArcIndex> operations_research::BidirectionalDijkstra< GraphType, DistanceType >::Path::forward_arc_path

The forward arc path from a source to "meeting_point". Might be empty if no path is found, or if "meeting_point" is a source (the reverse implication doesn't work: even if meeting_point is a source Sa, there might be another source Sb != Sa such that the path [Sb....Sa] is shorter than [Sa], because of the initial distances).

Definition at line 85 of file bidirectional_dijkstra.h.

meeting_point

template<typename GraphType , typename DistanceType >

NodeIndex operations_research::BidirectionalDijkstra< GraphType, DistanceType >::Path::meeting_point

The node where the two half-paths meet. -1 if no path exists.

Definition at line 78 of file bidirectional_dijkstra.h.

---

The documentation for this struct was generated from the following file:

• ortools/graph/bidirectional_dijkstra.h