Function rs_graph::shortestpath::floydwarshall::directed

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

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, Builder, EdgeVec};
use rs_graph::shortestpath::floydwarshall;

let mut g = LinkedListGraph::<usize>::new();
let nodes = g.add_nodes(5);
let mut weights = vec![];
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()
{
    g.add_edge(nodes[u], nodes[v]);
    weights.push(w);
}

let result = floydwarshall::directed(&g, EdgeVec::from(weights));
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],]);