Function dijkstra_search

pub fn dijkstra_search<G, I, F, K, E, H, C>(
    graph: G,
    starts: I,
    edge_cost: F,
    visitor: H,
) -> Result<C, E>
where
    G: IntoEdges + Visitable,
    G::NodeId: Eq + Hash,
    I: IntoIterator<Item = G::NodeId>,
    F: FnMut(G::EdgeRef) -> Result<K, E>,
    K: Measure + Copy,
    H: FnMut(DijkstraEvent<G::NodeId, &G::EdgeWeight, K>) -> C,
    C: ControlFlow,

Dijkstra traversal of a graph.

Starting points are the nodes in the iterator starts (specify just one start vertex x by using Some(x)).

The traversal emits discovery and finish events for each reachable vertex, and edge classification of each reachable edge. visitor is called for each event, see DijkstraEvent for possible values.

The return value should implement the trait ControlFlow, and can be used to change the control flow of the search.

Control Implements ControlFlow such that Control::Continue resumes the search. Control::Break will stop the visit early, returning the contained value. Control::Prune will stop traversing any additional edges from the current node and proceed immediately to the Finish event.

There are implementations of ControlFlow for (), and Result<C, E> where C: ControlFlow. The implementation for () will continue until finished. For Result, upon encountering an E it will break, otherwise acting the same as C.

*Panics if you attempt to prune a node from its Finish event.

The pseudo-code for the Dijkstra algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.

// G - graph, s - single source node, weight - edge cost function
DIJKSTRA(G, s, weight)
  let score be empty mapping
  let visited be empty set
  let Q be a priority queue
  score[s] := DEFAULT_COST
  PUSH(Q, (score[s], s))                // only score determines the priority
  while Q is not empty
    cost, u := POP-MIN(Q)
    if u in visited
      continue
    PUT(visited, u)                     // event: Discover(u, cost)
    for each _, v, w in OutEdges(G, u)  // v - target vertex, w - edge weight
      ...                               // event: ExamineEdge(u, v, w)
      if v in visited
        continue
      next_cost = cost + weight(w)
      if {(v is key in score)
          and (score[v] <= next_cost)}  // event: EdgeNotRelaxed(u, v, w)
        ...                             
      else:                             // v not scored or scored higher
        score[v] = next_cost            // event: EdgeRelaxed(u, v, w)
        PUSH(Q, (next_cost, v))
    end for                             // event: Finish(u)
  end while

Example returning Control.

Find the shortest path from vertex 0 to 5, and exit the visit as soon as we reach the goal vertex.

use rustworkx_core::petgraph::prelude::*;
use rustworkx_core::petgraph::graph::node_index as n;
use rustworkx_core::petgraph::visit::Control;

use rustworkx_core::traversal::{DijkstraEvent, dijkstra_search};

let gr: Graph<(), ()> = Graph::from_edges(&[
    (0, 1), (0, 2), (0, 3), (0, 4),
    (1, 3),
    (2, 3), (2, 4),
    (4, 5),
]);

// record each predecessor, mapping node → node
let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
let start = n(0);
let goal = n(5);
dijkstra_search(
    &gr,
    Some(start),
    |edge| -> Result<usize, ()> {
        Ok(1)
    },
    |event| {
        match event {
            DijkstraEvent::Discover(v, _) => {
                if v == goal {
                    return Control::Break(v);
                }   
            },
            DijkstraEvent::EdgeRelaxed(u, v, _) => {
                predecessor[v.index()] = u;
            },
            _ => {}
        };

        Control::Continue
    },
).unwrap();

let mut next = goal;
let mut path = vec![next];
while next != start {
    let pred = predecessor[next.index()];
    path.push(pred);
    next = pred;
}
path.reverse();
assert_eq!(&path, &[n(0), n(4), n(5)]);