Function rs_graph::shortestpath::floydwarshall::directed

pub fn directed<'a, G, W, F>(
    g: &'a G, 
    weights: F
) -> Vec<Vec<Option<(W, G::Node)>>> where
    G: IndexDigraph<'a>,
    W: NumAssign + Ord + Copy + Bounded,
    F: Fn(G::Edge) -> W, 

Solve the All-Pairs-Shortest-Path-Problem with the algorithm of Floyd and Warshall on a directed graph.

Returns a 2D vector with entries (dist, pred) for each pair of nodes where dist is the length of the shortest path and pred is the predecessor of the last node.

Example

use rs_graph::{LinkedListGraph, Buildable, Builder, EdgeVec};
use rs_graph::shortestpath::floydwarshall;
use rs_graph::traits::IndexGraph;

let mut weights = vec![];
let g = LinkedListGraph::<usize>::new_with(|b| {
    let nodes = b.add_nodes(5);
    for &(u,v,w) in [(0,1,6), (0,2,5),
                     (1,2,7), (1,3,3), (1,4,-2),
                     (2,3,-4), (3,4,8),
                     (3,1,-1),
                     (4,0,2), (4,3,7), ].iter()
    {
        b.add_edge(nodes[u], nodes[v]);
        weights.push(w);
    }
});

let result = floydwarshall::directed(&g, |e| weights[g.edge_id(e)]);
let mut s = [[0; 5]; 5];
for (i,v) in result.into_iter().enumerate() {
    for (j,d) in v.into_iter().enumerate() {
        s[i][j] = d.unwrap().0;
    }
}
assert_eq!(s, [[ 0, 0, 5, 1,-2],
               [ 0, 0, 5, 1,-2],
               [-5,-5, 0,-4,-7],
               [-1,-1, 4, 0,-3],
               [ 2, 2, 7, 3, 0],]);