Module rs_graph::shortestpath::dijkstra

source ·
Expand description

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, 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), g.id2node(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) }
    })
    .map(|(u, v, d)| (g.node_id(u), g.node_id(v), 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, g.id2node(e), g.id2node(b), |e| weights[e.index()]).unwrap();

assert_eq!(dist, 20);

let path = path
    .into_iter()
    .map(|e| g.enodes(e))
    .map(|(u,v)| (g.node_id(u), g.node_id(v)))
    .map(|(u,v)| if u < 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 Aliases