#include <routing_neighborhoods.h>

Public Member Functions
	ShortestPathOnAlternatives (int num_nodes, std::vector< std::vector< int64_t > > alternative_sets, RoutingTransitCallback2 arc_evaluator)

bool	HasAlternatives (int node) const

absl::Span< const int64_t >	GetShortestPath (int64_t source, int64_t sink, absl::Span< const int64_t > chain)

Detailed Description

Class used to compute shortest paths on DAGs formed by chains of alternative node sets.

Definition at line 109 of file routing_neighborhoods.h.

Constructor & Destructor Documentation

◆ ShortestPathOnAlternatives()

operations_research::ShortestPathOnAlternatives::ShortestPathOnAlternatives	(	int	num_nodes,
		std::vector< std::vector< int64_t > >	alternative_sets,
		RoutingTransitCallback2	arc_evaluator )

Definition at line 168 of file routing_neighborhoods.cc.

Member Function Documentation

◆ GetShortestPath()

absl::Span< const int64_t > operations_research::ShortestPathOnAlternatives::GetShortestPath	(	int64_t	source,
		int64_t	sink,
		absl::Span< const int64_t >	chain )

Returns the shortest path between source and sink, going through the DAG formed by the alternative nodes of the chain. The path omits source and sink.

Updating values "layer" by "layer" (each one is fully connected to the previous one).

Get the predecessor in the shortest path to sink in the last layer.

Build the path from predecessors on the shortest path.

Definition at line 195 of file routing_neighborhoods.cc.

◆ HasAlternatives()

bool operations_research::ShortestPathOnAlternatives::HasAlternatives ( int node ) const

Definition at line 189 of file routing_neighborhoods.cc.

The documentation for this class was generated from the following files: