#matrix #floyd #warshall #informatics #graphics

nightly generic-floyd-warshall

为类似数组的类型实现的Floyd-Warshall算法

2个不稳定版本

0.2.0 2020年10月4日
0.1.0 2020年9月30日

#2343 in 算法

MIT 许可证

5KB

泛型Floyd-Warshall算法

generic-floyd-warshall旨在与Rust语言中的核心类似数组的原始类型和类型(如Vectors)一起使用,以便可以使用类似数组的类型来形成矩阵,并正确处理Floyd-Warshall算法在这些矩阵上的执行。

此外,generic-floyd-warshall旨在与实现std::ops::{ Add, Index, IndexMut }std::cmp::PartialOrd的用户定义类型一起使用。

fn main() {
    let graph = vec![
        vec![0.0, f32::INFINITY, -2.0, f32::INFINITY],
        vec![4.0, 0.0, 3.0, f32::INFINITY],
        vec![f32::INFINITY, f32::INFINITY, 0.0, 2.0],
        vec![f32::INFINITY, -1.0, f32::INFINITY, 0.0]
    ];

    let expected = vec![
        vec![0.0, -1.0, -2.0, 0.0],
        vec![4.0, 0.0, 2.0, 4.0],
        vec![5.0, 1.0, 0.0, 2.0],
        vec![3.0, -1.0, 1.0, 0.0]
    ];

    let len = graph.len();
    let mut calculated = graph.clone();

    floyd_warshall(&mut calculated, len);

    assert_eq!(expected, calculated);
}

此crate处于实验阶段。欢迎批评和建议。

无运行时依赖