Module rs_graph::shortestpath::dijkstra

Dijkstra's shortest path algorithm.

Dijkstra's algorithm computes the shortest path from some start node $s \in V$ to all other nodes in (directed or undirected) graph. Each edge is assigned a non-negative weight (or length) $w \colon E \to \mathbb{R}_+$.

Dijkstra's algorithm is essentially an A*-search using the zero potential (heuristic) for all nodes.

Example

use rs_graph::{LinkedListGraph, Builder, EdgeVec, traits::*};
use rs_graph::adjacencies::Neighbors;
use rs_graph::shortestpath::dijkstra;
use rs_graph::string::from_ascii;

let data = from_ascii::<LinkedListGraph>(r"
    a-----9-----b
   / \           \
  |   2           6
  |    \           \
 14     c-----8-----d
  |    / \         /
  |   9  10      15
   \ /     \     /
    e----7--f----
").unwrap();
let g = data.graph;
let weights = data.weights;
let nodes = data.nodes;
let a = nodes[&'a'];
let b = nodes[&'b'];
let c = nodes[&'c'];
let d = nodes[&'d'];
let e = nodes[&'e'];
let f = nodes[&'f'];

let mut preds: Vec<_> = dijkstra::start(&Neighbors(&g), e, |e| weights[e.index()])
    .map(|(u, e, d)| {
        let uv = g.enodes(e);
        if uv.0 == u { (uv.1, u, d) } else { (uv.0, u, d) }
    })
    .collect();

assert_eq!(preds, vec![(e,f,7), (e,c,9), (c,a,11), (c,d,17), (a,b,20)]);

let (path, dist) = dijkstra::find_undirected_path(&g, e, b, |e| weights[e.index()]).unwrap();

assert_eq!(dist, 20);

let path = path
    .into_iter()
    .map(|e| g.enodes(e))
    .map(|(u,v)| if g.node_id(u) < g.node_id(v) { (u,v) } else { (v,u) })
    .collect::<Vec<_>>();
assert_eq!(path, vec![(c,e), (a,c), (a,b)]);

Structs

NoHeur

Internal type used when no heuristic is required.

Functions

find_directed_path	Run a Dijkstra-search on a directed graph and return the path.
find_undirected_path	Run a Dijkstra-search on an undirected graph and return the path.
start	Start and return an Dijkstra-iterator using default data structures.
start_directed	Start a Dijkstra-search on a directed graph.
start_generic	Start and return an Dijkstra-iterator with a custom accumulator and custom data structures.
start_undirected	Start a Dijkstra-search on a undirected graph.
start_with_data	Start and return an Dijkstra-iterator with custom data structures.

Type Definitions

Dijkstra	Dijkstra search iterator.
DijkstraDefault	The Dijkstra-iterator with default types.