Function graphalgs::shortest_path::johnson

pub fn johnson<G, F, K>(
    graph: G,
    edge_cost: F
) -> Result<Vec<Vec<K>>, NegativeCycle>where
    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable + Visitable,
    G::NodeId: Eq,
    F: FnMut(G::EdgeRef) -> K,
    K: FloatMeasure + Sub<K, Output = K>,

Johnson algorithm for all pairs shortest path problem.

Сompute the lengths of shortest paths in a weighted graph with positive or negative edge weights, but no negative cycles.

Arguments

• graph: weighted graph.
• edge_cost: closure that returns cost of a particular edge.

Returns

• Err: if graph contains negative cycle.
• Ok: matrix Vec<Vec<K>> of shortest distances, in cell (i, j) of which the length of the shortest path from node i to node j is stored.

Examples

use graphalgs::shortest_path::johnson;
use petgraph::Graph;

let inf = f32::INFINITY;

let graph = Graph::<(), f32>::from_edges(&[
    (0, 1, 2.0), (1, 2, 10.0), (1, 3, -5.0),
    (3, 2, 2.0), (2, 3, 20.0),
]);

// Graph represented with the weight of each edge.
//        2
//  (0)------->(1)
//    ___10____/|
//   /          | -5
//   v          v
//  (2)<--2----(3)
//   \----20--->/

assert_eq!(
    johnson(&graph, |edge| *edge.weight()),
    Ok(vec![vec![0.0, 2.0, -1.0, -3.0],
            vec![inf, 0.0, -3.0, -5.0],
            vec![inf, inf,  0.0, 20.0],
            vec![inf, inf,  2.0,  0.0]])
);


// Negative cycle.
let graph = Graph::<(), f32>::from_edges(&[
    (0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)]);

assert!(johnson(&graph, |edge| *edge.weight()).is_err());