用Rust实现Floyd算法（从零开始掌握图中最短路径的多源求解）

什么是Floyd算法？

Floyd算法由Robert W. Floyd于1962年提出，它能高效地计算出图中任意两个顶点之间的最短距离（如果存在路径）。与Dijkstra算法不同，Floyd适用于带负权边的图（但不能有负权环），且能一次性求出所有点对的最短路径。

该算法的时间复杂度为 O(n³)，空间复杂度为 O(n²)，其中 n 是图中顶点的数量。虽然复杂度较高，但对于中小规模图或需要频繁查询任意两点最短路径的场景非常实用。

准备工作：Rust环境配置

确保你已安装Rust。若未安装，可访问 Rust官网 下载并安装。

创建新项目：

cargo new floyd_rustcd floyd_rust

Floyd算法核心思想

Floyd算法基于动态规划。设 dist[i][j] 表示从顶点 i 到 j 的最短距离。初始时，dist 矩阵就是图的邻接矩阵（无直接边则设为无穷大）。

算法通过三重循环，依次尝试以每个顶点 k 作为中间点，看是否能缩短 i 到 j 的路径：

for k in 0..n {    for i in 0..n {        for j in 0..n {            if dist[i][k] + dist[k][j] < dist[i][j] {                dist[i][j] = dist[i][k] + dist[k][j];            }        }    }}

Rust代码实现

下面我们将用Rust完整实现Floyd算法。为了处理“无穷大”，我们使用 i32::MAX / 2（避免加法溢出）。

fn floyd_warshall(graph: &mut Vec<Vec<i32>>) {    let n = graph.len();    // 三重循环：k 为中间节点    for k in 0..n {        for i in 0..n {            for j in 0..n {                // 避免溢出：只在两边都不是无穷大时更新                if graph[i][k] != i32::MAX / 2 && graph[k][j] != i32::MAX / 2 {                    let new_dist = graph[i][k] + graph[k][j];                    if new_dist < graph[i][j] {                        graph[i][j] = new_dist;                    }                }            }        }    }}fn main() {    // 示例图：4个节点    // 使用 i32::MAX / 2 表示无穷大（无路径）    let mut dist = vec![        vec![0, 3, i32::MAX / 2, 7],        vec![8, 0, 2, i32::MAX / 2],        vec![5, i32::MAX / 2, 0, 1],        vec![2, i32::MAX / 2, i32::MAX / 2, 0],    ];    println!("原始距离矩阵:");    print_matrix(&dist);    floyd_warshall(&mut dist);    println!("\nFloyd算法执行后的最短路径矩阵:");    print_matrix(&dist);}// 辅助函数：打印矩阵（将极大值显示为 "∞"）fn print_matrix(matrix: &Vec<Vec<i32>>) {    for row in matrix {        for &val in row {            if val == i32::MAX / 2 {                print!("{:>4}", "∞");            } else {                print!("{:>4}", val);            }        }        println!();    }}

运行结果解析

运行上述代码，你将看到原始矩阵和经过Floyd算法处理后的最短路径矩阵。例如，从节点0到节点2的最短路径原本不存在（∞），但通过0→3→2（7+1=8）或0→1→2（3+2=5），最终结果为5。

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

Rust以其内存安全、零成本抽象和高性能著称。在实现如Rust Floyd算法这类对性能敏感的图算法时，Rust既能提供接近C/C++的速度，又能避免空指针、缓冲区溢出等常见错误。

此外，Rust的类型系统和所有权模型使得代码更健壮，特别适合构建可靠的基础算法库。

总结

通过本教程，你已经掌握了如何用Rust实现Floyd-Warshall算法，理解了其动态规划思想，并能处理带权有向图中的多源最短路径问题。无论你是学习最短路径算法，还是探索Rust图算法的实际应用，这都是一个坚实的基础。

建议你尝试修改图结构、添加负权边（但不要构成负环），观察算法行为。进一步地，你可以将此算法封装为库，供其他项目调用。

关键词回顾：Rust Floyd算法、最短路径算法、Rust图算法、Floyd-Warshall实现