Struct traitgraph_algo::dijkstra::Dijkstra

pub struct Dijkstra<Graph: GraphBase, WeightType: DijkstraWeight, NodeWeights: NodeWeightArray<WeightType>, Heap: DijkstraHeap<WeightType, Graph::NodeIndex>> { /* private fields */ }

Data structure for Dijkstra’s shortest path algorithm.

This variant of Dijkstra’s algorithm supports only computing the length of a shortest path, and not the shortest path itself. Therefore it does not need an array of back pointers for each node, saving a bit of memory.

Implementations

impl<WeightType: DijkstraWeight + Eq + Debug, EdgeData: DijkstraWeightedEdgeData<WeightType>, Graph: StaticGraph<EdgeData = EdgeData>, NodeWeights: NodeWeightArray<WeightType>, Heap: DijkstraHeap<WeightType, Graph::NodeIndex>> Dijkstra<Graph, WeightType, NodeWeights, Heap>

pub fn new(graph: &Graph) -> Self

Create the data structures for the given graph.

pub fn shortest_path_lens<TargetMap: DijkstraTargetMap<Graph>, DijkstraPerformance: DijkstraPerformanceData>( &mut self, graph: &Graph, source: Graph::NodeIndex, targets: &TargetMap, target_amount: usize, max_weight: WeightType, forbid_source_target: bool, distances: &mut Vec<(Graph::NodeIndex, WeightType)>, max_node_weight_data_size: usize, max_heap_data_size: usize, performance_data: DijkstraPerformance ) -> DijkstraStatus<DijkstraPerformance>

Compute the shortest paths from source to all targets, with given maximum weight.

max_node_weight_data_size: the maximum number of nodes for which a weight can be stored before the search aborts.