Function graphalgs::shortest_path::shortest_distances

pub fn shortest_distances<G>(graph: G, start: G::NodeId) -> Vec<f32>where
    G: Visitable + NodeIndexable + IntoEdges + IntoNeighbors,

The lengths of the shortest paths from the start vertex to all the others.

The algorithm is based on BFS, and the path length is equal to the number of edges in this path. Returns Vec<f32>, the i-th position of which stores the length of the path from the start node to the node with index i. If it is impossible to get from the vertex x to the vertex y, then the distance from x to y will be equal to f32::INFINITY. Time complexity: O(|V| + |E|), where |V| is the number of vertices, and |E| is the number of edges in the graph.

Examples

use graphalgs::shortest_path::shortest_distances;
use petgraph::Graph;

let inf = f32::INFINITY;
let graph = Graph::<u8, ()>::from_edges(&[(0, 1), (0, 2), (1, 2)]);

assert_eq!(shortest_distances(&graph, 0.into()), vec![0.0, 1.0, 1.0]);
assert_eq!(shortest_distances(&graph, 1.into()), vec![inf, 0.0, 1.0]);
assert_eq!(shortest_distances(&graph, 2.into()), vec![inf, inf, 0.0]);