面试题：Rust泛型与trait bounds的复杂应用

Question

假设有一个 `Graph` 结构体，它是泛型的，节点类型为 `Node`，边的权重类型为 `Weight`。定义一个泛型方法 `shortest_path`，用于计算图中两个节点之间的最短路径。`Node` 类型需要实现 `Eq` 和 `Hash` trait，以便在图的内部数据结构中使用。`Weight` 类型需要实现 `std::cmp::Ord` 和 `std::ops::Add` trait 。请给出完整的 `Graph` 结构体定义、必要的 `use` 语句以及 `shortest_path` 方法的实现框架（不需要完整的最短路径算法实现，但要体现泛型和trait bounds的正确使用）。

Answer 1

use std::collections::HashMap;

// Graph结构体定义
struct Graph<Node, Weight>
where
    Node: Eq + Hash,
    Weight: std::cmp::Ord + std::ops::Add<Output = Weight>,
{
    nodes: HashMap<Node, HashMap<Node, Weight>>,
}

impl<Node, Weight> Graph<Node, Weight>
where
    Node: Eq + Hash,
    Weight: std::cmp::Ord + std::ops::Add<Output = Weight>,
{
    // shortest_path方法实现框架
    fn shortest_path(&self, start: &Node, end: &Node) -> Option<(Weight, Vec<Node>)> {
        // 这里不需要完整的最短路径算法实现，但可以预留思路，比如使用Dijkstra算法等
        // 例如初始化距离哈希表，队列等操作
        let mut distances: HashMap<&Node, Weight> = HashMap::new();
        let mut previous: HashMap<&Node, &Node> = HashMap::new();
        let mut queue: Vec<&Node> = Vec::new();

        // 初始化距离为无穷大，除了起点
        for node in self.nodes.keys() {
            if node == start {
                distances.insert(node, Weight::default());
            } else {
                distances.insert(node, Weight::max_value());
            }
            queue.push(node);
        }

        while let Some(current) = queue.pop() {
            // 检查邻居节点
            for (neighbor, weight) in self.nodes.get(current).unwrap() {
                let alt = distances.get(current).unwrap() + weight;
                if alt < *distances.get(neighbor).unwrap() {
                    distances.insert(neighbor, alt);
                    previous.insert(neighbor, current);
                }
            }
        }

        // 构建路径
        if let Some(_) = distances.get(end) {
            let mut path = Vec::new();
            let mut at = end;
            while at != start {
                path.push(*at);
                at = previous.get(at).unwrap();
            }
            path.push(*start);
            path.reverse();
            return Some((distances.get(end).unwrap().clone(), path));
        }

        None
    }
}