Struct traitgraph::algo::dijkstra::Dijkstra

pub struct Dijkstra<Graph: GraphBase, NodeWeights> { /* fields omitted */ }

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<EdgeData: WeightedEdgeData, Graph: StaticGraph<EdgeData = EdgeData>, NodeWeights: NodeWeightArray<usize>> Dijkstra<Graph, NodeWeights>

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

Create the data structures for the given graph.

pub fn shortest_path_lens<TargetMap: DijkstraTargetMap<Graph>>(
    &mut self,
    graph: &Graph,
    source: Graph::NodeIndex,
    targets: &TargetMap,
    target_amount: usize,
    max_weight: usize,
    forbid_source_target: bool,
    distances: &mut Vec<(Graph::NodeIndex, usize)>
)

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