Function dijkstra 

pub fn dijkstra<E, T>(
    n: usize,
    edges: &[E],
    s: usize,
) -> (Vec<Option<T>>, Vec<Option<usize>>)
where
    E: Edge<T>,
    T: Clone + Default + Ord + Debug,

dijkstra はあるひとつの頂点から全ての頂点への最短距離を計算します。

返り値 (dist, prev) はそれぞれ以下です。

• dist[t]: s から t までの最短距離
• prev[t]: s を根とする最短経路木における t の親頂点

prev をゴールの頂点からたどることで、最短経路を復元できます。

s から t への経路が存在しない場合 dist[t]、prev[t] は None です。

Examples

use dijkstra::{Edge, ConstEdge, dijkstra};
let edges = vec![
    ConstEdge::new(0, 1, 1),
    ConstEdge::new(0, 2, 1),
    ConstEdge::new(1, 2, 1),
    ConstEdge::new(2, 3, 1),
];
//
//     0 -----> 1 -----> 2 -----> 3
//     |                 ^
//     |                 |
//     +-----------------+
//
let (dist, prev) = dijkstra(4, &edges, 0);
assert_eq!(dist[0], Some(0));
assert_eq!(dist[1], Some(1));
assert_eq!(dist[2], Some(1));
assert_eq!(dist[3], Some(2));
assert_eq!(prev[0], None);
assert_eq!(prev[1], Some(0));
assert_eq!(prev[2], Some(0));
assert_eq!(prev[3], Some(2));