Dijkstra

Dijkstra算法是一种图遍历算法,用于找到源顶点到图中所有其他顶点的最短路径。 数据结构 顶点(Vertex): 一个保存顶点id的结构体。 边(Edge): 一个保存起点和终点顶点id的结构体,以及边的权重(代价),必须是正整数。 图(Graph): 一个保存所有顶点和边的结构体。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 use std::cmp::Ordering; #[derive(Debug, PartialEq, Eq, Clone, Hash)] pub struct Vertex { // `id`: 顶点的唯一标识符,用字符串表示。 id: String, } #[derive(Debug, PartialEq, Eq, Clone)] pub struct Edge { // `from`: 边的起点顶点id。 from: String, // `to`: 边的终点顶点id。 to: String, // `cost`: 遍历该边的权重或代价。 cost: u32, } #[derive(Debug, PartialEq, Eq)] pub struct Graph { // `vertices`: 一个包含所有顶点的`Vertex`结构体向量。 vertices: Vec<Vertex>, // `edges`: 一个包含所有边的`Edge`结构体向量。 edges: Vec<Edge>, } #[derive(Clone, Eq, PartialEq)] struct Node { // `cost`: 从源顶点到该顶点的当前最短距离。 cost: u32, // `vertex_id`: 该节点所代表顶点的id。 vertex_id: String, } // 为`Node`实现`Ord`特性,使其可用于`BinaryHeap`。 impl Ord for Node { fn cmp(&self, other: &Self) -> Ordering { // 反转`cost`的排序,使`BinaryHeap`表现为最小堆。 // Rust中的`BinaryHeap`默认是最大堆,反转比较结果会使其成为最小堆。 other.cost.cmp(&self.cost) } } // 为`Node`实现`PartialOrd`特性。 impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } Dijkstra算法 最低代价 将源顶点到自身的距离初始化为0。 将源顶点及代价0推入优先队列。 循环直到优先队列为空。 从优先队列中弹出距离最小的顶点。 如果当前顶点是目标顶点,则跳出循环。 如果已经找到了更短的路径到达当前顶点,则跳过。 遍历所有以当前顶点为起点的边。 计算通过当前顶点到达邻居顶点的代价。 如果找到了更短的路径到达邻居顶点,则更新距离,并将其推入优先队列。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 use std::collections::{BinaryHeap, HashMap}; impl Graph { // 使用Dijkstra算法计算从src到dest的最低代价。 pub fn dijkstra_cost(&self, src: &str, dest: &str) -> Option<u32> { // `distances`: 一个`HashMap`用于存储从源顶点到每个顶点的最短距离。 let mut distances: HashMap<String, u32> = HashMap::new(); // `pq`: 一个`BinaryHeap`(优先队列)用于高效选择距离最小的顶点。 let mut pq: BinaryHeap<Node> = BinaryHeap::new(); // 将源顶点到自身的距离初始化为0。 distances.insert(src.to_string(), 0); // 将源顶点及代价0推入优先队列。 pq.push(Node { cost: 0, vertex_id: src.to_string(), }); // 循环直到优先队列为空。 while let Some(Node { cost, vertex_id }) = pq.pop() { // 如果当前顶点是目标顶点,则返回代价。 if vertex_id == dest { return Some(cost); } // 如果已经找到了更短的路径到达当前顶点,则跳过。 if cost > *distances.get(&vertex_id).unwrap_or(&u32::MAX) { continue; } // 遍历所有以当前顶点为起点的边。 for edge in self.edges.iter().filter(|e| e.from == vertex_id) { // 计算通过当前顶点到达邻居顶点的代价。 let next_cost = cost + edge.cost; // 如果找到了更短的路径到达邻居顶点,则更新距离,并将其推入优先队列。 if next_cost < *distances.get(&edge.to).unwrap_or(&u32::MAX) { distances.insert(edge.to.clone(), next_cost); pq.push(Node { cost: next_cost, vertex_id: edge.to.clone(), }); } } } // 如果没有找到路径,则返回None。 None } } 最短路径 与最低代价的算法大致相同,但需要保存一个previous的HashMap来存储到达每个顶点的最短路径上的前一个顶点。 ...

Dijkstra’s algorithm is a graph traversal algorithm that finds the shortest path between the source vertex and all other vertices in the graph. data structure Vertex: a struct that holds the vertex id. Edge: a struct that holds the vertex id of the start and end points, and the cost of the edge which must be a positive integer. Graph: a struct that holds the vertices and edges. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 use std::cmp::Ordering; #[derive(Debug, PartialEq, Eq, Clone, Hash)] pub struct Vertex { // `id`: A unique identifier for the vertex, represented as a String. id: String, } #[derive(Debug, PartialEq, Eq, Clone)] pub struct Edge { // `from`: The ID of the starting vertex of the edge. from: String, // `to`: The ID of the ending vertex of the edge. to: String, // `cost`: The weight or cost associated with traversing the edge. cost: u32, } #[derive(Debug, PartialEq, Eq)] pub struct Graph { // `vertices`: A vector of `Vertex` structs, representing all vertices in the graph. vertices: Vec<Vertex>, // `edges`: A vector of `Edge` structs, representing all edges in the graph. edges: Vec<Edge>, } #[derive(Clone, Eq, PartialEq)] struct Node { // `cost`: The current shortest distance from the source vertex to this vertex. cost: u32, // `vertex_id`: The ID of the vertex represented by this node. vertex_id: String, } // Implement `Ord` trait for `Node` to make it usable in `BinaryHeap`. impl Ord for Node { fn cmp(&self, other: &Self) -> Ordering { // Reverse the ordering of `cost` to make `BinaryHeap` behave as a min-heap. // `BinaryHeap` in Rust is a max-heap by default, so flipping the comparison results // in a min-heap behavior. other.cost.cmp(&self.cost) } } // Implement `PartialOrd` trait for `Node`. impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } Dijkstra algorithm lowest cost Initialize the distance from the source vertex to itself as 0. Push the source vertex into the priority queue with cost 0. Loop until the priority queue is empty. Pop the vertex with the smallest distance from the priority queue. If the current vertex is the destination, break the loop. If a shorter path to the current vertex has already been found, skip it. Iterate over all edges starting from the current vertex. Calculate the cost to the neighbor vertex through the current vertex. If a shorter path to the neighbor vertex is found, update the distance, and push it into the priority queue. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 use std::collections::{BinaryHeap, HashMap}; impl Graph { // Computes the lowest cost from src to dest using Dijkstra's algorithm. pub fn dijkstra_cost(&self, src: &str, dest: &str) -> Option<u32> { // `distances`: A `HashMap` to store the shortest distances from the source vertex to each vertex. let mut distances: HashMap<String, u32> = HashMap::new(); // `pq`: A `BinaryHeap` (priority queue) to efficiently select the vertex with the smallest distance. let mut pq: BinaryHeap<Node> = BinaryHeap::new(); // Initialize the distance from the source vertex to itself as 0. distances.insert(src.to_string(), 0); // Push the source vertex into the priority queue with cost 0. pq.push(Node { cost: 0, vertex_id: src.to_string(), }); // Loop until the priority queue is empty. while let Some(Node { cost, vertex_id }) = pq.pop() { // If the current vertex is the destination, return the cost. if vertex_id == dest { return Some(cost); } // If a shorter path to the current vertex has already been found, skip it. if cost > *distances.get(&vertex_id).unwrap_or(&u32::MAX) { continue; } // Iterate over all edges starting from the current vertex. for edge in self.edges.iter().filter(|e| e.from == vertex_id) { // Calculate the cost to the neighbor vertex through the current vertex. let next_cost = cost + edge.cost; // If a shorter path to the neighbor vertex is found, update the distance and push it into the priority queue. if next_cost < *distances.get(&edge.to).unwrap_or(&u32::MAX) { distances.insert(edge.to.clone(), next_cost); pq.push(Node { cost: next_cost, vertex_id: edge.to.clone(), }); } } } // If no path is found, return None. None } } shortest path Much the same as the lowest cost, but keep a previous HashMap to store the previous vertex in the shortest path to each vertex. ...