A-Level计算机：Dijkstra最短路径算法全解析 | Dijkstra’s Shortest Path Algorithm

📌 引言 / Introduction

在 A-Level 计算机科学课程中，优化算法（Optimisation Algorithm）是一个核心考点。其中，Dijkstra 最短路径算法是 AQA 考试局 4.3.6 章节的必学内容。它不仅出现在理论考题中，更是现代导航系统、网络路由等技术的底层基础。本文将带你全面理解 Dijkstra 算法的原理、实现与应用。

In the A-Level Computer Science curriculum, optimisation algorithms are a key topic. Among them, Dijkstra’s shortest path algorithm is required content in AQA specification 4.3.6. It appears not only in exam theory questions but also underpins modern navigation systems and network routing. This article provides a comprehensive guide to understanding, tracing, and applying Dijkstra’s algorithm.

🔑 核心知识点 / Key Knowledge Points

1️⃣ 什么是Dijkstra算法？/ What is Dijkstra’s Algorithm?

Dijkstra 算法是一种贪心算法，用于在加权图中寻找从起始节点到所有其他节点的最短路径。与广度优先搜索（BFS）不同，Dijkstra 使用优先队列（Priority Queue）来高效管理待访问节点。算法由荷兰计算机科学家 Edsger W. Dijkstra 于 1959 年提出，至今仍是图论中最经典的算法之一。

Dijkstra’s algorithm is a greedy algorithm that finds the shortest path from a starting node to every other node in a weighted graph. Unlike breadth-first search (BFS), Dijkstra uses a priority queue to efficiently manage nodes to visit. It was proposed by Dutch computer scientist Edsger W. Dijkstra in 1959 and remains one of the most classic graph algorithms.

2️⃣ 算法步骤 / Algorithm Steps

• 初始化：将起始节点的距离设为 0，其他节点设为无穷大。将所有节点标记为未访问。
• 选择当前节点：从未访问节点中选择距离最小的节点作为当前节点。
• 更新邻居：对于当前节点的每个未访问邻居，计算经过当前节点的距离。如果新距离更短，则更新该邻居的距离。
• 标记已访问：将当前节点标记为已访问。
• 重复：直到所有节点都被访问，或目标节点已被标记。

English version:

• Initialisation: Set the start node’s distance to 0, all others to infinity. Mark all nodes as unvisited.
• Select current node: Choose the unvisited node with the smallest distance.
• Update neighbours: For each unvisited neighbour, calculate the distance through the current node. Update if shorter.
• Mark visited: Mark the current node as visited.
• Repeat: Until all nodes are visited or the target is reached.

3️⃣ 优先队列的作用 / Role of the Priority Queue

Dijkstra 算法的时间复杂度取决于数据结构的选择：使用简单的数组实现为 O(V²)；而使用二叉堆（Binary Heap）作为优先队列可优化至 O((V+E) log V)。这正是 A-Level 考试中可能出现的 dry-run 表格题的核心——你需要追踪每次迭代中优先队列的变化。

The time complexity of Dijkstra’s algorithm depends on the data structure used: O(V²) with a simple array, versus O((V+E) log V) with a binary heap priority queue. This is precisely what may appear in A-Level exam dry-run table questions — tracing how the priority queue changes with each iteration.

4️⃣ 实际应用 / Real-World Applications

• 📍 卫星导航系统（Sat Nav / GPS）：计算从起点到目的地的最短或最快路线。
• 🌐 网络路由（Network Routing）：路由器使用 Dijkstra 算法确定数据包的最优传输路径（如 OSPF 协议）。
• 🎮 游戏AI（Game AI）：在策略游戏和 RPG 中计算角色移动的路径。
• 🚚 物流规划（Logistics）：优化配送路线，降低运输成本。

English version:

• 📍 Satellite Navigation (GPS): Computing the shortest or fastest route from start to destination.
• 🌐 Network Routing: Routers use Dijkstra’s algorithm to determine optimal packet paths (e.g., OSPF protocol).
• 🎮 Game AI: Pathfinding for character movement in strategy games and RPGs.
• 🚚 Logistics Planning: Optimising delivery routes to reduce transportation costs.

5️⃣ 与其他算法的对比 / Comparison with Other Algorithms

💡 学习建议 / Study Tips

1. 动手画图 / Draw it out: 用纸笔手动模拟 Dijkstra 算法的每一步——从简单的 4-5 个节点的图开始，逐步增加复杂度。A-Level 考试中经常要求填写 dry-run 表格。
2. 理解而非背诵 / Understand, don’t memorise: 不要死记硬背代码。理解为什么每次选择距离最小的节点、为什么需要优先队列，远比记住代码行更重要。
3. 刷真题 / Practise past papers: AQA 历年真题中 Dijkstra 相关题目反复出现。建议至少完成近 5 年所有相关真题，熟悉出题风格。
4. 做比较笔记 / Compare algorithms: 将 Dijkstra 与 BFS、A* 做对比表格，清晰区分各自的适用场景和数据结构差异。
5. 代码实现 / Code it: 用 Python 或 pseudocode 实现一遍完整的 Dijkstra 算法，加深对优先队列和松弛操作的理解。