Module rs_graph::shortestpath::bidijkstra

Dijkstra's bidirectional shortest path algorithm.

The bidirectional Dijkstra algorithm starts the search at the start and the end node simultaneously. The shortest path is found if the two searches meet.

This is actually a bidirectional A*-search with the all zero node potential.

Example

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

let data = from_ascii::<LinkedListGraph>(r"
    a-----9-----b
   / \           \
  |   2           6
  |    \           \
 14     c-----8-----d
  |    / \         /
  |  10  12      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'];

// ensure that the nodes are visited in the correct order
let visited = bidijkstra::start(&Neighbors(&g), &Neighbors(&g), e, b, |e| weights[e.index()])
    .map(|(u, _ , d)| (u, d))
    .collect::<Vec<_>>();
assert_eq!(visited, vec![(d, 6), (f, 7), (a, 9), (c, 10), (a, 12)]);

// obtain the shortest path directly.
let (path, dist) = bidijkstra::find_undirected_path(&g, e, b, |e| weights[e.index()]).unwrap();

assert_eq!(dist, 21);

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

Re-exports

pub use crate::shortestpath::dijkstra::NoHeur;

Functions

find_directed_path	Run a bidirectional Dijkstra-search on an directed graph and return the path.
find_undirected_path	Run a bidirectional Dijkstra-search on an undirected graph and return the path.
start	Compute a shortest path with bidirectional Dijkstra algorithm using default data structures.
start_directed	Start a bidirectional Dijkstra-search on a directed graph.
start_undirected	Start a bidirectional Dijkstra-search on an undirected graph.
start_with_data	Run bidirectional Dijkstra on a generic graph with custom data structures.

Type Definitions

BiDijkstra	Bi-Dijkstra search iterator.
BiDijkstraDefault	Bi-Dijkstra search iterator with default data structures.