Function rs_graph::shortestpath::dijkstra::undirected [−][src]
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,
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]);