spokes

网络和网络流优化工具

简介

以下示例基于以下图形 ，来源于 维基百科。

在这里，目标是找到以节点 0 为根的最短路径树。在示例中，验证了节点 0 到节点 4 的距离为 20。

use spokes::{Network, algorithms::{dijkstra_shortest_path, Distance}, ArcStorage};

let mut network: Network<usize, (), u16> = Network::new();
network.add_nodes((0..6).map(|i| (i, ())));
network.add_arcs([
    (0, 1, 7), (1, 0, 7),
    (0, 5, 14), (5, 0, 14),
    (0, 2, 9), (2, 0, 9),
    (1, 2, 10), (2, 1, 10),
    (1, 3, 15), (3, 1, 15),
    (2, 5, 2), (5, 2, 2),
    (2, 3, 11), (3, 2, 11),
    (3, 4, 6), (4, 3, 6),
    (4, 5, 9), (5, 4, 9),
]);

let shortest_path_tree = dijkstra_shortest_path(&network, 0);

assert_eq!(shortest_path_tree.node(&4), Some(&Distance::Finite(20)));

let mut expected_network: Network<usize, Distance<u16>, ()> = Network::new();

expected_network.add_nodes([
    (0, Distance::Finite(0)),
    (1, Distance::Finite(7)),
    (2, Distance::Finite(9)),
    (3, Distance::Finite(20)),
    (4, Distance::Finite(20)),
    (5, Distance::Finite(11)),
]);

expected_network.add_arcs([
    (1, 0),
    (2, 0),
    (3, 2),
    (5, 2),
    (4, 5),
]);

assert_eq!(shortest_path_tree, expected_network);

许可证：MIT 或 Apache-2.0