📚 Using Dijkstra’s Algorithm to Find the Shortest Path | 使用 Dijkstra 算法求解最短路径
Dijkstra’s algorithm is a classic graph traversal method used to find the shortest path from a single source node to every other node in a weighted graph with non-negative edge weights. In Edexcel A-Level Computer Science, it is important to understand both the mechanics of the algorithm and the way it is presented in exam answers, including distance tables, priority queues and predecessor tracking.
Dijkstra 算法是一种经典的图遍历方法，用于在具有非负边权的加权图中，找到从单一源节点到其他所有节点的最短路径。在 Edexcel A-Level 计算机科学考试中，既要理解算法的执行机制，也要掌握在答题中呈现距离表、优先队列和前驱节点跟踪的方法。
1. The Shortest Path Problem | 最短路径问题
A weighted graph consists of vertices, also called nodes, connected by edges that have an associated cost or weight. The shortest path problem asks us to find a route between two vertices such that the sum of the weights along the chosen edges is minimised.
加权图由顶点（也称为节点）和连接这些顶点的边组成，每条边都有一个相关的代价或权值。最短路径问题要求我们找到两个顶点之间的一条路线，使得所选边上权值的总和最小。
For example, in a road network the vertices could be towns and the edge weights could be driving times in minutes. The shortest path is not necessarily the path with the fewest edges; it is the path with the lowest total cost.
例如，在道路网络中，顶点可以是城镇，边权可以是驾车时间（分钟）。最短路径并不一定是经过边数最少的路径，而是总代价最低的路径。
Dijkstra’s algorithm solves the single-source shortest path problem. Starting from a given source node, it calculates the minimum distance to every other reachable node, provided all edge weights are zero or positive.
Dijkstra 算法解决的是单源最短路径问题。从给定的源节点开始，它会计算到每一个可到达节点的最小距离，前提是所有的边权都为零或正数。
2. Graph Representation for Dijkstra | Dijkstra 算法的图表示
To apply Dijkstra’s algorithm, a weighted graph can be stored using an adjacency matrix or an adjacency list. An adjacency matrix uses a 2D array where the cell value gives the weight of the edge between two vertices; a missing edge can be represented by infinity or a very large number.
要应用 Dijkstra 算法，加权图可以用邻接矩阵或邻接表来存储。邻接矩阵使用二维数组，单元格的值表示两个顶点之间边的权值；不存在的边可以用无穷大或一个非常大的数表示。
An adjacency list stores, for each vertex, a list of its direct neighbours together with the corresponding edge weights. This is often more memory-efficient for sparse graphs and is the natural representation used with a priority queue.
邻接表为每个顶点存储其直接邻居以及对应边权的列表。对于稀疏图，这种方式通常更节省内存，并且是与优先队列配合使用时的自然表示方法。
In Edexcel exam questions, graphs are usually presented visually or as a table. You are expected to read the graph, build a working-values table, and show how the algorithm updates the shortest known distances.
在 Edexcel 考试题中，图通常以图形或表格形式给出。你需要读懂图，建立工作值表，并展示算法如何更新已知的最短距离。
3. Greedy Relaxation: The Key Idea | 贪心松弛：核心思想
Dijkstra’s algorithm is a greedy algorithm. At each step it selects the unvisited vertex with the smallest current distance, marks it as visited, and then uses it to improve the distances to its neighbours. This improvement step is called relaxation.
Dijkstra 算法是一种贪心算法。每一步它选择当前距离最小的未访问顶点，将其标记为已访问，然后利用它来改善其邻居的距离。这个改善步骤称为松弛。
If vertex u has distance dist[u] and there is an edge from u to v with weight w(u, v), then the candidate distance to v through u is:
如果顶点 u 的距离为 dist[u]，且存在一条从 u 到 v 的边，权值为 w(u, v)，那么通过 u 到达 v 的候选距离为：
candidate = dist[u] + w(u, v)
If this candidate is smaller than the currently stored dist[v], we update dist[v] and record u as the predecessor of v.
如果这个候选值小于当前存储的 dist[v]，我们就更新 dist[v]，并将 u 记录为 v 的前驱节点。
if dist[u] + w(u, v) < dist[v] then dist[v] = dist[u] + w(u, v)
The key insight is that once a vertex has the smallest temporary distance among all unvisited vertices, its shortest distance is final. This is why Dijkstra’s algorithm works when all edge weights are non-negative.
关键思想是：一旦某个顶点在所有未访问顶点中具有最小的临时距离，那么它的最短距离就已经确定。这就是为什么当所有边权非负时 Dijkstra 算法是有效的。
4. The Formal Step-by-Step Procedure | 正式的分步流程
The algorithm can be described as follows. First, create a distance table with three rows: vertex, shortest distance from source, and predecessor. Initialise the source distance to zero and every other vertex to infinity.
该算法可以描述如下。首先创建一个距离表，包含三行：顶点、从源点到该顶点的最短距离、前驱节点。将源点的距离初始化为零，其他所有顶点初始化为无穷大。
- Mark the source as current, and do not mark it as visited yet.
- 将源点作为当前节点，此时尚未标记为已访问。
- For the current vertex, examine every unvisited neighbour and relax the edge if possible.
- 对于当前顶点，检查每一个未访问的邻居，并在可能的情况下进行松弛。
- After examining all neighbours, mark the current vertex as visited.
- 检查完所有邻居后，将当前顶点标记为已访问。
- Select the unvisited vertex with the smallest distance as the new current vertex.
- 选择未访问顶点中距离最小的那个作为新的当前顶点。
- Repeat until the target vertex is visited or all reachable vertices have been visited.
- 重复上述过程，直到目标顶点被访问，或者所有可到达的顶点都已访问。
It is essential to only consider unvisited neighbours when relaxing, because the shortest path to a visited vertex is already final and cannot be improved later.
必须只考虑未访问的邻居来进行松弛，因为已访问顶点的最短路径已经确定，之后不能再次改善。
5. Worked Example: A to F | 例题：从 A 到 F
Consider the following weighted graph. The edges and their weights are: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6 and E-F 3. We want to find the shortest path from A to F.
考虑以下加权图。边及其权值为：A-B 4、A-C 2、B-C 1、B-D 5、C-D 8、C-E 10、D-E 2、D-F 6 和 E-F 3。我们需要找到从 A 到 F 的最短路径。
Initialise the distance table as follows:
初始化距离表如下：
| Vertex | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Distance | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| Predecessor | – | – | – | – | – | – |
Start at A. Relax its neighbours: B becomes 4 and C becomes 2. Mark A as visited. The smallest unvisited distance is C with 2, so C becomes current.
从 A 开始。松弛其邻居：B 变为 4，C 变为 2。将 A 标记为已访问。未访问顶点中最小距离是 C，为 2，因此 C 成为当前节点。
From C, relax unvisited neighbours B, D and E. Distances are updated as follows: B = min(4, 2+1) = 3, D = min(∞, 2+8) = 10, E = min(∞, 2+10) = 12. Mark C as visited. The next node is B with distance 3.
从 C 出发，松弛未访问的邻居 B、D 和 E。距离更新如下：B = min(4, 2+1) = 3，D = min(∞, 2+8) = 10，E = min(∞, 2+10) = 12。将 C 标记为已访问。下一个节点是距离为 3 的 B。
From B, relax unvisited neighbour D: D = min(10, 3+5) = 8. Mark B as visited. The next node is D with distance 8.
从 B 出发，松弛未访问的邻居 D：D = min(10, 3+5) = 8。将 B 标记为已访问。下一个节点是距离为 8 的 D。
From D, relax unvisited neighbours E and F: E = min(12, 8+2) = 10, F = min(∞, 8+6) = 14. Mark D as visited. The next node is E with distance 10.
从 D 出发，松弛未访问的邻居 E 和 F：E = min(12, 8+2) = 10，F = min(∞, 8+6) = 14。将 D 标记为已访问。下一个节点是距离为 10 的 E。
From E, relax unvisited neighbour F: F = min(14, 10+3) = 13. Mark E as visited. Finally, F is visited with distance 13.
从 E 出发，松弛未访问的邻居 F：F = min(14, 10+3) = 13。将 E 标记为已访问。最后，F 被访问，距离为 13。
6. Distance Table and Priority Queue Trace | 距离表与优先队列跟踪
The final distance table after the algorithm terminates is shown below. It records the shortest distance from A to every vertex.
算法终止后的最终距离表如下所示。它记录了从 A 到每个顶点的最短距离。
| Vertex | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Shortest distance | 0 | 3 | 2 | 8 | 10 | 13 |
| Predecessor | – | C | A | B | D | E |
Using the predecessor row, we can reconstruct the shortest path by starting at F and working backwards: F → E → D → B → C → A. Reversing this gives A → C → B → D → E → F.
利用前驱行，我们可以从 F 开始反向重建最短路径：F → E → D → B → C → A。将其反转得到 A → C → B → D → E → F。
The priority queue trace would show the order in which vertices were extracted: A, C, B, D, E, F. This order matches the visited sequence because each time we select the unvisited vertex with the smallest known distance.
优先队列的跟踪会显示顶点的提取顺序：A、C、B、D、E、F。这个顺序与访问顺序一致，因为每次我们都选择已知距离最小的未访问顶点。
7. Pseudocode for Edexcel Exam Questions | Edexcel 考试伪代码
A standard exam-style pseudocode for Dijkstra’s algorithm is given below. It assumes a graph represented by an adjacency list and a priority queue ordered by distance.
下面给出一个标准的考试风格 Dijkstra 算法伪代码。它假设图用邻接表表示，并且有一个按距离排序的优先队列。
function dijkstra(graph, source):
dist = array of size |V| filled with infinity
pred = array of size |V| filled with null
dist[source] = 0
pq = priority queue containing all vertices keyed by dist
while pq is not empty:
u = pq.removeMin()
for each neighbour v of u:
if v is in pq:
newDist = dist[u] + weight(u, v)
if newDist < dist[v]:
dist[v] = newDist
pred[v] = u
pq.decreaseKey(v, newDist)
return dist, pred
In the pseudocode, removeMin extracts the vertex with the smallest distance. The decreaseKey operation updates the priority of a vertex after its distance has been reduced, ensuring the priority queue remains correct.
在伪代码中，removeMin 取出距离最小的顶点。decreaseKey 操作在某个顶点的距离减小后更新其在优先队列中的优先级，从而确保优先队列保持正确。
When writing pseudocode in an Edexcel exam, it is acceptable to show relaxation and selection steps more informally, as long as the greedy selection and distance update logic are clear.
在 Edexcel 考试中编写伪代码时，可以更非正式地展示松弛和选择步骤，只要贪心选择和距离更新逻辑清晰即可。
8. Time and Space Complexity | 时间复杂度与空间复杂度
The time complexity of Dijkstra’s algorithm depends on the data structures used. With an adjacency matrix and a simple linear search for the minimum, the algorithm runs in O(V²) time, where V is the number of vertices.
Dijkstra 算法的时间复杂度取决于所使用的数据结构。使用邻接矩阵和简单的线性搜索最小值时，算法的时间复杂度为 O(V²)，其中 V 是顶点数量。
With a binary heap as the priority queue and an adjacency list, the time complexity becomes O((V + E) log V), where E is the number of edges. This is better for sparse graphs where E is much smaller than V².
使用二叉堆作为优先队列和邻接表时，时间复杂度变为 O((V + E) log V)，其中 E 是边的数量。对于 E 远小于 V² 的稀疏图，这种实现更高效。
The space complexity is O(V + E) for the adjacency list representation, plus O(V) for the distance and predecessor arrays. For an adjacency matrix, the space complexity is O(V²).
邻接表表示的空间复杂度为 O(V + E)，距离和前驱数组还需要 O(V) 的空间。对于邻接矩阵，空间复杂度为 O(V²)。
In exam answers, it is useful to state both the basic and the heap-based complexity, and to explain when each implementation is preferable.
在考试答案中，最好同时说明基本实现和基于堆的实现的时间复杂度，并解释每种实现分别适用于什么情况。
9. Limitations: Negative Edge Weights | 局限性：负权边
Dijkstra’s algorithm does not produce correct results when a graph contains negative edge weights. Because the algorithm greedily finalises a vertex once it has the smallest temporary distance, a later negative edge could provide an even shorter path to that vertex.
当图中包含负权边时，Dijkstra 算法无法得到正确结果。因为该算法会在某个顶点具有最小临时距离时就将其贪心地确定下来，但之后出现的一条负权边可能会提供一条到达该顶点的更短路径。
As an example, suppose the edges are A-B with weight 2, A-C with weight 4, and C-B with weight -3. Starting at A, the algorithm sets B = 2 and C = 4. It visits B first, marks it as final, and then relaxes C-B to give a path A-C-B with total cost 1. However, B has already been visited, so the correct shortest path is missed.
举例来说，假设边为 A-B 权值 2，A-C 权值 4，C-B 权值 -3。从 A 开始，算法设 B = 2，C = 4。它先访问 B 并将其标记为最终节点，然后通过 C-B 松弛得到路径 A-C-B，总代价为 1。但此时 B 已经被访问过，因此正确的最短路径被遗漏了。
For graphs that may contain negative edges, the Bellman-Ford algorithm should be used instead, because it can correctly handle them, although it has a higher time complexity.
对于可能包含负权边的图，应改用 Bellman-Ford 算法，因为它能正确处理负权边，尽管其时间复杂度更高。
10. Dijkstra vs A* Search | Dijkstra 与 A* 搜索
Dijkstra’s algorithm explores outward from the source in all directions based purely on actual known distances. It guarantees the shortest path but can be slow for large graphs because it does not use any information about the target’s direction.
Dijkstra 算法仅根据已知的实际距离，从源点向所有方向扩展搜索。它能保证最短路径，但在大规模图中可能较慢，因为它没有利用任何关于目标方向的信息。
The A* algorithm improves on Dijkstra by using a heuristic function h(n) that estimates the remaining cost from a node to the target. Its selection priority is dist[n] + h(n). Dijkstra is a special case of A* where h(n) = 0 for every node.
A* 算法通过使用启发函数 h(n) 来改进 Dijkstra，该函数估计从节点 n 到目标的剩余代价。它的选择优先级为 dist[n] + h(n)。Dijkstra 是 A* 在 h(n) = 0 时的特殊情况。
If the heuristic is admissible, meaning it never overestimates the true remaining cost, A* is guaranteed to find the shortest path while usually visiting fewer nodes than Dijkstra.
如果启发函数是可采纳的，即它从不高估真实的剩余代价，那么 A* 算法保证能够找到最短路径，同时通常比 Dijkstra 访问更少的节点。
11. Exam Technique and Presentation | 考试技巧与作答呈现
In Edexcel A-Level Computer Science exams, you may be asked to run Dijkstra’s algorithm on a given graph, complete a working-values table, or state the final shortest path and its length. Clear presentation is essential for full marks.
在 Edexcel A-Level 计算机科学考试中，你可能会被要求对给定图运行 Dijkstra 算法、填写工作值表，或者写出最终的最短路径及其长度。清晰的作答呈现对于获得满分至关重要。
A well-presented answer should include a table showing all vertices, their current distances, their predecessor vertices, and whether each vertex has been visited. At each iteration, the selected vertex should be clearly stated.
一份好的答案应包括一个表格，显示所有顶点、它们的当前距离、前驱节点以及每个顶点是否已访问。在每次迭代中，应清楚地说明所选择的顶点。
After the algorithm finishes, you must reconstruct the shortest path using the predecessor column and state the total weight. Do not forget to write the path in the correct order from source to target.
算法结束后，你必须使用前驱列重建最短路径，并写出总权值。不要忘记按从源点到目标的正确顺序书写路径。
12. Common Mistakes and Revision Checklist | 常见错误与复习清单
Common mistakes include forgetting to initialise all distances to infinity, updating visited vertices after they have been finalised, selecting a vertex with a larger distance instead of the smallest, and failing to record predecessors for path reconstruction.
常见错误包括：忘记将所有距离初始化为无穷大、在顶点已经确定后仍对其进行更新、选择了距离较大的顶点而不是最小距离顶点，以及没有记录前驱节点导致无法重建路径。
Use this checklist before an exam: initialise source to 0 and others to ∞; select the unvisited vertex
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply