Struct rs_graph::shortestpath::dijkstra::Dijkstra
[−]
[src]
pub struct Dijkstra<'a, G, W, N, E, H = BinHeap<NodeItem<N, E, W>, usize>> where
G: 'a + IndexGraph<'a, Node = N, Edge = E>,
N: 'a + Node + Hash,
E: 'a + Edge,
W: NumAssign + Ord + Copy,
H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>, { /* fields omitted */ }
Dijkstra's shortest path algorithm.
Methods
impl<'a, G, W, N, E, H> Dijkstra<'a, G, W, N, E, H> where
G: 'a + IndexGraph<'a, Node = N, Edge = E>,
N: 'a + Node + Hash,
E: 'a + Edge,
W: NumAssign + Ord + Copy,
H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,
[src]
G: 'a + IndexGraph<'a, Node = N, Edge = E>,
N: 'a + Node + Hash,
E: 'a + Edge,
W: NumAssign + Ord + Copy,
H: Heap<Key = NodeItem<G::Node, G::Edge, W>, Item = usize>,
fn new(g: &'a G) -> Self
Create new data structure for running Dijkstra on a graph.
fn undirected<'b>(
&mut self,
weights: &EdgeSlice<'a, 'b, G, W>,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>
&mut self,
weights: &EdgeSlice<'a, 'b, G, W>,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>
Compute a shortest path with Dijkstra's algorithm on an undirected graph.
Each edge can be traversed in both directions with the same weight.
weights
the (non-negative) edge weightssrc
the source nodesnk
the sink node
Return the incoming edge for each node forming the shortest path tree.
fn bidirected<'b>(
&mut self,
weights: &BiEdgeSlice<'a, 'b, G, W>,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)> where
G: IndexNetwork<'a>,
&mut self,
weights: &BiEdgeSlice<'a, 'b, G, W>,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)> where
G: IndexNetwork<'a>,
Solve shortest path with Dijkstra as bidirected graph.
The graph is considered as bidirected graph with different weights for each direction.
weights
the (non-negative) arc weightssrc
the source nodesnk
the sink node
Return the incoming arc for each node forming the shortest path tree.
fn directed<'b>(
&mut self,
weights: &EdgeSlice<'a, 'b, G, W>,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)> where
G: Digraph<'a>,
&mut self,
weights: &EdgeSlice<'a, 'b, G, W>,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)> where
G: Digraph<'a>,
Solve shortest path with Dijkstra as directed graph.
The graph is considered directed, travel is only allowed along outgoing edges.
weights
the (non-negative) arc weightssrc
the source nodesnk
the sink node
Return the incoming arc for each node forming the shortest path tree.
fn generic<Weights, F, Neighs, It>(
&mut self,
weights: &Weights,
src: G::Node,
snk: Option<G::Node>,
accum: F,
neighs: Neighs
) -> Vec<(G::Node, G::Edge)> where
Weights: Index<G::Edge, Output = W>,
F: Fn(W, W) -> W,
Neighs: Fn(&'a G, G::Node) -> It,
It: Iterator<Item = (G::Edge, G::Node)>,
&mut self,
weights: &Weights,
src: G::Node,
snk: Option<G::Node>,
accum: F,
neighs: Neighs
) -> Vec<(G::Node, G::Edge)> where
Weights: Index<G::Edge, Output = W>,
F: Fn(W, W) -> W,
Neighs: Fn(&'a G, G::Node) -> It,
It: Iterator<Item = (G::Edge, G::Node)>,