用Rust实现Dijkstra算法（从零开始掌握最短路径算法）

准备工作：Rust环境与依赖

首先，确保你已安装Rust。如果还没安装，可以访问 rust-lang.org 下载并安装。

我们将使用标准库中的 BinaryHeap（二叉堆）作为优先队列，并用 HashMap 存储图结构。无需额外依赖！

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

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

use std::collections::{HashMap, BinaryHeap};use std::cmp::Reverse;// 图结构：节点名 -> [(邻居, 权重)]type Graph = HashMap<String, Vec<(String, u32)>>;

步骤二：实现Dijkstra算法

算法流程如下：

1. 初始化：起点距离为0，其他为无穷大（用u32::MAX表示）
2. 将起点加入优先队列（最小堆）
3. 循环：取出当前距离最小的未处理节点
4. 用该节点更新其邻居的距离
5. 重复直到队列为空

fn dijkstra(graph: &Graph, start: &str) -> HashMap<String, u32> {    let mut distances: HashMap<String, u32> = HashMap::new();    let mut heap = BinaryHeap::new();    // 初始化所有节点距离为无穷大    for node in graph.keys() {        distances.insert(node.clone(), u32::MAX);    }    // 起点距离为0    distances.insert(start.to_string(), 0);    heap.push(Reverse((0, start.to_string())));    while let Some(Reverse((current_dist, current_node))) = heap.pop() {        // 如果当前距离大于已记录的最短距离，跳过        if current_dist > distances[&current_node] {            continue;        }        // 遍历邻居        if let Some(neighbors) = graph.get(&current_node) {            for (neighbor, weight) in neighbors {                let new_dist = current_dist + weight;                // 如果找到更短路径，更新                if new_dist < distances[neighbor] {                    distances.insert(neighbor.clone(), new_dist);                    heap.push(Reverse((new_dist, neighbor.clone())));                }            }        }    }    distances}

步骤三：测试我们的实现

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

fn main() {    let mut graph: Graph = HashMap::new();    // 构建图：A -> B(1), A -> C(4)    //         B -> C(2), B -> D(5)    //         C -> D(1)    graph.insert("A".to_string(), vec![("B".to_string(), 1), ("C".to_string(), 4)]);    graph.insert("B".to_string(), vec![("C".to_string(), 2), ("D".to_string(), 5)]);    graph.insert("C".to_string(), vec![("D".to_string(), 1)]);    graph.insert("D".to_string(), vec![]);    let distances = dijkstra(&graph, "A");    println!("从A出发的最短距离：");    for (node, dist) in &distances {        if *dist == u32::MAX {            println!("{}: 不可达", node);        } else {            println!("{}: {}", node, dist);        }    }}

运行结果应为：

A: 0B: 1C: 3D: 4

为什么选择Rust实现Dijkstra？

Rust以其内存安全、零成本抽象和高性能著称。在实现如最短路径算法这类对性能敏感的算法时，Rust能提供接近C++的速度，同时避免空指针、数据竞争等常见错误。

总结

通过本教程，你已经学会了如何用Rust实现Dijkstra算法。这不仅是一个经典的Rust图算法案例，也是理解贪心策略和优先队列应用的好例子。

记住：Dijkstra算法要求图中不能有负权边。如果存在负权边，请考虑使用Bellman-Ford算法。

希望这篇Dijkstra实现教程对你有帮助！动手试试修改图结构，看看结果如何变化吧。