Function rs_graph::shortestpath::dijkstra::undirected

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 graph
• weights the (non-negative) edge weights
• src the source node
• snk 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]);