探索图的捷径（Rust语言实现最短路径算法从零开始）

准备工作：安装 Rust

如果你还没安装 Rust，请访问 rust-lang.org 按照指引安装。安装完成后，你可以通过以下命令验证：

rustc --version

项目结构搭建

在终端中运行以下命令创建新项目：

cargo new shortest_path_tutorialcd shortest_path_tutorial

实现 Dijkstra 算法

我们将使用 BinaryHeap（最大堆）配合自定义比较逻辑来模拟最小堆。Rust 标准库没有直接提供最小堆，但我们可以通过取反距离值来实现。

首先，在 Cargo.toml 中添加依赖（本例不需额外依赖，但需注意标准库使用）：

接下来，编辑 src/main.rs 文件：

use std::collections::{BinaryHeap, HashMap};use std::cmp::Ordering;// 定义一个状态结构体，用于优先队列#[derive(Eq, PartialEq)]struct State {    cost: u32,    position: usize,}// 实现 Reverse Ordering：使 BinaryHeap 表现为最小堆impl Ord for State {    fn cmp(&self, other: &Self) -> Ordering {        // 注意：这里反向比较，因为 BinaryHeap 是最大堆        other.cost.cmp(&self.cost)            .then_with(|| self.position.cmp(&other.position))    }}impl PartialOrd for State {    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {        Some(self.cmp(other))    }}// 图表示：邻接表// graph[i] = [(neighbor, weight), ...]fn dijkstra(graph: &Vec<Vec<(usize, u32)>>, start: usize) -> Vec<u32> {    let mut dist: Vec<u32> = vec![u32::MAX; graph.len()];    let mut heap = BinaryHeap::new();    dist[start] = 0;    heap.push(State { cost: 0, position: start });    while let Some(State { cost, position }) = heap.pop() {        // 如果当前路径不是最优的，跳过        if cost > dist[position] {            continue;        }        // 遍历邻居        for &(next, weight) in &graph[position] {            let next_cost = cost + weight;            if next_cost < dist[next] {                dist[next] = next_cost;                heap.push(State { cost: next_cost, position: next });            }        }    }    dist}fn main() {    // 构建一个示例图：    // 节点 0 -> 1 (权重 4)    // 节点 0 -> 2 (权重 1)    // 节点 1 -> 3 (权重 1)    // 节点 2 -> 1 (权重 2)    // 节点 2 -> 3 (权重 5)    let graph = vec![        vec![(1, 4), (2, 1)],     // 节点 0        vec![(3, 1)],             // 节点 1        vec![(1, 2), (3, 5)],     // 节点 2        vec![],                   // 节点 3    ];    let start = 0;    let distances = dijkstra(&graph, start);    println!("从节点 {} 到各节点的最短距离：", start);    for (i, &d) in distances.iter().enumerate() {        if d == u32::MAX {            println!("  节点 {}: 不可达", i);        } else {            println!("  节点 {}: {}", i, d);        }    }}

代码解析

• State 结构体保存当前路径代价和位置。
• 通过重写 Ord 和 PartialOrd，让 BinaryHeap 按照 最小代价 弹出元素。
• dijkstra 函数初始化距离数组为无穷大（u32::MAX），起点距离为 0。
• 每次从堆中取出当前代价最小的节点，更新其邻居的距离。

运行程序

在项目根目录运行：

cargo run

你将看到输出：

从节点 0 到各节点的最短距离：  节点 0: 0  节点 1: 3  节点 2: 1  节点 3: 4

总结

恭喜！你已经用 Rust 成功实现了 Dijkstra 最短路径算法。这不仅加深了你对图算法的理解，也展示了 Rust 在系统编程中的强大能力——内存安全、高性能且表达清晰。

无论是学习 Rust最短路径算法、掌握 Dijkstra算法 原理，还是实践 Rust图算法 编程，这个小项目都是绝佳的 编程入门教程。继续探索吧，图的世界还有很多精彩算法等你发现！

提示：你可以尝试扩展此代码，支持记录具体路径，或处理更大的图数据。