掌握Rust最短路径算法（从零开始实现Dijkstra算法的完整指南）

准备工作：Rust环境与依赖

首先，请确保你已安装Rust（推荐使用rustup）。我们还需要使用优先队列（最小堆）来高效获取当前距离最小的节点。Rust标准库不包含优先队列，因此我们将使用binary-heap-plus或直接利用std::collections::BinaryHeap并自定义比较逻辑。

在Cargo.toml中添加以下依赖（如果需要更简洁的优先队列，可选）：

# 通常我们只用标准库即可，但需注意BinaryHeap是最大堆# 因此我们要对距离取反或自定义Ord

步骤一：定义图的数据结构

我们用邻接表表示图。每个节点对应一个列表，存储其邻居及边的权重。

use std::collections::HashMap;// 图的邻接表表示：节点 -> [(邻居, 权重)]type Graph = HashMap>;

步骤二：实现Dijkstra算法

核心思想：维护一个距离数组dist，记录起点到各点的最短距离；使用优先队列按距离从小到大处理节点。

use std::collections::{BinaryHeap, HashMap};use std::cmp::Ordering;#[derive(Copy, Clone, Eq, PartialEq)]struct State {    cost: u32,    position: usize,}// BinaryHeap是最大堆，所以我们要反转比较逻辑impl Ord for State {    fn cmp(&self, other: &Self) -> Ordering {        other.cost.cmp(&self.cost)    }}impl PartialOrd for State {    fn partial_cmp(&self, other: &Self) -> Option {        Some(self.cmp(other))    }}fn dijkstra(graph: &Graph, start: usize) -> HashMap {    let mut dist: HashMap = HashMap::new();    let mut heap = BinaryHeap::new();    // 初始化起点    dist.insert(start, 0);    heap.push(State { cost: 0, position: start });    while let Some(State { cost, position }) = heap.pop() {        // 如果当前cost大于已记录的最短距离，跳过        if cost > *dist.get(&position).unwrap_or(&u32::MAX) {            continue;        }        // 遍历邻居        if let Some(neighbors) = graph.get(&position) {            for &(next, weight) in neighbors {                let next_cost = cost + weight;                // 如果找到更短路径，更新并加入堆                if next_cost < *dist.get(&next).unwrap_or(&u32::MAX) {                    dist.insert(next, next_cost);                    heap.push(State { cost: next_cost, position: next });                }            }        }    }    dist}

步骤三：测试你的算法

让我们构建一个简单图并运行算法：

fn main() {    let mut graph: Graph = HashMap::new();        // 构建图：0 -> 1 (权重2), 0 -> 2 (权重5)    //         1 -> 2 (权重1), 1 -> 3 (权重4)    //         2 -> 3 (权重1)    graph.insert(0, vec![(1, 2), (2, 5)]);    graph.insert(1, vec![(2, 1), (3, 4)]);    graph.insert(2, vec![(3, 1)]);    graph.insert(3, vec![]);    let distances = dijkstra(&graph, 0);    println!("从节点0出发的最短距离: {:?}", distances);    // 输出: {0: 0, 1: 2, 2: 3, 3: 4}}

为什么选择Rust实现图算法？

Rust以其内存安全、零成本抽象和高性能著称，非常适合实现如Rust编程教程中强调的系统级算法。通过所有权和借用机制，Rust在编译期就能避免空指针、数据竞争等常见错误，让你专注于算法逻辑而非内存管理。

总结

恭喜！你已经成功用Rust实现了Dijkstra最短路径算法。通过本教程，你不仅掌握了Rust最短路径算法的核心思想，还学会了如何在Rust中处理图数据结构和优先队列。下一步可以尝试实现A*算法或处理负权边的Bellman-Ford算法，进一步提升你的Rust图算法技能！

关键词回顾：Rust最短路径算法、Dijkstra算法、Rust图算法、Rust编程教程