Fast Paths

最著名的计算最短路径的算法可能是Dijkstra算法和A*算法。然而，通过预处理图，可以实现更快的最短路径计算。

Fast Paths使用了收缩层次结构，这是最短路径计算中已知的最快的加速技术之一。它特别适合计算道路网络中的最短路径，但也可以用于任何具有正的非零边权重的有向图。

安装

在Cargo.toml

[dependencies]
fast_paths = "0.2.0"

基本用法

// begin with an empty graph
let mut input_graph = InputGraph::new();

// add an edge between nodes with ID 0 and 6, the weight of the edge is 12.
// Note that the node IDs should be consecutive, if your graph has N nodes use 0...N-1 as node IDs,
// otherwise performance will degrade.
input_graph.add_edge(0, 6, 12);
// ... add many more edges here

// freeze the graph before using it (you cannot add more edges afterwards, unless you call thaw() first)
input_graph.freeze();

// prepare the graph for fast shortest path calculations. note that you have to do this again if you want to change the
// graph topology or any of the edge weights
let fast_graph = fast_paths::prepare(&input_graph);

// calculate the shortest path between nodes with ID 8 and 6 
let shortest_path = fast_paths::calc_path(&fast_graph, 8, 6);

match shortest_path {
    Some(p) => {
        // the weight of the shortest path
        let weight = p.get_weight();
        
        // all nodes of the shortest path (including source and target)
        let nodes = p.get_nodes();
    },
    None => {
        // no path has been found (nodes are not connected in this graph)
    }
}

批量计算最短路径

对于批量计算最短路径，上述方法效率低下。您应该保留PathCalculator对象以执行多个查询

// ... see above
// create a path calculator (note: not thread-safe, use a separate object per thread)
let mut path_calculator = fast_paths::create_calculator(&fast_graph);
let shortest_path = path_calculator.calc_path(&fast_graph, 8, 6);

计算多个源和目标之间的路径

当我们想考虑多个源或目标时，也可以有效地计算最短路径

// ... see above
// we want to either start at node 2 or 3 both of which carry a different initial weight
let sources = vec![(3, 5), (2, 7)];
// ... and go to either node 6 or 8 which also both carry a cost upon arrival
let targets = vec![(6, 2), (8, 10)];
// calculate the path with minimum cost that connects any of the sources with any of the targets while taking into 
// account the initial weights of each source and node
let shortest_path = path_calculator.calc_path_multiple_sources_and_targets(&fast_graph, sources, targets);

序列化准备好的图

FastGraph实现了标准的Serde序列化。

为了能够在32位WebAssembly环境中使用该图，需要在64位系统上准备时将其转换为32位表示。这可以通过以下两种方法实现，但仅适用于不超过32位限制的图，即节点数和边数以及所有权重都必须低于2^32。

use fast_paths::{deserialize_32, serialize_32, FastGraph};

#[derive(Serialize, Deserialize)]
struct YourData {
    #[serde(serialize_with = "serialize_32", deserialize_with = "deserialize_32")]
    graph: FastGraph,
    // the rest of your struct
}

修改后准备图

可以使用固定的节点排序快速完成图准备，这只是一个节点ID的排列。可以这样操作

let fast_graph = fast_paths::prepare(&input_graph);
let node_ordering = fast_graph.get_node_ordering();

let another_fast_graph = fast_paths::prepare_with_order(&another_input_graph, &node_ordering);

为了让它正常工作，another_input_graph必须与input_graph具有相同的节点数，否则prepare_with_order将返回错误。此外，如果input_graph和another_input_graph彼此相似，例如只更改了一些边的权重，性能才能被接受。

基准测试

FastPaths在消费级笔记本电脑的单核上使用DIMACS实现挑战图的公路网络运行。以下图用于基准测试

最短路径计算时间是在100k随机路由查询的平均值上。基准测试是在Macbook Pro M1 Max上使用Rust 1.74.1运行的。运行这些基准测试的代码可以在benchmarks分支上找到。

测试套件中还包含了一些使用较小地图的基准测试。您可以按以下方式运行它们

export RUST_TEST_THREADS=1; cargo test --release -- --ignored --nocapture

图限制

• 环边（从节点A到节点A）将被忽略，因为我们只考虑正的非零边权重，它们不能成为最短路径的一部分
• 如果图中有重复的边（从节点A到节点B的多个边），则只考虑权重最低的边

特别感谢

感谢来自Dustin Carlino和A/B Street的特别感谢！

许可证

本项目受以下任一许可证的许可

• Apache License, Version 2.0, (LICENSE-APACHE或https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT或http://opensource.org/licenses/MIT)

任选其一。

贡献

除非您明确声明，否则您有意提交给fast_paths的任何贡献，根据Apache-2.0许可证定义，将根据上述内容双许可，无需任何附加条款或条件。