Dijkstra 算法模板及应用
原创约 4216 字
一句话总结
Dijkstra 算法是一种用于计算图中单源最短路径的算法，本质上是一个经过特殊改造的 BFS 算法，改造点有两个：
1、使用 优先级队列，而不是普通队列进行 BFS 算法。
2、添加了一个备忘录，记录起点到每个可达节点的最短路径权重和。
学习 Dijkstra 最短路径算法之前，你需要先了解 图结构基础及通用代码实现，下面的讲解中，我会用到图结构 Graph 的通用 API。
另外，你必须要理解 二叉树的 DFS/BFS 遍历 以及 图结构的 DFS/BFS 遍历 中 BFS 遍历的基本原理，因为 Dijkstra 算法本质上就是一个经过特殊改造的 BFS 算法。
在讲解二叉树和图结构的 BFS 遍历算法时，我同时给出了三种 BFS 算法的写法，如果忘了可以回去复习一下。
其中第三种 BFS 算法相对复杂一些，但是最灵活，因为它新建了一个 State 类，允许每个节点独立维护一些额外信息。
具体代码如下：
java 🟢
// 多叉树的层序遍历
// 每个节点自行维护 State 类，记录深度等信息
class State {
Node node;
int depth;
public State(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
void levelOrderTraverse(Node root) {
if (root == null) {
return;
}
Queue<State> q = new LinkedList<>();
// 记录当前遍历到的层数（根节点视为第 1 层）
q.offer(new State(root, 1));
while (!q.isEmpty()) {
State state = q.poll();
Node cur = state.node;
int depth = state.depth;
// 访问 cur 节点，同时知道它所在的层数
System.out.println("depth = " + depth + ", val = " + cur.val);
for (Node child : cur.children) {
q.offer(new State(child, depth + 1));
}
}
}
// 图结构的 BFS 遍历，从节点 s 开始进行 BFS，且记录路径的权重和
// 每个节点自行维护 State 类，记录从 s 走来的权重和
class State {
// 当前节点 ID
int node;
// 从起点 s 到当前节点的权重和
int weight;
public State(int node, int weight) {
this.node = node;
this.weight = weight;
}
}
void bfs(Graph graph, int s) {
boolean[] visited = new boolean[graph.size()];
Queue<State> q = new LinkedList<>();
q.offer(new State(s, 0));
visited[s] = true;
while (!q.isEmpty()) {
State state = q.poll();
int cur = state.node;
int weight = state.weight;
System.out.println("visit " + cur + " with path weight " + weight);
for (Edge e : graph.neighbors(cur)) {
if (!visited[e.to]) {
q.offer(new State(e.to, weight + e.weight));
visited[e.to] = true;
}
}
}
}cpp 🤖
// 多叉树的层序遍历
// 每个节点自行维护 State 类，记录深度等信息
class State {
public:
Node* node;
int depth;
State(Node* node, int depth) : node(node), depth(depth) {}
};
void levelOrderTraverse(Node* root) {
if (root == nullptr) {
return;
}
queue<State> q;
// 记录当前遍历到的层数（根节点视为第 1 层）
q.push(State(root, 1));
while (!q.empty()) {
State state = q.front();
q.pop();
Node* cur = state.node;
int depth = state.depth;
// 访问 cur 节点，同时知道它所在的层数
cout << "depth = " << depth << ", val = " << cur->val << endl;
for (Node* child : cur->children) {
q.push(State(child, depth + 1));
}
}
}
// 图结构的 BFS 遍历，从节点 s 开始进行 BFS，且记录路径的权重和
// 每个节点自行维护 State 类，记录从 s 走来的权重和
class State {
public:
// 当前节点 ID
int node;
// 从起点 s 到当前节点的权重和
int weight;
State(int node, int weight) : node(node), weight(weight) {}
};
void bfs(const Graph& graph, int s) {
vector<bool> visited(graph.size(), false);
queue<State> q;
q.push(State(s, 0));
visited[s] = true;
while (!q.empty()) {
State state = q.front();
q.pop();
int cur = state.node;
int weight = state.weight;
cout << "visit " << cur << " with path weight " << weight << endl;
for (const Edge& e : graph.neighbors(cur)) {
if (!visited[e.to]) {
q.push(State(e.to, weight + e.weight));
visited[e.to] = true;
}
}
}
}python 🤖
# 多叉树的层序遍历
# 每个节点自行维护 State 类，记录深度等信息
class State:
def __init__(self, node, depth):
self.node = node
self.depth = depth
def levelOrderTraverse(root):
if root is None:
return
from collections import deque
q = deque([State(root, 1)])
while q:
state = q.popleft()
cur = state.node
depth = state.depth
# 访问 cur 节点，同时知道它所在的层数
print(f"depth = {depth}, val = {cur.val}")
for child in cur.children:
q.append(State(child, depth + 1))
# 图结构的 BFS 遍历，从节点 s 开始进行 BFS，且记录路径的权重和
# 每个节点自行维护 State 类，记录从 s 走来的权重和
class State:
def __init__(self, node, weight):
# 当前节点 ID
self.node = node
# 从起点 s 到当前节点的权重和
self.weight = weight
def bfs(graph, s):
visited = [False] * len(graph)
from collections import deque
q = deque([State(s, 0)])
visited[s] = True
while q:
state = q.popleft()
cur = state.node
weight = state.weight
print(f"visit {cur} with path weight {weight}")
for e in graph.neighbors(cur):
if not visited[e.to]:
q.append(State(e.to, weight + e.weight))
visited[e.to] = Truego 🤖
// 多叉树的层序遍历
// 每个节点自行维护 State 类，记录深度等信息
type State struct {
node *Node
depth int
}
func levelOrderTraverse(root *Node) {
if root == nil {
return
}
q := []*State{{root, 1}}
for len(q) > 0 {
state := q[0]
q = q[1:]
cur := state.node
depth := state.depth
// 访问 cur 节点，同时知道它所在的层数
fmt.Printf("depth = %d, val = %d\n", depth, cur.val)
for _, child := range cur.children {
q = append(q, &State{child, depth + 1})
}
}
}
// 图结构的 BFS 遍历，从节点 s 开始进行 BFS，且记录路径的权重和
// 每个节点自行维护 State 类，记录从 s 走来的权重和
type State struct {
// 当前节点 ID
node int
// 从起点 s 到当前节点的权重和
weight int
}
func bfs(graph Graph, s int) {
visited := make([]bool, graph.size())
q := []*State{{s, 0}}
visited[s] = true
for len(q) > 0 {
state := q[0]
q = q[1:]
cur := state.node
weight := state.weight
fmt.Printf("visit %d with path weight %d\n", cur, weight)
for _, e := range graph.neighbors(cur) {
if !visited[e.to] {
q = append(q, &State{e.to, weight + e.weight})
visited[e.to] = true
}
}
}
}javascript 🤖
// 多叉树的层序遍历
// 每个节点自行维护 State 类，记录深度等信息
class State {
constructor(node, depth) {
this.node = node;
this.depth = depth;
}
}
var levelOrderTraverse = function(root) {
if (root === null) {
return;
}
var q = [new State(root, 1)];
while (q.length !== 0) {
var state = q.shift();
var cur = state.node;
var depth = state.depth;
// 访问 cur 节点，同时知道它所在的层数
console.log("depth = " + depth + ", val = " + cur.val);
for (var i = 0; i < cur.children.length; i++) {
var child = cur.children[i];
q.push(new State(child, depth + 1));
}
}
}
// 图结构的 BFS 遍历，从节点 s 开始进行 BFS，且记录路径的权重和
// 每个节点自行维护 State 类，记录从 s 走来的权重和
class State {
constructor(node, weight) {
// 当前节点 ID
this.node = node;
// 从起点 s 到当前节点的权重和
this.weight = weight;
}
}
var bfs = function(graph, s) {
var visited = new Array(graph.size()).fill(false);
var q = [new State(s, 0)];
visited[s] = true;
while (q.length !== 0) {
var state = q.shift();
var cur = state.node;
var weight = state.weight;
console.log("visit " + cur + " with path weight " + weight);
var neighbors = graph.neighbors(cur);
for (var i = 0; i < neighbors.length; i++) {
var e = neighbors[i];
if (!visited[e.to]) {
q.push(new State(e.to, weight + e.weight));
visited[e.to] = true;
}
}
}
}这种写法对于树结构来说有些多此一举，但是对于加权图来说，就非常有用了。
我们即将实现的 Dijkstra 算法就是基于这个算法的改进，每个节点都需要记录从起点到自己的最短路径权重和，再结合 优先级队列 这种能够动态排序的数据结构，就可以高效地计算出最短路径了。
下面来具体介绍 Dijkstra 算法的通用代码实现。