Function rs_graph::shortestpath::dijkstra::undirected
source · pub fn undirected<'a, 'b, G, Ws, W>(
g: &'a G,
weights: Ws,
src: G::Node,
snk: Option<G::Node>
) -> Vec<(G::Node, G::Edge)>where
G: IndexGraph<'a>,
G::Node: Hash,
Ws: EdgeMap<'a, G, W>,
W: NumAssign + Ord + Copy,
Expand description
Compute a shortest path with Dijkstra’s algorithm on an undirected graph.
Each edge can be traversed in both directions with the same weight.
g
the graphweights
the (non-negative) edge weightssrc
the source nodesnk
the sink node
Return the incoming edge for each node forming the shortest path tree.
Example
use rs_graph::*;
use rs_graph::shortestpath::dijkstra;
let mut g = LinkedListGraph::<u32>::default();
let mut weights: Vec<usize> = vec![];
let nodes: Vec<_> = (0..6).map(|_| g.add_node()).collect();
for &(u,v,w) in [(0,1,7), (0,2,9), (0,3,14),
(1,2,10), (1,3,15),
(2,3,11), (2,5,2),
(3,4,6), (5,4,9)].iter() {
g.add_edge(nodes[u], nodes[v]);
weights.push(w);
}
let preds = dijkstra::undirected(&g, EdgeVec::from(weights), nodes[0], Some(nodes[4]));
assert_eq!(g.src(preds.iter().find(|&&(u,_)| u==nodes[2]).unwrap().1), nodes[0]);
assert_eq!(g.src(preds.iter().find(|&&(u,_)| u==nodes[5]).unwrap().1), nodes[2]);
assert_eq!(g.src(preds.iter().find(|&&(u,_)| u==nodes[4]).unwrap().1), nodes[5]);