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来存储到达每个顶点的最短路径上的前一个顶点。
当找到到达邻居顶点的更短路径时,更新距离和前一个顶点,并将其推入优先队列。
当到达目标顶点时,使用previous映射反向重构路径。
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| impl Graph {
// 使用Dijkstra算法计算从src到dest的最短路径,并返回一个顶点向量作为路径。
pub fn dijkstra_path(&self, src: &str, dest: &str) -> Option<Vec<&Vertex>> {
// `distances`: 一个`HashMap`用于存储从源顶点到每个顶点的最短距离。
let mut distances: HashMap<String, u32> = HashMap::new();
// `previous`: 一个`HashMap`用于存储到达每个顶点的最短路径上的前一个顶点。
let mut previous: HashMap<String, String> = 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 {
break;
}
// 如果已经找到了更短的路径到达当前顶点,则跳过。
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);
previous.insert(edge.to.clone(), vertex_id.clone());
pq.push(Node {
cost: next_cost,
vertex_id: edge.to.clone(),
});
}
}
}
// 使用previous映射构造从src到dest的路径。
self.construct_path(&previous, src, dest)
}
// 使用previous映射构造从src到dest的路径。
fn construct_path(
&self,
previous: &HashMap<String, String>,
src: &str,
dest: &str,
) -> Option<Vec<&Vertex>> {
// `path`: 一个存储最短路径上顶点的向量。
let mut path = Vec::new();
// `current`: 当前正在处理的顶点,初始化为目标顶点。
let mut current = dest;
// 循环直到当前顶点是源顶点。
while current != src {
// 在图中通过id查找顶点。
if let Some(vertex) = self.vertices.iter().find(|v| v.id == current) {
// 将顶点添加到路径中。
path.push(vertex);
} else {
// 如果找不到顶点,则返回None。
return None;
}
// 从previous映射中获取前一个顶点。
if let Some(prev) = previous.get(current) {
// 移动到前一个顶点。
current = prev;
} else {
// 如果找不到前一个顶点,则返回None。
return None;
}
}
// 将源顶点添加到路径中。
if let Some(vertex) = self.vertices.iter().find(|v| v.id == src) {
path.push(vertex);
} else {
return None;
}
// 反转以获得正确的顺序。
path.reverse();
// 返回路径。
Some(path)
}
}
|
时间复杂度和空间复杂度#
时间复杂度#
使用优先队列(二叉堆)的邻接表表示#
找到最小距离顶点:
使用二叉堆,这一步需要O(log V)的时间复杂度。
更新距离:
每次边松弛(更新距离)需要O(log V)的时间复杂度,因为需要更新堆。
在最坏情况下,我们需要松弛所有边,因此这一步的时间复杂度为O(E log V)。
总的时间复杂度: O((V + E) log V)。
在连通图中,E至少为V-1,因此可以简化为O(E log V)。
这是最常见和最高效的稀疏图实现方式。
使用斐波那契堆的邻接表表示#
找到最小距离顶点: O(log V)。
更新距离:
O(1)的均摊时间复杂度(即每次操作的平均时间是常数)。
总的时间复杂度: O(V log V + E)。
这在理论上是最快的,但斐波那契堆有较高的常数开销,在实践中使用较少。
时间复杂度的关键考虑因素#
稀疏图与密集图:
对于稀疏图(E « V^2),O(E log V)比O(V^2)要好得多。
对于密集图(E ≈ V^2),O(V^2)可能是可以接受的。
优先队列的实现:
优先队列的选择对时间复杂度有重大影响。
二叉堆是最常见的,因为它平衡了性能和实现的简单性。
空间复杂度#
Dijkstra算法的空间复杂度主要取决于存储图和距离所使用的数据结构。
邻接矩阵:
O(V^2)用于存储邻接矩阵。
O(V)用于存储距离。
总的空间复杂度: O(V^2)。
邻接表:
O(V + E)用于存储邻接表(V用于顶点,E用于边)。
O(V)用于存储距离。
O(V)用于存储路
