petgraph/
dijkstra.rs

1use std::collections::{
2    HashMap,
3    BinaryHeap,
4};
5use std::collections::hash_map::Entry::{
6    Occupied,
7    Vacant,
8};
9
10use std::hash::Hash;
11
12use scored::MinScored;
13use super::visit::{
14    Visitable,
15    VisitMap,
16    IntoEdges,
17    EdgeRef,
18};
19use algo::Measure;
20
21/// [Generic] Dijkstra's shortest path algorithm.
22///
23/// Compute the length of the shortest path from `start` to every reachable
24/// node.
25///
26/// The graph should be `Visitable` and implement `IntoEdges`. The function
27/// `edge_cost` should return the cost for a particular edge, which is used
28/// to compute path costs. Edge costs must be non-negative.
29///
30/// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
31/// cost is calculated.
32///
33/// Returns a `HashMap` that maps `NodeId` to path cost.
34pub fn dijkstra<G, F, K>(graph: G, start: G::NodeId, goal: Option<G::NodeId>,
35                         mut edge_cost: F)
36    -> HashMap<G::NodeId, K>
37    where G: IntoEdges + Visitable,
38          G::NodeId: Eq + Hash,
39          F: FnMut(G::EdgeRef) -> K,
40          K: Measure + Copy,
41{
42    let mut visited = graph.visit_map();
43    let mut scores = HashMap::new();
44    //let mut predecessor = HashMap::new();
45    let mut visit_next = BinaryHeap::new();
46    let zero_score = K::default();
47    scores.insert(start, zero_score);
48    visit_next.push(MinScored(zero_score, start));
49    while let Some(MinScored(node_score, node)) = visit_next.pop() {
50        if visited.is_visited(&node) {
51            continue
52        }
53        if goal.as_ref() == Some(&node) {
54            break
55        }
56        for edge in graph.edges(node) {
57            let next = edge.target();
58            if visited.is_visited(&next) {
59                continue
60            }
61            let mut next_score = node_score + edge_cost(edge);
62            match scores.entry(next) {
63                Occupied(ent) => if next_score < *ent.get() {
64                    *ent.into_mut() = next_score;
65                    //predecessor.insert(next.clone(), node.clone());
66                } else {
67                    next_score = *ent.get();
68                },
69                Vacant(ent) => {
70                    ent.insert(next_score);
71                    //predecessor.insert(next.clone(), node.clone());
72                }
73            }
74            visit_next.push(MinScored(next_score, next));
75        }
76        visited.visit(node);
77    }
78    scores
79}
petgraph/dijkstra.rs

petgraph/
dijkstra.rs
