Decision Mathematics 1 (D1): Graph Algorithms for Minimum Spanning Trees and Shortest Paths — 决策数学1(D1)：最小生成树与最短路径的图论算法

一、什么是决策数学：从算法思维出发 | What Is Decision Mathematics: Starting from Algorithmic Thinking

决策数学（Decision Mathematics，简称 D1）是 Edexcel A-Level 进阶数学（Further Mathematics）中一门非常独特的模块。它与纯数学（Pure Mathematics）处理连续函数、极限和微积分不同，也与力学（Mechanics）研究运动和受力不同，决策数学研究的是”如何用明确的步骤解决离散问题”。这类问题的核心不是”计算一个数值”，而是”设计一个过程”：给定一堆数据或一个网络，找到最优解或者可行的解。

Decision Mathematics (D1) is a distinctive module within Edexcel A-Level Further Mathematics. Unlike Pure Mathematics, which deals with continuous functions, limits and calculus, and unlike Mechanics, which studies motion and forces, Decision Mathematics is concerned with “how to solve discrete problems using explicit steps.” The core of these problems is not “compute a value” but “design a procedure”: given a set of data or a network, find an optimal solution or a feasible solution.

在这门课里，你会反复遇到一个关键词：算法（algorithm）。算法是一组可以一步一步执行的、明确而有限的指令。例如，把一副扑克牌按从小到大的顺序排好，你可以用冒泡排序（bubble sort），也可以用快速排序（quick sort）；从一张地铁线路图里找出从 A 站到 B 站的最短乘车路线，你可以用 Dijkstra 算法。掌握决策数学，本质上是学会”像计算机一样思考”，并把这种思考用人类能检查的方式写在答题纸上。

In this module you will meet one keyword again and again: the algorithm. An algorithm is a finite, unambiguous set of instructions that can be carried out step by step. For example, to sort a deck of cards into ascending order you can use bubble sort or quick sort; to find the shortest route from station A to station B on a metro map you can use Dijkstra’s algorithm. Mastering Decision Mathematics is essentially learning to “think like a computer” while writing your thinking in a way an examiner can check on paper.

Edexcel 的 D1 考试非常强调”过程”。一道最小生成树（Minimum Spanning Tree）或者最短路径（Shortest Path）的题目，即使你写出了正确的最终答案，只要中间的排序、选边或者标号过程有一步顺序错误，就会被扣分。因此，理解每一个算法”为什么这样走”比死记步骤更重要。本文聚焦 D1 中最常考、也最容易被扣分的图论算法：Kruskal、Prim 和 Dijkstra，并从”图与网络”的基础概念讲起。

Edexcel D1 exams place heavy emphasis on process. For a Minimum Spanning Tree or Shortest Path question, even if you write down the correct final answer, you will lose marks if any intermediate step of sorting, edge-selection or labelling is out of order. Therefore, understanding “why each algorithm moves the way it does” matters more than memorising steps. This article focuses on the graph-theory algorithms that are most frequently examined and most often penalised in D1: Kruskal, Prim and Dijkstra, starting from the basic concepts of graphs and networks.

二、图与网络的基本结构：顶点、边、权与树 | Graphs and Networks: Vertices, Edges, Weights and Trees

在决策数学里，一个”图”（graph）由两个集合组成：顶点（vertices 或 nodes）的集合，以及连接这些顶点的边（edges 或 arcs）的集合。顶点通常用大写字母表示，例如 A、B、C、D；每条边连接两个顶点，可以带有一个数字，这个数字叫”权”（weight）。权可以表示距离、时间、成本或者任何你希望最小化的量。带权的图就叫”网络”（network）。

In Decision Mathematics a graph consists of two sets: a set of vertices (nodes) and a set of edges (arcs) joining them. Vertices are usually written with capital letters, for example A, B, C, D; each edge joins two vertices and may carry a number called its weight. The weight can represent distance, time, cost or any quantity you wish to minimise. A weighted graph is called a network.

有几类特殊的图需要牢牢记住。第一，”简单图”（simple graph）中任意两个顶点之间最多只有一条边，且没有连接某个顶点到它自己的”环”（loop）。第二，”有向图”（digraph 或 directed graph）中的边有方向，用箭头表示，例如表示”从 A 出发、沿单行道到达 B”；而”无向图”中的边可以双向通行。第三，”树”（tree）是一种特殊的连通图：它把所有的顶点都连在一起，但不存在任何回路（cycle）。树在 D1 中极为重要，因为最小生成树本质上就是”权最小的树”。

Several special kinds of graph must be remembered. First, in a simple graph there is at most one edge between any two vertices and no loop joining a vertex to itself. Second, a directed graph (digraph) has edges with directions, shown by arrows, for example representing “travel from A along a one-way street to B”; in an undirected graph the edges can be traversed in both directions. Third, a tree is a special connected graph: it joins all the vertices together but contains no cycles. Trees matter enormously in D1, because a minimum spanning tree is essentially “the tree of smallest total weight.”

另外一个反复出现的概念是顶点的”度”（degree）：就是与该顶点相连的边的条数。例如，如果一个顶点连接了 3 条边，它的度就是 3。度在判断一个图能否构成树、以及在”路线检查”（route inspection）等问题里都很有用。理解了这些术语，我们就可以进入 D1 的核心问题：在给定网络里，如何用最小的总代价把全部顶点连接起来。

Another recurring concept is the degree of a vertex: the number of edges incident to it. If a vertex has three edges attached, its degree is 3. Degree is useful when deciding whether a graph can form a tree, and in problems such as route inspection. Once you understand these terms, we can move to the central question of D1: given a network, how do we connect all the vertices at minimum total cost?

三、最小生成树问题：用最小的总代价连接所有顶点 | The Minimum Spanning Tree Problem: Connecting All Vertices at Minimum Cost

设想你要为一片新开发区铺设水管，把几个居民点全部连到同一个供水系统里。管道可以沿居民点之间的道路铺设，每条道路的铺设成本不同。你的任务是：让所有居民点都连在一起（不要求每一对居民点之间都有直接管道，只要通过管网彼此可达即可），同时让总成本尽可能低。这就是”最小生成树”（Minimum Spanning Tree，简称 MST）问题。

Imagine you are laying water pipes in a new housing estate so that several settlements are all joined to one supply system. Pipes can run along roads between the settlements, and each road has a different laying cost. Your task is to connect all the settlements together (you do not need a direct pipe between every pair, only that they are all reachable through the network) while keeping the total cost as low as possible. This is the Minimum Spanning Tree (MST) problem.

最小生成树有两条必须同时满足的性质。第一，它必须是”生成”的（spanning）：图中每一个顶点都必须被包含进来。第二，它必须是”树”（tree）：连通且没有回路。一个包含 n 个顶点的树恰好有 n − 1 条边，这是一个非常方便的检查条件：如果你最终画出的 MST 边数不是 n − 1，那一定算错了。第三，它必须是”最小”的：所有可能生成树中，它的边的总权最小。

A minimum spanning tree must satisfy two properties at the same time. First, it must be spanning: every vertex of the graph must be included. Second, it must be a tree: connected and cycle-free. A tree on n vertices has exactly n − 1 edges, which is a very convenient check: if the MST you finally draw does not have n − 1 edges, something is wrong. Third, it must be minimal: among all possible spanning trees, its total edge weight is the smallest.

注意，最小生成树在”总权最小”的意义下是唯一的，但在”具体选了哪些边”上可能不唯一：当网络里有若干条边权相等时，可能存在多个总权相同的最小生成树。考试时，只要边的总权正确、边数为 n − 1、且连通无回路，通常就能拿到满分，即使你选择的边和答案示例不完全一样。Edexcel 的评分标准要求你展示”选边的顺序”，因此接下来我们要学习的 Kruskal 和 Prim 两种算法，本质上就是两种”系统地挑选最小权边”的方法。

Note that the MST is unique in the sense of “minimum total weight” but not necessarily unique in the specific edges chosen: when several edges have equal weight, there can be several MSTs with the same total. In an exam, as long as the total weight is correct, the number of edges is n − 1, and the result is connected and cycle-free, you will normally get full marks even if your chosen edges differ from a sample answer. Edexcel mark schemes require you to show the order in which you select edges, so the two algorithms we now study, Kruskal and Prim, are essentially two ways of “systematically picking the smallest-weight edges.”

四、Kruskal 算法：按边权从小到大排序、逐个连接 | Kruskal’s Algorithm: Sort Edges by Weight and Join Them One by One

Kruskal 算法的思路非常直观：既然我们要总权最小，那就先把所有的边按权从小到大排好，然后从最小的边开始，一条一条地加入。唯一要遵守的规则是”不要形成回路”：如果一条边会把已经连起来的两个顶点再次连在一起（也就是会形成回路），就跳过它。重复这个过程，直到选满 n − 1 条边为止。

The idea behind Kruskal’s algorithm is very intuitive: since we want the smallest total weight, first sort all the edges in ascending order of weight, then add them one by one starting from the smallest. The only rule to obey is “do not form a cycle”: if an edge would reconnect two vertices that are already joined (that is, it would close a cycle), skip it. Repeat until exactly n − 1 edges have been chosen.

我们用一个具体例子来说明。考虑一个有 5 个顶点 A、B、C、D、E 的网络，边的权如下（单位忽略）：AB = 3，AE = 1，BC = 5，BE = 4，CE = 2，CD = 7，DE = 6。首先按权从小到大排序：AE(1)、CE(2)、AB(3)、BE(4)、BC(5)、DE(6)、CD(7)。然后逐个检查并选边。

Let us illustrate with a concrete example. Consider a network on 5 vertices A, B, C, D, E with the following edge weights: AB = 3, AE = 1, BC = 5, BE = 4, CE = 2, CD = 7, DE = 6. First sort the edges in ascending order: AE(1), CE(2), AB(3), BE(4), BC(5), DE(6), CD(7). Then examine and select edges one at a time.

步骤 Step	考虑的边 Edge	权 Weight	是否选入 Included?	理由 Reason
1	AE	1	是 Yes	不形成回路 No cycle
2	CE	2	是 Yes	不形成回路 No cycle
3	AB	3	是 Yes	不形成回路 No cycle
4	BE	4	否 No	会形成回路 A-B-E-A Would form cycle A-B-E-A
5	BC	5	否 No	会形成回路 A-B-C-E-A Would form cycle
6	DE	6	是 Yes	不形成回路，边数已满 4 条 No cycle, 4 edges reached

最终选入的边是 AE、CE、AB、DE，共 4 条（n − 1 = 4），总权为 1 + 2 + 3 + 6 = 12。检查：5 个顶点全部连通，没有任何回路，边数正好是 4，因此这就是最小生成树。注意 BE 和 BC 被跳过是因为它们会形成回路，而不是因为它们的权比某些已选边更大。

The edges finally chosen are AE, CE, AB and DE, four edges in total (n − 1 = 4), with total weight 1 + 2 + 3 + 6 = 12. Check: all five vertices are connected, there is no cycle, and the edge count is exactly 4, so this is the minimum spanning tree. Note that BE and BC were skipped because they would create a cycle, not because their weights are larger than some chosen edge.

考试时展示 Kruskal 的关键是：第一，先把所有边按权排序写出来（这是得分点）；第二，按顺序一条条列出来，明确写出”选”还是”拒”，并对拒绝的边给出”形成回路”的理由；第三，最后写出总权和边的数量。千万不要只画一张图了事，排序列表和拒绝理由正是 Edexcel 评分标准里”方法分”的来源。

The keys to presenting Kruskal in an exam are: first, write out the sorted list of all edges by weight (this earns method marks); second, list them one by one, clearly writing “choose” or “reject”, giving the reason “would form a cycle” for rejected edges; third, finish with the total weight and the number of edges. Never just draw a diagram and stop: the sorted list and the rejection reasons are exactly where the Edexcel mark scheme awards method marks.

五、Prim 算法：从一个顶点出发、向外生长的树 | Prim’s Algorithm: Grow the Tree Outward from a Single Vertex

Prim 算法走的是另一条路：它不先给所有边排序，而是”从内部向外生长”。你先任意选择一个起始顶点，把它加入树中；然后反复执行这样一步：在所有”一端在树内、另一端在树外”的边中，选出权最小的那一条，把树外的那个顶点和这条边一起加入树中。重复，直到所有顶点都进入树里。

Prim’s algorithm takes a different route: rather than sorting all edges first, it grows “from the inside outward”. You first choose any starting vertex and add it to the tree; then repeatedly perform this step: among all edges with one end inside the tree and the other end outside, choose the one of smallest weight, and add both that outside vertex and that edge to the tree. Repeat until every vertex is in the tree.

Prim 有两个常见变体：基于顶点矩阵的”表格形式”（matrix form），以及基于网络的”图形形式”（graphical form）。表格形式适合顶点很多、但网络是完整图（每对顶点之间都有边）的情形，它用一个不断增大的表格记录”已选边”和”候选边的权”。考试中 Edexcel 通常要求你明确采用其中一种形式，并保持格式一致。

Prim has two common variants: the matrix (tabular) form based on a table of vertices, and the graphical form based on the network. The matrix form suits cases with many vertices where the network is complete (an edge between every pair); it records “chosen edges” and “candidate edge weights” in a growing table. In exams Edexcel usually asks you to use one specific form and to keep the format consistent.

还是用上一节的同一个网络做例子，这次从顶点 A 开始。树内初始只有 {A}。候选边中，连接 A 到树外顶点的只有 AB(3) 和 AE(1)，最小的权是 1，所以选 AE，把 E 加入树中。现在树内是 {A, E}，候选边变为：AB(3)、EB(4)、EC(2)、ED(6)，最小的是 EC(2)，选 CE，把 C 加入。树内是 {A, E, C}，候选边为：AB(3)、EB(4)、CB(5)、CD(7)、ED(6)，最小的是 AB(3)，选 AB，把 B 加入。最后树内是 {A, E, C, B}，候选边为 CB(5)、CD(7)、ED(6)，最小的是 ED(6)，选 DE，把 D 加入。全部 5 个顶点都进入树中，结束。

Let us reuse the same network from the previous section, this time starting from vertex A. Initially the tree contains only {A}. Among the candidate edges, those joining A to outside vertices are AB(3) and AE(1); the smallest weight is 1, so we choose AE and add E to the tree. Now the tree is {A, E}, and the candidates are AB(3), EB(4), EC(2) and ED(6); the smallest is EC(2), so we choose CE and add C. The tree is {A, E, C}, with candidates AB(3), EB(4), CB(5), CD(7) and ED(6); the smallest is AB(3), so we choose AB and add B. Finally the tree is {A, E, C, B}, with candidates CB(5), CD(7) and ED(6); the smallest is ED(6), so we choose DE and add D. All five vertices are now in the tree, so we stop.

Prim 最终选入的边也是 AE、CE、AB、DE，总权同样是 12。这印证了一个重要事实：无论用 Kruskal 还是 Prim，只要网络的最小生成树总权唯一，两种算法都会得到相同的总权；不同的只是选边的顺序和思考方式。考试时如果题目要求”用 Prim 算法”，你必须从指定的（或你声明的）起始顶点开始，并清楚地列出每一步的候选边和所选边。

Prim’s final edge set is also AE, CE, AB and DE, with the same total weight of 12. This confirms an important fact: whether you use Kruskal or Prim, as long as the MST total weight is unique, both algorithms yield the same total weight; they differ only in the order of selection and the way of thinking. In an exam, if the question says “use Prim’s algorithm”, you must start from the specified (or your declared) starting vertex and clearly list the candidate edges and the chosen edge at every step.

六、Dijkstra 算法：单源最短路径的标号法 | Dijkstra’s Algorithm: The Labelling Method for Shortest Paths

最小生成树解决的是”用最小总代价把大家连起来”，而 Dijkstra 算法解决的是另一个问题：”从一个指定的起点，到图中每一个顶点的最短路径是多长”。这在现实里对应着导航软件、物流调度、网络路由等场景。Dijkstra 只适用于”边权非负”的网络（这也是 D1 考试中的默认情形），并且要求网络通常是无向的或者已被处理成合适的形式。

The MST problem answers “how to connect everyone at minimum total cost”, whereas Dijkstra’s algorithm answers a different question: “from one specified start vertex, what is the shortest path to every other vertex in the graph?” In real life this corresponds to navigation software, logistics scheduling and network routing. Dijkstra only applies to networks with non-negative edge weights (the default situation in D1 exams), and the network is usually undirected or already prepared into a suitable form.

Dijkstra 的核心是”标号”（labelling）。每个顶点都会得到一个标签，形如 (距离, 前驱顶点)，表示”目前已知的、从起点到达该顶点的最短距离，以及这条最短路径上紧邻它的前一个顶点”。算法开始时，起点被标为 (0, −)，其余所有顶点被标为”暂时无穷大”。然后重复”松弛”（relax）过程：每次从未确定（temporary）的顶点中选出距离最小的一个，把它变成确定（permanent），再检查通过它能否让它的邻居获得更短的距离，如果能，就更新邻居的标签。

The heart of Dijkstra is labelling. Each vertex receives a label of the form (distance, previous vertex), meaning “the shortest distance currently known from the start to this vertex, together with the vertex immediately before it on that path”. At the start, the source vertex is labelled (0, −) and every other vertex is labelled “temporarily infinite”. Then the relaxation process repeats: each time, among the temporary vertices choose the one with the smallest distance and make it permanent; then check whether travelling through it can give its neighbours a shorter distance, and if so, update those neighbours’ labels.

我们用一个例子完整地走一遍。考虑网络：A 为起点，边为 AB = 4，AC = 2，BC = 1，BD = 5，CD = 8，CE = 10，DE = 2，其中 A、B、C、D、E 为顶点。初始标签：A(0, −)，其余均为 (∞, −)。第一步，把 A 确定为永久，松弛 A 的邻居：B 变为 (4, A)，C 变为 (2, A)。第二步，未确定顶点中距离最小的是 C(2)，把 C 永久化，松弛 C 的邻居：通过 C 到 B 的距离为 2 + 1 = 3，比 B 当前的 4 更小，所以 B 更新为 (3, C)；通过 C 到 D 为 2 + 8 = 10，D 更新为 (10, C)；通过 C 到 E 为 2 + 10 = 12，E 更新为 (12, C)。

Let us walk through an example fully. Consider a network with A as the source, and edges AB = 4, AC = 2, BC = 1, BD = 5, CD = 8, CE = 10, DE = 2, with vertices A, B, C, D, E. Initial labels: A(0, −), all others (∞, −). Step 1, make A permanent and relax A’s neighbours: B becomes (4, A) and C becomes (2, A). Step 2, among temporary vertices the smallest distance is C(2), so make C permanent and relax C’s neighbours: via C the distance to B is 2 + 1 = 3, smaller than B’s current 4, so B updates to (3, C); via C to D is 2 + 8 = 10, so D updates to (10, C); via C to E is 2 + 10 = 12, so E updates to (12, C).

第三步，未确定顶点中最小的是 B(3)，把 B 永久化，松弛 B 的邻居：通过 B 到 D 为 3 + 5 = 8，比 D 当前的 10 更小，D 更新为 (8, B)。第四步，最小的是 D(8)，把 D 永久化，松弛 D 的邻居：通过 D 到 E 为 8 + 2 = 10，比 E 当前的 12 更小，E 更新为 (10, D)。第五步，只剩 E(10)，把 E 永久化。算法结束。最终最短距离：A=0，C=2，B=3，D=8，E=10。

Step 3, the smallest temporary vertex is B(3), so make B permanent and relax B’s neighbours: via B to D is 3 + 5 = 8, smaller than D’s current 10, so D updates to (8, B). Step 4, the smallest is D(8), so make D permanent and relax D’s neighbours: via D to E is 8 + 2 = 10, smaller than E’s current 12, so E updates to (10, D). Step 5, only E(10) remains, so make E permanent. The algorithm ends. Final shortest distances: A = 0, C = 2, B = 3, D = 8, E = 10.

要还原某条最短路径本身，只需从目标顶点沿着”前驱”标签一路回溯到起点。例如 E 的最短路径：E 的前驱是 D，D 的前驱是 B，B 的前驱是 C，C 的前驱是 A，所以 A 到 E 的最短路径是 A → C → B → D → E，总长 10。回溯时要特别注意标签的前驱字段是否在后面的松弛中已被更新，必须用最终的标签来回溯。

To recover the actual shortest path, simply trace back from the target vertex through the “previous vertex” labels to the source. For example, the shortest path to E: E’s previous is D, D’s previous is B, B’s previous is C, C’s previous is A, so the shortest path from A to E is A → C → B → D → E with total length 10. When tracing back, be careful that a label’s previous-vertex field may have been updated by later relaxations; you must trace using the final labels.

七、三种算法的对比与考试易错点 | Comparing the Three Algorithms and Common Exam Pitfalls

把三个算法放在一起对比，能帮你更清楚地记住它们各自的适用场景。Kruskal 和 Prim 都属于”求最小生成树”，目标是连通所有顶点且总权最小，最终得到 n − 1 条边、无回路；而 Dijkstra 属于”求最短路径”，目标是给出从单个起点到每个顶点的最短距离，结果不是树而是一组”距离 + 前驱”标签。用错算法是 D1 最常见的失分原因之一。

Placing the three algorithms side by side helps you remember when to use each. Kruskal and Prim both solve the MST problem: the goal is to connect all vertices at minimum total weight, producing n − 1 edges with no cycles. Dijkstra, by contrast, solves the shortest-path problem: the goal is the shortest distance from a single source to every vertex, and the result is not a tree but a set of “distance + previous” labels. Using the wrong algorithm is one of the most common causes of lost marks in D1.

维度 Aspect	Kruskal	Prim	Dijkstra
目标 Goal	最小生成树 MST	最小生成树 MST	单源最短路径 Shortest path
起点 Start	不需要 Not needed	任选或指定 Any or specified	指定起点 Specified source
输出 Output	n − 1 条边 n − 1 edges	n − 1 条边 n − 1 edges	距离 + 前驱标签 Labels
关键操作 Key action	先排序再选边 Sort then pick	从树内向外选最小边 Grow outward	永久化 + 松弛 Permanent + relax
限制 Constraint	不得形成回路 No cycle	不得形成回路 No cycle	边权非负 Non-negative weights

考试中还有几个高频易错点需要特别注意。第一，Kruskal 里排序一定要”从小到大完整列出”，漏掉排序列表会被扣方法分；拒绝边的理由必须写”形成回路”（would form a cycle），不能只写”跳过”。第二，Prim 里每一步都要写清楚”当前候选边有哪些、选了哪条”，否则过程分拿不全；如果题目指定了起始顶点，一定要从它开始。第三，Dijkstra 里”永久化”和”松弛”两个动作不能混在一起，必须先把距离最小的顶点永久化，再更新它的邻居；更新邻居时，只有得到”更小”的距离才改标签，相等或更大都不改。

There are several high-frequency pitfalls to watch in exams. First, in Kruskal you must write the full sorted list in ascending order; omitting it loses method marks. The reason for a rejected edge must be “would form a cycle”, not just “skip”. Second, in Prim you must state clearly at every step which candidate edges exist and which one was chosen, otherwise you lose process marks; if the question specifies a starting vertex, start from it. Third, in Dijkstra “making permanent” and “relaxing” must not be mixed: you must first make permanent the vertex with the smallest distance, then update its neighbours; when updating, change a label only if you obtain a strictly smaller distance, not when it is equal or larger.

还有一个非常实用的检查技巧：无论哪种图论算法，做完后都花十秒钟做一遍”合理性检查”。最小生成树检查边数是否等于 n − 1、是否连通、是否无回路；Dijkstra 检查每个顶点的最终距离是否小于或等于任何”绕路”得到的距离（三角形不等式）。这些检查往往能在一眼之间发现漏选边、误选边或者标号顺序错误，是考场上的最后一道防线。

One more very useful checking technique: after any graph algorithm, spend ten seconds on a sanity check. For the MST, check that the edge count equals n − 1, that it is connected, and that it is cycle-free. For Dijkstra, check that every vertex’s final distance is at most the distance obtained by any detour (the triangle inequality). These checks often spot a missing edge, a wrongly chosen edge, or an out-of-order labelling at a glance, serving as a final line of defence in the exam room.

Summary | 总结

决策数学 D1 的核心是”算法思维”，而图论算法是其中最具考试价值的部分。本文从”图与网络”的基本概念（顶点、边、权、树、度）出发，系统讲解了三类核心算法：Kruskal 算法通过”先排序、再选边、拒绝回路”求最小生成树；Prim 算法通过”从单点向外生长”求同一个最小生成树；Dijkstra 算法通过”永久化 + 松弛”的标号法求单源最短路径。三者虽然都作用于带权网络，但目标和输出完全不同，切不可混用。

The core of Decision Mathematics D1 is algorithmic thinking, and graph algorithms are its most exam-worthy part. Starting from the basic concepts of graphs and networks (vertices, edges, weights, trees, degree), this article systematically covered three core algorithms: Kruskal’s algorithm finds the MST by “sorting first, picking edges, and rejecting cycles”; Prim’s algorithm finds the same MST by “growing outward from a single vertex”; Dijkstra’s algorithm finds single-source shortest paths by the “permanent + relax” labelling method. Although all three operate on weighted networks, their goals and outputs are completely different and must never be confused.

掌握这三个算法，要点在于”过程”而非”结果”：在 Edexcel 的评分标准里，排序列表、候选边、拒绝理由、标号顺序都是方法分的来源。最后请记住几条硬性检查：最小生成树必须恰好有 n − 1 条边、连通且无回路；Dijkstra 只适用于边权非负的网络，回溯最短路径必须使用最终的”前驱”标签。把这些规则内化，图论算法题就能从”容易扣分的陷阱”变成”稳定拿分的板块”。

The key to mastering these three algorithms is process rather than result: in the Edexcel mark scheme, the sorted list, candidate edges, rejection reasons and labelling order are all sources of method marks. Finally, remember a few hard checks: an MST must have exactly n − 1 edges, be connected and be cycle-free; Dijkstra applies only to networks with non-negative edge weights, and tracing the shortest path must use the final “previous” labels. Once you internalise these rules, graph-algorithm questions change from “traps that easily lose marks” into “sections where marks come steadily.”

---

更多咨询请联系16621398022（同微信）