一 最短路径问题
在图中，一个节点到其他所有节点最短的路径。
二 Dijkstra算法
2.1 算法目标
使用 Dijkstra 算法，可以寻找图中节点之间的最短路径。特别是，可以在图中寻找一个节点（称为“源节点”）到所有其它节点的最短路径，生成一个最短路径树。
2.2 算法基本流程
- Dijkstra 算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径。
- Dijkstra 算法会记录当前已知的最短路径，并在寻找到更短的路径时更新。
- 一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为“已访问”并添加到路径中。
- 重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案。
Dijkstra 只能用在权重为正的图中，因为计算过程中需要将边的权重相加来寻找最短路径。
2.3 核心框架
函数签名：
// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离 int[] dijkstra(int start, List<Integer>[] graph);
定义结构：
class State { // 图节点的 id int id; // 从 start 节点到当前节点的距离 int distFromStart; State(int id, int distFromStart) { this.id = id; this.distFromStart = distFromStart; } }
核心框架：
Dijkstra 可以理解成一个带 dp table（或者说备忘录）的 BFS 算法，伪码如下：
// 返回节点 from 到节点 to 之间的边的权重 int weight(int from, int to); // 输入节点 s 返回 s 的相邻节点 List<Integer> adj(int s); // 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离 int[] dijkstra(int start, List<Integer>[] graph) { // 图中节点的个数 int V = graph.length; // 记录最短路径的权重，你可以理解为 dp table // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重 int[] distTo = new int[V]; // 求最小值，所以 dp table 初始化为正无穷 Arrays.fill(distTo, Integer.MAX_VALUE); // base case，start 到 start 的最短距离就是 0 distTo[start] = 0; // 优先级队列，distFromStart 较小的排在前面 Queue<State> pq = new PriorityQueue<>((a, b) -> { return a.distFromStart - b.distFromStart; }); // 从起点 start 开始进行 BFS pq.offer(new State(start, 0)); while (!pq.isEmpty()) { State curState = pq.poll(); int curNodeID = curState.id; int curDistFromStart = curState.distFromStart; if (curDistFromStart > distTo[curNodeID]) { // 已经有一条更短的路径到达 curNode 节点了 continue; } // 将 curNode 的相邻节点装入队列 for (int nextNodeID : adj(curNodeID)) { // 看看从 curNode 达到 nextNode 的距离是否会更短 int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID); if (distTo[nextNodeID] > distToNextNode) { // 更新 dp table distTo[nextNodeID] = distToNextNode; // 将这个节点以及距离放入队列 pq.offer(new State(nextNodeID, distToNextNode)); } } } return distTo; }
2.4 从二叉树到Dijkstra（推导过程）
1. 二叉树的层级遍历框架：
// 输入一棵二叉树的根节点，层序遍历这棵二叉树 void levelTraverse(TreeNode root) { if (root == null) return 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int depth = 1; // 从上到下遍历二叉树的每一层 while (!q.isEmpty()) { int sz = q.size(); // 从左到右遍历每一层的每个节点 for (int i = 0; i < sz; i++) { TreeNode cur = q.poll(); printf("节点 %s 在第 %s 层", cur, depth); // 将下一层节点放入队列 if (cur.left != null) { q.offer(cur.left); } if (cur.right != null) { q.offer(cur.right); } } depth++; } }
while 循环控制一层一层往下走，for 循环利用 sz 变量控制从左到右遍历每一层二叉树节点。2. 多叉树的层序遍历
基于二叉树遍历，我们可以得到多叉树的层序遍历
// 输入一棵多叉树的根节点，层序遍历这棵多叉树 void levelTraverse(TreeNode root) { if (root == null) return; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int depth = 1; // 从上到下遍历多叉树的每一层 while (!q.isEmpty()) { int sz = q.size(); // 从左到右遍历每一层的每个节点 for (int i = 0; i < sz; i++) { TreeNode cur = q.poll(); printf("节点 %s 在第 %s 层", cur, depth); // 将下一层节点放入队列 for (TreeNode child : cur.children) { q.offer(child); } } depth++; } }
3. BFS框架（权重均为1 的最短路径）
也就可以得到BFS框架
本质就是让你在一幅「图」中找到从起点
start 到终点 target 的最近距离BFS默认所有节点之间的边，权重均为1.
// 输入起点，进行 BFS 搜索 int BFS(Node start) { Queue<Node> q; // 核心数据结构 Set<Node> visited; // 避免走回头路 q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录搜索的步数 while (q not empty) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散一步 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); printf("从 %s 到 %s 的最短距离是 %s", start, cur, step); /* 将 cur 的相邻节点加入队列 */ for (Node x : cur.adj()) { if (x not in visited) { q.offer(x); visited.add(x); } } } step++; } }
BFS 的核心数据结构；
cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited4. 从BFS到Dijkstra
因为Dijkstra用来计算有权重的最短路径，所以和BFS不同，BFS只需要记录depth就是可以（可以看成权重均为1），而Dijkstra需要记录两点之间的最短权重。
而BFS中的while下的for循环是用来记录层级结构（depth），在Dijkstra中不再使用depth的话，就可以去除for循环。
可以转变为以下结构。
class State { // 记录 node 节点的深度 int depth; TreeNode node; State(TreeNode node, int depth) { this.depth = depth; this.node = node; } } // 输入一棵二叉树的根节点，遍历这棵二叉树所有节点 void levelTraverse(TreeNode root) { if (root == null) return 0; Queue<State> q = new LinkedList<>(); q.offer(new State(root, 1)); // 遍历二叉树的每一个节点 while (!q.isEmpty()) { State cur = q.poll(); TreeNode cur_node = cur.node; int cur_depth = cur.depth; printf("节点 %s 在第 %s 层", cur_node, cur_depth); // 将子节点放入队列 if (cur_node.left != null) { q.offer(new State(cur_node.left, cur_depth + 1)); } if (cur_node.right != null) { q.offer(new State(cur_node.right, cur_depth + 1)); } } }