Function floyd_warshall 

pub fn floyd_warshall<G>(graph: &G) -> Result<Vec<Vec<f64>>, GraphError>
where
    G: Graph<Weight = f64>,

Runs the Floyd-Warshall all-pairs shortest-path algorithm.

Returns a V × V distance matrix indexed by node position (the index of the NodeId as returned by NodeId::index). Entry [i][j] is the shortest distance from node i to node j, or f64::INFINITY if no path exists.

Errors

Returns GraphError::NegativeCycle if a negative-weight cycle is detected (i.e., dist[i][i] < 0 for any i after the algorithm).

Complexity

O(V³) time, O(V²) space.

Examples

use graph_core::{AdjacencyList, Graph};
use graph_shortest_path::floyd_warshall;

let mut g: AdjacencyList<()> = AdjacencyList::directed();
let a = g.add_node(());  // index 0
let b = g.add_node(());  // index 1
let c = g.add_node(());  // index 2
g.add_edge(a, b, 3.0).unwrap();
g.add_edge(b, c, 2.0).unwrap();
g.add_edge(a, c, 10.0).unwrap();

let dist = floyd_warshall(&g).unwrap();
assert_eq!(dist[0][2], 5.0); // a→b→c costs 5, cheaper than a→c at 10
assert_eq!(dist[1][0], f64::INFINITY); // no path back