📚 Using Dijkstra’s algorithm to find the shortest path | 使用Dijkstra算法寻找最短路径
Dijkstra's algorithm is a fundamental graph search method that solves the single-source shortest path problem for a graph with non-negative edge weights. It works by iteratively selecting the vertex with the smallest known distance from the source, updating its neighbours, and gradually building a shortest-path tree. For A-Level Computer Science, understanding this algorithm is essential for tackling network routing, logistics planning, and algorithmic thinking questions. The method relies on a priority queue to achieve efficient performance, typically O((V+E) log V) with a binary heap.
Dijkstra算法是一种基础的图搜索方法，用于求解具有非负边权图的单源最短路径问题。它通过反复选择当前已知距离源点最小的顶点，更新其邻居的距离，并逐步构建最短路径树。在A-Level计算机科学中，理解该算法对于解决网络路由、物流规划和算法思维题至关重要。该方法依靠优先队列来实现高效性能，使用二叉堆时通常为 O((V+E) log V) 时间复杂度。
1. Introduction to Dijkstra’s Algorithm | Dijkstra算法简介
Dijkstra's algorithm was conceived by Edsger W. Dijkstra in 1956 and published in 1959. It belongs to the family of greedy algorithms because at each step it picks the locally optimal choice – the unvisited vertex with the smallest tentative distance – assuming that this will lead to a globally optimal solution. The algorithm is only valid when all edge weights are non-negative; negative weights can cause it to fail by permanently locking in suboptimal distances.
Dijkstra算法由 Edsger W. Dijkstra 于1956年构思，1959年发表。它属于贪心算法家族，因为在每一步中它都选择局部最优解——即具有最小临时距离的未访问顶点——假定这将导向全局最优解。该算法仅在所有权重非负时有效；负权重会导致错误，因为它会永久固定次优的距离。
2. Graph Representation for Shortest Path | 用于最短路径的图表示
Before applying Dijkstra’s algorithm, we must represent the graph in a format suitable for computation. An adjacency list is typically used: for each vertex, we store a list of pairs (neighbour, weight). Alternatively, an adjacency matrix can be used, but it is less efficient for sparse graphs. For A-Level Edexcel, questions often provide the graph as a diagram with edge weights; you are expected to translate it into a table of distances or draw the adjacency structure.
在应用Dijkstra算法之前，我们必须用适合计算的格式表示图。通常使用邻接表：对每个顶点，存储一个(邻居, 权重)对的列表。也可以使用邻接矩阵，但对于稀疏图效率较低。在Edexcel A-Level考试中，题目通常给出带边权重的图；你应当将其转化为距离表格或画出邻接结构。
- Graph G = (V, E) where V is set of vertices, E is set of edges.
- 图 G = (V, E)，其中 V 是顶点集，E 是边集。
- Edge weight w(u, v) ≥ 0 for all (u, v) in E.
- 每条边权重 w(u, v) ≥ 0。
- Adjacency list: adj[u] = {(v1, w1), (v2, w2), ...}
- 邻接表：adj[u] = {(v1, w1), (v2, w2), ...}
3. Key Data Structures: Distance, Predecessor, and Priority Queue | 关键数据结构：距离、前驱和优先队列
Dijkstra' urce to that vertex, initialised to infinity (∞) and zero for the source. Second, an array prev[] records the preceding vertex on the current shortest path, enabling us to reconstruct the full path later. Third, a priority queue (min-heap) is used to efficiently select the vertex with the smallest dist[] value that has not yet been finalised.
Dijkstra算法为每个顶点维护三个关键信息。第一，数组 dist[] 存储从源点到该顶点当前的最短距离，初始化为无穷大(∞)，源点为0。第二，数组 prev[] 记录当前最短路径上的前驱顶点，使我们能够随后重构完整路径。第三，使用优先队列(最小堆)高效选择未最终确定且 dist[] 值最小的顶点。
| Data Structure | Purpose | Initialization |
|---|---|---|
| dist[] | Store shortest path estimate | All ∞ except source = 0 |
| prev[] | Track path predecessor | None or null |
| Priority queue Q | Select vertex with minimum dist | Contains source with key 0 |
数据结构 | 用途 | 初始化
dist[]: 存储最短路径估计; 所有为∞，源点为0
prev[]: 记录路径前驱; 无或空
优先队列Q: 选择最小dist的顶点; 包含源点，键值为0
4. The Algorithm Step by Step | 算法逐步解析
Dijkstra's algorithm proceeds by repeatedly extracting the vertex with the minimum distance from the priority queue. For each neighbour of this vertex, we perform relaxation: if the distance to the neighbour via the current vertex is smaller than the known distance, update dist[neighbour] and prev[neighbour], then insert or decrease-key in the priority queue. The process continues until the queue is empty, at which point all reachable vertices have their correct shortest distances.
Dijkstra算法通过反复从优先队列中提取距离最小的顶点进行。对于该顶点的每个邻居，我们执行松弛操作：如果通过当前顶点到达邻居的距离小于已知距离，则更新 dist[邻居] 和 prev[邻居]，然后在优先队列中插入或减小键值。该过程一直持续到队列为空，此时所有可达顶点的最短距离均已正确确定。
- her dist[v] = ∞; prev[v] = undefined for all v. Create min-priority queue Q with (src, 0).
- 初始化 dist[src]=0，所有其他 dist[v]=∞；所有 prev[v] 未定义。创建最小优先队列 Q，插入 (src,0)。
- While Q is not empty: remove vertex u with smallest dist[u].
- 当 Q 非空：移除具有最小 dist[u] 的顶点 u。
- t[v], then update dist[v] = dist[u] + w, prev[v] = u, and insert/update (v, dist[v]) in Q.
- 对于 u 的每个邻居 v 及其权重 w：若 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w，prev[v] = u，并将 (v, dist[v]) 插入或更新至 Q 中。
- Once Q is empty, dist[] contains shortest distances.
- 一旦 Q 为空，dist[] 包含最短距离。
5. Worked Example: Finding the Shortest Path | 实际示例：寻找最短路径
Consider a graph with vertices A, B, C, D, E and weighted edges: A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2. The source is A. We will trace the algorithm to find the shortest path to E.
考虑一个图，顶点为 A, B, C, D, E，带权边：A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2。源点为 A。我们将追踪算法以找到到 E 的最短路径。
| Step | Vertices in Q | Selected u | dist[A] | dist[B] | dist[C] | dist[D] | dist[E] |
|---|---|---|---|---|---|---|---|
| 0 | A | - | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | B,C | A | 0 | 4 | 2 | ∞ | ∞ |
| 2 | B,D,E | C | 0 | 3 (via C) | 2 | 10 | 12 |
| 3 | D,E | B | 0 | 3 | 2 | 8 (via B) | 12 |
| 4 | E | D | 0 | 3 | 2 | 8 | 10 (via D) |
| 5 | - | E | 0 | 3 | 2 | 8 | 10 |
ia D. The predecessor chain reconstructed from prev[E]=D, prev[D]=B, prev[B]=C, prev[C]=A.
到 E 的最短路径：A → C → B → D → E，总权重为10。注意通过 C 直达 E 的路径权重为12，但我们经由 D 发现了一条更好的路径。可以从 prev[E]=D, prev[D]=B, prev[B]=C, prev[C]=A 重构前驱链。
6. Pseudocode for Dijkstra’s Algorithm | Dijkstra算法的伪代码
The following pseudocode captures Dijkstra's algorithm using a min-priority queue. It assumes a graph is given as an adjacency list. The decrease-key operation is handled by inserting a new entry with the updated distance and ignoring stale entries when popped.
以下伪代码使用最小优先队列描述了Dijkstra算法。它假设图以邻接表给出。通过插入带有更新距离的新条目并在弹出时忽略过期条目来处理减小键值操作。
DIJKSTRA(G, src):
FOR each vertex v in G.V:
dist[v] = INFINITY
prev[v] = NIL
dist[src] = 0
Q = min-priority queue
Q.insert(src, 0)
WHILE Q is not empty:
u = Q.extract_min()
FOR each neighbour v of u with weight w:
IF dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
Q.insert(v, dist[v]) // instead of decrease-key
RETURN dist, prev
This implementation is exam-friendly; you can also use a version where Q stores all vertices and you extract min by scanning dist[] if a priority queue is not explicitly required.
这个实现适合考试；你也可以使用一个版本，其中 Q 存储所有顶点，如果未明确要求优先队列，则通过扫描 dist[] 来提取最小值。
7. Using a Binary Heap for Efficiency | 使用二叉堆提高效率
exity. With a binary heap (or a Fibonacci heap), extraction takes O(log V) and insertion or decrease-key takes O(log V), giving O((V+E) log V). For dense graphs where E ≈ V², the heap version still outperforms the naive approach in most practical cases.
在没有优先队列的朴素实现中，每次提取最小距离顶点需要 O(V) 时间，导致总体时间复杂度为 O(V²)。使用二叉堆(或斐波那契堆)时，提取操作为 O(log V)，插入或减小键值为 O(log V)，得到 O((V+E) log V)。对于接近 E ≈ V² 的稠密图，堆版本在大多数实际情况下仍优于朴素方法。
- Binary heap: extract-min O(log V), insert O(log V), decrease-key O(log V).
- 二叉堆：提取最小 O(log V)，插入 O(log V)，减小键值 O(log V)。
- Fibonacci heap: extract-min O(log V) amortised, insert O(1), decrease-key O(1).
- 斐波那契堆：提取最小 O(log V) 均摊，插入 O(1)，减小键值 O(1)。
8. Why Negative Edge Weights Break Dijkstra | 为什么负权边会破坏Dijkstra算法
Dijkstra's greedy strategy assumes that once a vertex's distance is finalised (when popped from the priority queue), no future path can improve it. This holds when all edge weights are non-negative. If a graph contains a negative weight edge, a longer path might be discovered later that reduces the total cost, but the vertex already finalised will not be revisited, leading to incorrect results. For graphs with negative edges, the Bellman-Ford algorithm should be used.
Dijkstra的贪心策略假设一旦一个顶点的距离被最终确定(当从优先队列弹出时)，任何未来的路径都不能改善它。当所有边权非负时，这一假设成立。如果图中包含负权边，可能之后会发现一条更长的路径却降低了总成本，但已最终确定的顶点不会重新访问，从而导致错误结果。对于带负权边的图，应使用Bellman-Ford算法。
s via B with cost 1, but Dijkstra finalises C with distance 2 first and never corrects it.
示例：顶点 A, B, C；边 A→B:4, A→C:2, B→C:-3。真正的最短路径 A→C 经由 B 的成本为1，但Dijkstra首先以距离2最终确定了C，并且不再纠正。
9. Proof of Correctness (Brief) | 正确性简要证明
The correctness of Dijkstra's algorithm can be shown by induction. At the moment a vertex u is extracted from the queue, its dist[u] equals the true shortest distance from the source. This is because any alternative path must leave the set of visited vertices via some edge with non-negative weight, and the distance to u is minimal among all unvisited vertices. Thus, no shorter path can exist. By induction, all vertices extracted sequentially have correct distances.
Dijkstra算法的正确性可通过归纳法证明。在顶点 u 从队列中弹出的那一刻，其 dist[u] 等于从源点出发的真正最短距离。这是因为任何备选路径都必须通过某条非负权的边离开已访问顶点集合，而 u 在所有未访问顶点中距离最小。因此不可能存在更短的路径。通过归纳，依次提取的所有顶点都具有正确的距离。
This relies on the non-negative weight assumption; if some weight is negative, the inductive step fails.
这依赖于非负权重的假设；如果某些权重为负，归纳步骤将失败。
10. Real-World Applications | 实际应用
Dijkstra's algorithm is widely used in network routing protocols, such as OSPF (Open Shortest Path First) and IS-IS, where routers compute shortest paths to all destinations in a link-state network. It is also applied in GPS navigation systems to find the quickest route, in robotics for path planning, and in games for AI movement. Whenever you need to minimise distance or cost in a graph with non-negative weights, Dijkstra is a go-to solution.
Dijkstra算法广泛应用于网络路由协议，如OSPF(开放最短路径优先)和IS-IS，其中路由器在链路状态网络中计算到所有目的地的最短路径。它还应用于GPS导航系统以查找最快路线、机器人路径规划以及游戏中的AI移动。当需要在非负权图中最小化距离或成本时，Dijkstra是首选方案。
11. Limitations and Alternatives | 局限与替代算法
Besides the negative weight limitation, Dijkstra's algorithm may be inefficient for extremely large graphs if an inappropriate data structure is used. For single-pair shortest path without negative edges, A* search can be faster by using a heuristic to guide the search. For graphs with negative edges, Bellman-Ford runs in O(VE) and can detect negative cycles. The Floyd-Warshall algorithm computes all-pairs shortest paths in O(V³), which is useful for dense graphs or when multiple queries are needed.
除了负权重限制外，如果使用了不恰当的数据结构，Dijkstra算法对于极大的图可能效率低下。对于没有负权边的单对最短路径，A*搜索通过使用启发式引导搜索可以更快。对于带负权边的图，Bellman-Ford以 O(VE) 运行并可检测负环。Floyd-Warshall算法以 O(V³) 计算所有点对的最短路径，适用于稠密图或需要多次查询的场景。
| Algorithm | Handles Negative Weights? | Time Complexity | Use Case |
|---|---|---|---|
| Dijkstra (heap) | No | O((V+E) log V) | Single-source, non-neg weights |
| Bellman-Ford | Yes | O(VE) | Single-source, detects neg cycles |
| A* search | No | Dependent on heuristic | Single-pair, directed search |
| Floyd-Warshall | Yes (no neg cycles) | O(V³) | All-pairs shortest paths |
算法 | 处理负权？ | 时间复杂度 | 适用场景
Dijkstra(堆): 否，O((V+E) log V)，单源，非负权
Bellman-Ford: 是，O(VE)，单源，检测负环
A*搜索: 否，取决于启发式，单对，定向搜索
Floyd-Warshall: 是(无负环)，O(V³)，全源最短路径
12. Exam Tips and Common Pitfalls | 考试技巧和常见陷阱
When answering Dijkstra-related questions in Edexcel A-Level Computer Science exams, always show your working table or step-by-step distances. Clearly label the order in which vertices are finalised. Double-check that you do not assign a final distance until the vertex is extracted from the priority queue; many students mistakenly think the distance is final as soon as updated. Also, remember to state that it only works for non-negative weights; the examiner often awards a mark for this condition. Practice reconstructing the path using the predecessor array and be ready to discuss efficiency trade-offs.
在Edexcel A-Level计算机科学考试中回答Dijkstra相关问题时，始终展示你的工作表格或逐步距离。清晰地标明顶点被最终确定的顺序。仔细检查，直到顶点从优先队列中弹出才指定最终距离；许多学生错误地认为距离一旦更新就是最终的。另外，记得说明它只适用于非负权重；考官通常为这一条件给分。练习使用前驱数组重建路径，并准备好讨论效率权衡。
- Start with a correct initialisation: dist[source]=0, all others ∞, and Q contains source.
- 以正确的初始化开始：dist[源点]=0，其他为∞，Q包含源点。
- For each step, extract the unvisited vertex with smallest dist, NOT just any neighbour.
- 每一步，提取未访问顶点中 dist 最小的，而不是任意邻居。
- Update neighbours carefully: if new distance is strictly smaller, update and record predecessor.
- 仔细更新邻居：如果新距离严格小于旧距离，更新并记录前驱。
- Write the final shortest-path tree as a set of edges or list the path explicitly.
- 将最终最短路径树写为一组边或明确列出路径。
- Mention time complexity and data structures if the question asks for evaluation.
- 如果问题要求评估，提及时间复杂度和数据结构。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图