In Edexcel A-Level Decision Mathematics, linear programming is used to find the best possible outcome, such as maximum profit or minimum cost, when resources are limited. ‘Locating the optimal point’ means identifying the exact coordinates in the feasible region where the objective function takes its optimum value. This article explains both the objective line sliding method and the vertex testing method, with worked examples and exam tips.
A linear programming problem involves decision variables, an objective function, and a set of linear constraints. The objective function is the expression we aim to maximise or minimise, such as profit P = 3x + 2y. The constraints are linear inequalities that represent limited resources, and non-negativity restrictions x ≥ 0, y ≥ 0 are usually assumed.
线性规划问题包含决策变量、目标函数和一组线性约束条件。目标函数是我们要最大化或最小化的表达式，例如利润 P = 3x + 2y。约束条件表示有限资源的线性不等式，通常还假设非负限制 x ≥ 0, y ≥ 0。
In Edexcel questions, the variables often stand for numbers of products or amounts of materials, so the final answer must make practical sense. You may be asked to find the optimal point, state the optimal value, or adjust the objective function to test different scenarios.
Each linear constraint defines a half-plane. For example, x + y ≤ 10 includes every point on one side of the line x + y = 10. The feasible region is the intersection of all these half-planes. It is the set of all points that satisfy every constraint simultaneously.
每个线性约束定义了一个半平面。例如，x + y ≤ 10 包含直线 x + y = 10 一侧的所有点。可行域是所有半平面的交集，即同时满足所有约束条件的点的集合。
When drawing the feasible region, shade out excluded areas or clearly label the allowed side. In a well-posed problem, the feasible region is a convex polygon. Its vertices, also called corner points, are essential because the optimal value is found at one of them for a linear objective function.
3. Objective Function and Objective Line | 目标函数与目标线
Suppose the objective is to maximise P = ax + by. For a fixed value c, the line ax + by = c is called an objective line or profit line. Every point on this line gives the same value P = c. Different values of c produce parallel objective lines with the same gradient.
假设目标是最大化 P = ax + by。对于某个固定值 c，直线 ax + by = c 称为目标线或利润线。该线上每个点都给出相同的 P = c 值。不同的 c 值产生平行且梯度相同的目标线。
Objective line: ax + by = c
目标线：ax + by = c
The gradient of the objective line is -a/b (provided b ≠ 0). This gradient controls the direction in which the line slides as the objective value increases or decreases.
目标线的梯度为 -a/b（假设 b ≠ 0）。该梯度决定了随着目标值增大或减小，直线平移的方向。
4. The Vertex Theorem | 顶点定理
If the feasible region is bounded, the fundamental theorem of linear programming states that the maximum and minimum values
Published by TutorHao | A-Level Revision Series | aleveler.com
In Edexcel A-Level Pure Mathematics, Chapter 6 covers circles in the coordinate plane. You are expected to find the centre and radius, write equations in standard and general form, and solve problems involving tangents, chords, and intersections with lines or other circles.
The equation of a circle with centre (a, b) and radius r is:
圆心在 (a, b)、半径为 r 的圆的方程是：
(x – a)² + (y – b)² = r²
If the circle is centred at the origin, this simplifies to x² + y² = r². The radius must be positive, and the right-hand side is r², so the left-hand side cannot be negative for points on the circle.
You should be able to write the standard equation directly when given the centre and radius. For example, a circle with centre (-2, 5) and radius 4 has equation (x + 2)² + (y – 5)² = 16.
2. General Form and Identifying Centre and Radius | 一般式与识别圆心和半径
The expanded general form of a circle is:
圆的一般式展开为：
x² + y² + 2gx + 2fy + c = 0
Comparing with the standard form (x – a)² + (y – b)² = r² gives centre (-g, -f) and radius √(g² + f² – c). The expression g² + f² – c must be positive for a real circle; if it equals zero, the circle degenerates to a point.
To convert a general circle equation into standard form, complete the square for the x terms and the y terms separately. This is the most reliable way to find the centre and radius from a general form.
Be careful: the constant term moves to the right-hand side, and you must add the same values within the brackets to both sides of the equation to keep it balanced.
注意：常数项移到右边，配方时在括号内加上的值必须同时加到方程两边以保持平衡。
4. Intersections with a Line | 与直线的交点
To find where a line intersects a circle, substitute the line equation y = mx + c into the circle equation. This produces a quadratic in x, which can be solved using factorisation, the quadratic formula, or the discriminant.
要求直线与圆的交点，将直线方程 y = mx + c 代入圆的方程，得到关于 x 的一元二次方程。可以使用因式分解、求根公式或判别式求解。
If the discriminant is positive, there are two intersections; if it is zero, the line is a tangent; if it is negative, the line misses the circle. This discriminant test is often used to show tangency.
Example: Determine whether y = x + 1 intersects x² + y² = 5. Substitute: x² + (x + 1)² = 5 → 2x² + 2x – 4 = 0 → x² + x – 2 = 0, so x = 1 or x = -2, giving two points of intersection.
例如：判断 y = x + 1 是否与 x² + y² = 5 相交。代入得 x² + (x + 1)² = 5 → 2x² + 2x – 4 = 0 → x² + x – 2 = 0，所以 x = 1 或 x = -2，得到两个交点。
5. Tangents to a Circle | 圆的切线
A tangent to a circle touches the circle at exactly one point. The tangent is perpendicular to the radius at the point of contact. This perpendicular relationship is central to most tangent questions.
圆的切线在圆上恰好接触一点。切线在切点处垂直于半径。这个垂直关系是大多数切线问题的核心。
If the gradient of the radius to point P is m_r, then the gradient of the tangent at P is m_t = -1/m_r, provided m_r ≠ 0. If the radius is vertical, the tangent is horizontal.
如果半径到点 P 的斜率为 m_r，那么 P 点切线的斜率为 m_t = -1/m_r，前提是 m_r ≠ 0。如果半径是竖直的，切线就是水平的。
To find the tangent equation, use the point-slope form y – y₁ = m_t(x – x₁). You may also need to prove a line is tangent by showing the perpendicular distance from the centre equals the radius, or by showing the discriminant is zero.
求切线方程时，使用点斜式 y – y₁ = m_t(x – x₁)。你可能还需要通过证明圆心到直线的垂直距离等于半径，或证明判别式为零，来证明一条直线是切线。
6. Chord and Perpendicular Bisector | 弦与垂直平分线
A chord is a line segment joining two points on a circle. The perpendicular bisector of any chord passes through the centre of the circle. This property is extremely useful for locating the centre when only a chord is known.
弦是圆上两点之间的线段。任何弦的垂直平分线都经过圆心。这个性质在已知一条弦而求圆心时非常有用。
If you know the midpoint of a chord and its gradient, the line through the centre is perpendicular to the chord. You can use this to find the centre or to write an equation the centre must satisfy.
The shortest distance from the centre to a chord is the perpendicular distance, and this distance d, the chord length L, and the radius r are related by r² = d² + (L/2)². This is Pythagoras applied to half of the chord.
圆心到弦的最短距离是垂直距离，该距离 d、弦长 L 和半径 r 满足 r² = d² + (L/2)²。这就是把勾股定理应用于半弦得到的。
7. Equation of a Chord and Circle Problems | 弦与圆问题
To find the equation of a chord given two points on the circle, use the midpoint and gradient formula. Alternatively, if the chord is defined by an intersection, solve the line and circle equations simultaneously.
如果已知圆上两点，求弦的方程可以使用中点和斜率公式。如果弦由交点定义，则联立直线与圆的方程求解。
Example: The chord through A(1, 2) and B(5, 6) has midpoint (3, 4) and gradient (6 – 2)/(5 – 1) = 1. Its perpendicular bisector has gradient -1 and passes through (3, 4), so its equation is y – 4 = -1(x – 3).
If this chord belongs to a circle, the centre must lie on the line y = -x + 7. This is often the key step in finding the circle’s equation from a chord and one other condition.
如果这条弦属于某个圆，圆心必定在直线 y = -x + 7 上。这往往是已知一条弦和另一个条件求圆的方程时的关键步骤。
8. Intersection of Two Circles | 两圆的交点
To find the common points of two circles, subtract one equation from the other to eliminate the x² and y² terms. This gives a linear equation, which often represents the common chord, also called the radical axis.
Then solve this line with one of the circle equations to find the intersection points, if any exist. If the distance between centres is greater than the sum of radii, the circles do not intersect.
然后将该直线与其中一个圆的方程联立求解，得到交点（如果有）。如果圆心距大于半径之和，两个圆不相交。
Example: Circle C₁: x² + y² = 25 and C₂: (x – 4)² + y² = 9. Subtract: (x – 4)² – x² = -16 → -8x + 16 = -16 → x = 4. Then y² = 25 – 16 = 9, so points (4, 3) and (4, -3).
Linear programming (LP) is a mathematical technique used to find the best outcome, such as maximum profit or minimum cost, in a model whose requirements are represented by linear relationships. In A-Level Computer Science, LP appears as an optimisation problem that can be solved algorithmically, often using graphical methods for two variables or more general iterative methods such as the simplex algorithm.
Linear programming deals with optimising a linear objective function subject to a set of linear constraints. The key components are decision variables, an objective function, constraints, and non-negativity restrictions.
Decision variables are the quantities we control, such as the number of units to produce or the amount of a resource to use.
决策变量是我们控制的量，例如要生产的单位数量或要使用的资源数量。
The objective function is the expression to maximise or minimise, such as total profit or total cost.
目标函数是要最大化或最小化的表达式，例如总利润或总成本。
Constraints are linear inequalities or equalities that limit the values of the variables. Non-negativity means that variables cannot be negative in most real-world problems.
约束条件是限制变量取值的线性不等式或等式。非负性表示在大多数实际问题中变量不能为负。
2. Formulating an LP problem | 建立线性规划问题模型
To formulate an LP problem, first identify the decision variables, then write the objective function, and finally express each constraint as a linear inequality or equation.
要建立线性规划模型，首先确定决策变量，然后写出目标函数，最后将每个约束表示为线性不等式或方程。
For example, a company makes two products X and Y. Product X earns £3 profit per unit and product Y earns £2 per unit. Machine time limits production: each X needs 2 hours, each Y needs 1 hour, and only 16 hours are available. Packaging requires 1 hour for X and 2 hours for Y, with only 16 hours available.
例如，一家公司生产两种产品 X 和 Y。产品 X 每单位赚取 3 英镑利润，产品 Y 每单位赚取 2 英镑。机器时间限制生产：每个 X 需要 2 小时，每个 Y 需要 1 小时，只有 16 小时可用。包装需要 X 1 小时，Y 2 小时，只有 16 小时可用。
Let x be the number of units of X and y be the number of units of Y. The model is written as:
设 x 为 X 的单位数量，y 为 Y 的单位数量。模型写为：
Maximise P = 3x + 2y Subject to: 2x + y ≤ 16 x + 2y ≤ 16 x ≥ 0, y ≥ 0
Here P is the total profit, and the inequalities represent the machine and packaging time limits.
这里 P 是总利润，不等式表示机器和包装时间限制。
3. Graphical method for two variables | 两变量图解法
For two decision variables, the constraints can be drawn as straight lines on a coordinate plane. The region that satisfies all constraints is called the feasible region.
对于两个决策变量，约束可以在坐标平面上画成直线。满足所有约束的区域称为可行域。
To draw the feasible region, first draw each constraint line. Then determine which side of each line satisfies the inequality by testing a point such as (0, 0). Shade the region that satisfies all inequalities simultaneously.
The corner points of the feasible region are critical because the optimal solution will occur at one of these vertices. Label the axes and the constraint lines clearly.
可行域的角点非常关键，因为最优解将出现在其中一个顶点处。需要清楚地标记坐标轴和约束直线。
4. Feasible region and optimal solution | 可行域与最优解
The optimal solution, if it exists, lies at a vertex of the feasible region. To find it, evaluate the objective function at each vertex and select the maximum or minimum value.
如果存在最优解，它位于可行域的顶点。为了找到它，在每个顶点处计算目标函数值，并选择最大值或最小值。
For the model above, the feasible region has vertices at (0, 0), (8, 0), (0, 8), and (16/3, 16/3). The objective values are shown in the table:
The maximum profit is 80/3, achieved at x = 16/3 and y = 16/3. If the problem requires integer answers, rounding is not enough because the solution must remain feasible.
最大利润为 80/3，在 x = 16/3 和 y = 16/3 处取得。如果问题要求整数答案，仅四舍五入是不够的，因为解必须保持可行。
5. Standard form and slack variables | 标准形式与松弛变量
To solve larger LP problems computationally, inequalities are converted into equations by adding slack variables. A slack variable represents unused resources.
为了用计算机求解更大的线性规划问题，通过添加松弛变量将不等式转换为方程。松弛变量表示未使用的资源。
For example, the constraint 2x + y ≤ 16 becomes 2x + y + s₁ = 16, where s₁ ≥ 0. Likewise, x + 2y ≤ 16 becomes x + 2y + s₂ = 16, where s₂ ≥ 0.
Introducing slack variables transforms the problem into a set of linear equations, which is easier for algorithms such as the simplex method to process.
引入松弛变量将问题转化为一组线性方程，这更容易被单纯形法等算法处理。
6. Introduction to the simplex method | 单纯形法简介
The simplex method is an iterative algorithm that moves from one vertex of the feasible region to an adjacent vertex, improving the objective value until the optimum is reached.
单纯形法是一种迭代算法，从可行域的一个顶点移动到相邻顶点，不断改进目标值，直到达到最优。
The method starts by creating an initial simplex tableau. It then identifies a pivot column from the most negative indicator in the bottom row for a maximisation problem. The pivot row is chosen using the minimum ratio test, and row operations are performed to update the tableau.
These steps repeat until all entries in the bottom row are non-negative. At that point, the basic variables give the optimal solution.
重复这些步骤，直到底部行中所有条目均为非负。此时，基变量给出最优解。
7. Computational thinking and algorithms | 计算思维与算法实现
In computer science, LP problems are solved by encoding the model into a program. Key computational thinking skills include abstraction, decomposition, pattern recognition, and algorithm design.
Abstraction removes unnecessary detail and keeps only the objective function, constraints, and variables. Decomposition breaks the problem into smaller parts such as entering variable selection, leaving variable selection, and pivoting.
The core loop of a simplex-based solver can be described as:
基于单纯形法的求解器的核心循环可以描述为：
WHILE optimal not reached SELECT entering variable SELECT leaving variable by minimum ratio test PIVOT END WHILE
This algorithmic view shows that linear programming is not only a mathematical tool but also a computational problem that can be implemented efficiently.
这种算法视角表明，线性规划不仅是一种数学工具，而且是一个可以有效实现的计算问题。
8. Using Python to solve LP | 使用 Python 求解线性规划
Libraries such as SciPy provide linprog for solving linear programming problems. A typical implementation defines the coefficients of the objective function, the constraint matrix, and the bounds of the variables.
The linprog function minimises c·x subject to A_ub x ≤ b_ub and x ≥ bounds. For a maximisation problem, we must convert it by negating the objective function, because linprog minimises
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
In Edexcel A Level Decision Mathematics, early and late event times are central to critical path analysis. They allow you to determine how soon each stage of a project can begin and how late it can be left without delaying the whole project.
在 Edexcel A Level 决策数学中，最早与最晚事件时间是关键路径分析的核心。它们帮助你确定项目每个阶段最早可以何时开始，以及最晚可以推迟到何时而不延误整个项目。
1. Activity Networks: Events and Activities | 活动网络：事件与活动
In an activity-on-arc network, every node represents an event: a point in time when one or more activities finish and the next ones may begin. Arcs represent activities with fixed durations. The event at the tail of an arc must occur before that activity can start; the event at the head occurs only when all incoming activities are complete.
The earliest event time (EET) is the soonest possible time at which an event can be reached, given the durations and dependencies. The latest event time (LET) is the latest time an event can occur without delaying the overall project. Neither is a duration; both are clock times measured from the project start.
The forward pass starts at the source node with EET = 0. For any other node j, consider every activity (i, j) entering j. Add its duration d(i,j) to EET(i). The earliest time for j is the maximum of these sums, because j cannot occur until all incoming activities have finished.
The backward pass starts at the sink node. Set its LET equal to the project duration, normally the EET of the sink. For any node i, consider every activity (i, j) leaving i. Subtract its duration from LET(j). The latest time for i is the minimum of these differences, because if i occurs any later, at least one following activity will overrun.
逆向计算从汇节点开始。将汇节点的 LET 设为项目总工期，通常等于该节点的 EET。对于任何节点 i，考虑所有离开 i 的活动 (i, j)，用 LET(j) 减去活动工期。节点 i 的最晚时间是这些差值的最小值，因为如果 i 再晚发生，至少一个后续活动会超期。
LET(i) = min { LET(j) − d(i,j) : (i,j) leaves i }
If a question imposes a later target completion time, set LET(sink) equal to that target time instead of the earliest project duration. This changes the floats but not the forward pass values.
5. Notation, Source, Sink and Dummy Activities | 符号、源节点、汇节点与虚活动
Edexcel questions often number events 1, 2, 3, … with the source as the lowest number and the sink as the highest. A dummy activity has zero duration and is shown as a dashed arc; it represents a logical dependency only. In forward and backward passes, dummies are treated like any other activity with d = 0.
Edexcel 题目通常将事件编号为 1、2、3……，源节点编号最小，汇节点编号最大。虚活动的工期为 0，用虚线弧表示；它只表示逻辑依赖关系。在正向和逆向计算中，虚活动与 d = 0 的普通活动一样处理。
6. Worked Example: Activity Data | 示例：活动数据
The table below gives a small project. We will build the network, compute EETs, LETs, and identify the critical path. Activities are labelled A to F, with durations and immediate predecessors.
下表给出一个小型项目。我们将构建网络，计算 EET 和 LET，并确定关键路径。活动用 A 到 F 标注，并给出工期和紧前活动。
Activity
Duration (days)
Must follow
<
Published by TutorHao | A-Level Revision Series | aleveler.com
In critical path analysis, the float of an activity measures how much the activity can be delayed without affecting the project completion time or the start of subsequent activities. Understanding float is essential for identifying the critical path and for efficient resource scheduling.
Float, sometimes called slack, is the amount of time by which an activity can be delayed beyond its earliest start time without causing a delay to the project or to dependent activities.
浮动时间（有时称为时差）是指活动可以比其最早开始时间延迟多久，而不会导致项目或依赖活动延迟。
There are three types of float: total float, free float and independent float. Each gives a different level of flexibility.
浮动时间有三种类型：总时差、自由时差和独立时差。每种类型给出不同层次的灵活性。
An activity with zero total float lies on the critical path.
总时差为零的活动位于关键路径上。
2. Key Times in Critical Path Analysis | 关键路径分析中的关键时间
To calculate float, you must first find the earliest start time (EST), earliest finish time (EFT), latest start time (LST) and latest finish time (LFT) for each activity.
EST is the soonest an activity can begin once all predecessors are complete. EFT = EST + duration.
EST 是所有前置活动完成后该活动可以开始的最早时间。EFT = EST + 持续时间。
LFT is the latest an activity can finish without delaying the project. LST = LFT − duration.
LFT 是在不延迟项目的前提下该活动可以完成的最晚时间。LST = LFT − 持续时间。
These four times are obtained from a forward pass and a backward pass through the activity network.
这四个时间通过对活动网络进行正推和逆推得到。
3. Total Float: Definition and Formula | 总时差：定义与公式
Total float is the maximum amount of time an activity can be delayed without delaying the whole project.
总时差是活动可以延迟的最大时间量，而不会延迟整个项目。
It is calculated using: Total Float = LFT − EFT, or equivalently Total Float = LST − EST.
计算公式为：总时差 = LFT − EFT，或等价地总时差 = LST − EST。
Both expressions always give the same value because EFT = EST + duration and LFT = LST + duration.
两种表达式总是给出相同的结果，因为 EFT = EST + 持续时间，LFT = LST + 持续时间。
If an activity has total float of 5 days, it can be delayed by up to 5 days without affecting the project finish date.
如果一项活动的总时差为5天，那么它可以延迟最多5天而不影响项目完成日期。
4. Interpreting Total Float | 解释总时差
Total float is shared with other activities on the same non-critical chain. Using all the float on one activity may reduce the float available for later activities.
A positive total float means the activity is not on the critical path. A zero total float means the activity is critical.
总时差为正意味着该活动不在关键路径上。总时差为零意味着该活动是关键活动。
In some exam questions, total float can be negative if a deadline is earlier than the current earliest finish; however, for standard project networks it is usually zero or positive.
Unlike total float, free float belongs to the activity itself and is not shared with other activities.
与总时差不同，自由时差属于活动本身，不与其他活动共享。
Free float can never exceed total float; it is often zero even when total float is positive.
自由时差永远不超过总时差；即使总时差为正，自由时差也常常为零。
6. Independent Float: Definition and Formula | 独立时差：定义与公式
Independent float is the amount of time an activity can be delayed regardless of the timing of preceding and following activities.
独立时差是指无论前置活动和后续活动的时间安排如何，活动都可以延迟的时间量。
It is calculated using: Independent Float = EST(next activity) − LFT(previous activity) − duration.
计算公式为：独立时差 = 紧后活动的 EST − 紧前活动的 LFT − 持续时间。
If this expression is negative, the independent float is taken as zero, because negative float has no practical meaning for a single activity.
如果该表达式为负，独立时差取为零，因为负时差对单个活动没有实际意义。
Independent float is the most conservative measure and is rarely used in basic scheduling decisions, but exam boards may ask for it.
独立时差是最保守的度量，在基本调度决策中很少使用，但考试局可能会要求计算它。
7. Calculating Float from a Precedence Table | 从优先关系表计算时差
A precedence table lists activities, their durations and immediate predecessors. Use it to build the activity network, then carry out forward and backward passes.
优先关系表列出活动、持续时间及紧前活动。用它构建活动网络，然后进行正推和逆推。
Record EST, EFT, LST, LFT in a table. Then apply the float formulas to each activity.
在表格中记录 EST、EFT、LST、LFT。然后对每项活动应用时差公式。
For example, if activity B has duration 4, EST 6, EFT 10, LST 9, LFT 13, then total float = 13 − 10 = 3 days.
Always show your workings clearly, as method marks are awarded in Edexcel Decision Mathematics.
务必清晰展示计算步骤，因为 Edexcel 决策数学中会给予方法分。
8. Float and the Critical Path | 时差与关键路径
The critical path is the longest path through the network. All activities on this path have zero total float.
关键路径是穿过网络的最长路径。该路径上的所有活动总时差为零。
Therefore, total float is a quick way to confirm the critical activities: if total float = 0, the activity is critical.
因此，总时差是确认关键活动的快捷方法：如果总时差为零，该活动就是关键活动。
A critical path can be identified by listing all activities with zero total float and checking that they form a continuous chain from start to finish.
关键路径可以通过列出所有总时差为零的活动并检查它们是否形成从开始到结束的连续链来识别。
9. Using Cascade (Gantt) Charts to Show Float | 使用级联图（甘特图）表示时差
A cascade chart, or Gantt chart, displays each activity as a block starting at its earliest start time, with its total float shown as a dotted extension.
级联图（或甘特图）将每项活动显示为从最早开始时间开始的方块，并用虚线延伸表示总时差。
The solid block represents the activity duration, while the dotted line shows the maximum delay possible before the project is affected.
实心方块表示活动持续时间，虚线表示在项目受到影响之前可能的最大延迟。
Exam questions often ask you to draw a cascade chart and shade or label the float clearly.
考题经常要求绘制级联图，并清楚地标记或涂色表示时差。
10. Common Misconceptions and Exam Tips | 常见误区与考试技巧
Misconception 1: total float and free float are the same. They are not; total float may delay the project only when the whole chain is considered, while free float delays only the next activity.
Misconception 2: an activity with zero free float must be critical. This is false; zero free float can happen on non-critical activities if the next activity starts immediately after it.
Project modelling is the process of turning a real-world project into a mathematical network of activities, durations, and precedence constraints. It allows decision mathematicians to calculate the shortest possible completion time, identify which activities cannot slip, and schedule resources efficiently.
A project model uses three building blocks: activities, durations, and precedence relations. Activities are tasks that consume time, durations are their lengths, and precedence relations show which tasks must finish before another can start.
The main outputs in Edexcel Decision Mathematics are the minimum project completion time, the critical path, and the float for every non-critical activity. These outputs come from a network built from a precedence table.
📚 Using the Nearest Neighbour Algorithm to Find an Upper Bound | 使用最近邻算法求上界
In many optimisation problems, especially the travelling salesman problem, we need a quick way to estimate the best possible solution without trying every possible route. The nearest neighbour algorithm is a simple greedy heuristic that constructs a complete Hamiltonian cycle and therefore provides an upper bound for the optimal tour length.
1. The Travelling Salesman Problem and Bounds | 旅行商问题与界限
The travelling salesman problem (TSP) asks for the shortest closed route that visits every vertex exactly once and returns to the starting vertex. This shortest route is called the optimal tour. In a minimisation problem, any feasible route gives an upper bound because the optimal tour cannot be longer than a route we have actually found.
To narrow the search, we often look for a lower bound and an upper bound. If a lower bound is L and an upper bound is U, the optimal tour length T* satisfies L ≤ T* ≤ U.
为了缩小搜索范围，我们通常寻找下界和上界。如果下界为 L，上界为 U，则最优回路长度 T* 满足 L ≤ T* ≤ U。
2. What the Nearest Neighbour Algorithm Does | 最近邻算法做什么
The nearest neighbour algorithm builds a route by a greedy rule: from the current vertex, move to the nearest unvisited vertex. This is repeated until all vertices have been visited, and then the route returns to the starting vertex.
Because the method always chooses the smallest immediate distance, it is fast and easy to apply by hand or program. However, being greedy does not guarantee the global optimum; it only guarantees a valid Hamiltonian cycle.
Once the nearest neighbour process finishes, the output is a closed cycle that visits every vertex exactly once. This is a feasible solution to the travelling salesman problem. Since the optimal tour is the minimum over all feasible Hamiltonian cycles, its length must be less than or equal to the length of this constructed cycle.
Gantt charts are one of the most widely taught planning tools in the Edexcel A-Level Business specification. They help managers schedule tasks, allocate resources and monitor progress over time. Understanding how to construct, interpret and evaluate a Gantt chart is essential for both coursework and examination questions on operations and project management.
A Gantt chart is a horizontal bar chart that represents a project schedule. Each task or activity is shown as a bar positioned along a time axis; the length of the bar indicates the planned duration of that task. The chart is named after Henry Gantt, an American engineer who popularised this visual planning method in the 1910s.
In A-Level Business, Gantt charts are often used in the operations and project management sections. They show the start and finish dates of activities, making it easier to see whether a project is running on schedule.
The main components of a Gantt chart include a task list, a time scale, horizontal task bars, milestones and progress indicators. The task list is usually placed on the left-hand vertical axis, while the time scale runs horizontally across the top or bottom.
Task bars show the planned duration of each activity. Milestones are represented by diamond shapes and mark important deadlines or decision points. Progress indicators may shade a portion of the bar to show how much of the task has been completed.
To construct a Gantt chart, a manager should first list all the activities required to complete the project. The next step is to estimate the duration of each activity and identify the order in which tasks must be completed.
The manager then draws a horizontal time axis, often divided into days, weeks or months. Each activity is represented by a bar starting at its planned start date and ending at its planned finish date. Bars that overlap in time can indicate activities that may be carried out simultaneously.
Finally, milestones can be inserted at key dates, and progress can be shaded as the project develops. For exam answers, a clear, labelled sketch is usually more important than a perfect scale drawing.
Interpreting a Gantt chart involves reading the start and finish dates of each bar, identifying which activities run at the same time and noticing any gaps between tasks. A gap between the end of one task and the start of the next may suggest idle time or a scheduling problem.
The chart can also show the overall project duration from the first task to the last. If a task has spare time built in, this is called float or slack; the task could be delayed without delaying the whole project.
However, a basic Gantt chart does not automatically show the critical path. To identify the critical path, managers often combine the Gantt chart with network diagram information or use software that calculates dependencies and float.
One major advantage of Gantt charts is their visual clarity. The bars make it easy for managers, employees and other stakeholders to understand the project schedule at a glance, even without specialist project management training.
Gantt charts also support resource planning. By seeing when tasks are scheduled, a manager can identify periods of high workload and move tasks or allocate extra staff to avoid bottlenecks.
They are useful for monitoring progress. By comparing the shaded portion of each bar with the current date, managers can quickly spot tasks that are behind schedule and take corrective action.
In addition, Gantt charts improve communication within teams. They provide a shared visual reference for deadlines, milestones and responsibilities, which can reduce misunderstandings and coordination failures.
Despite their benefits, Gantt charts have several limitations. For very large or complex projects with hundreds of tasks, the chart can become extremely long and difficult to read on a single page.
A basic Gantt chart does not clearly show the logical dependencies between tasks unless arrows or links are added. Without this information, managers may not fully understand how a delay in one activity affects related activities.
Gantt charts also require regular updating. If the chart is not revised as actual progress changes, it becomes outdated and may mislead decision-makers into thinking the project is still on track.
Furthermore, the chart focuses mainly on time and does not directly show costs, quality issues or cash flow implications. Managers therefore need to use it alongside other planning and control tools, such as budgets and critical path analysis.
Gantt charts and network diagrams are both project planning tools, but they serve different purposes. A network diagram, such as a critical path analysis diagram, emphasises the logical sequence and dependencies of activities, while a Gantt chart emphasises the time schedule and visual timeline.
📚 Critical Activities in Critical Path Analysis | 关键路径分析中的关键活动
In Edexcel A-Level Decision Mathematics, the concept of ‘critical activities’ lies at the heart of project planning and control. Knowing how to identify these activities allows you to determine the shortest possible completion time for a project and to recognise which tasks cannot be delayed without impacting the overall schedule. This article explains the essential theory, calculation methods, and exam techniques for critical activities in critical path analysis.
A project is modelled as a network of activities, where each activity is represented by a node (in activity-on-node notation, which Edexcel uses) or by an edge (in activity-on-arrow notation). Activities are connected by directed edges that show precedence constraints: an activity cannot start until all its immediate predecessors have been completed.
English: Each node typically contains the activity name and its duration.
中文：每个节点通常包含活动名称及其持续时间。
English: A dummy activity may be used in activity-on-arrow networks to represent dependencies, but in activity-on-node notation dummies are not needed.
中文：在活动箭线网络中可能使用虚活动来表示依赖关系，但在活动节点表示法中不需要虚活动。
Understanding the network structure is the first step in finding critical activities, because the timing calculations depend entirely on the precedence relationships and durations.
理解网络结构是寻找关键活动的第一步，因为时间计算完全依赖于先后关系和持续时间。
2. Defining a Critical Activity | 关键活动的定义
A critical activity is an activity for which any delay in its start or finish will cause a delay in the completion of the entire project. In other words, a critical activity has zero total float. Total float is the amount of time an activity can be delayed without affecting the project’s minimum completion time.
Mathematically, an activity is critical if and only if its total float is zero. The chain of critical activities from the start node to the end node forms the critical path.
3. Forward Pass: Earliest Start and Earliest Finish Times | 前向扫描：最早开始与最早完成时间
The forward pass calculates the earliest start time (EST) and earliest finish time (EFT) for each activity. The earliest start time of the first activity is usually set to 0. For any other activity, the EST is the maximum of the EFTs of all its immediate predecessors.
前向扫描计算每个活动的最早开始时间（EST）和最早完成时间（EFT）。第一个活动的最早开始时间通常设为 0。对于任何其他活动，其 EST 是其所有直接前导活动 EFT 的最大值。
EFT = EST + Duration
The project’s minimum completion time is the maximum EFT of all terminal activities (those with no successors).
项目的最短完成时间是所有终止活动（没有后继活动的活动）EFT 的最大值。
4. Backward Pass: Latest Finish and Latest Start Times | 后向扫描：最晚完成与最晚开始时间
The backward pass begins at the terminal activity or activities. The latest finish time (LFT) of a terminal activity is set equal to the project’s minimum completion time. For any other activity, the LFT is the minimum of the LSTs of all its immediate successors.
The latest start time (LST) is therefore the latest time an activity can start without delaying the project.
因此，最晚开始时间（LST）是活动在不延迟项目的前提下可以开始的最晚时间。
5. Calculating Total Float | 计算总浮动时间
Total float (TF) for an activity is the maximum amount of time the activity can be delayed beyond its earliest start without delaying the project completion. It can be calculated in two equivalent ways:
These two differences are always equal for a valid network. If an activity has zero total float, it is critical.
对于一个有效的网络，这两个差值总是相等的。如果一个活动的总浮动时间为零，则它是关键活动。
6. Identifying Critical Activities and the Critical Path | 识别关键活动与关键路径
Once the forward and backward passes are complete, you can identify critical activities by checking which activities have total float equal to zero. The sequence of critical activities forms one or more continuous paths from the start to the end. Every critical path must have the same total duration, equal to the project’s minimum completion time.
In exam questions, you may be asked to state the critical path and its length. Always write the path as a sequence of activity letters, e.g. A → C → E → G, and give the total duration.
在考试题目中，你可能被要求说明关键路径及其长度。始终将路径写为活动字母序列，例如 A → C → E → G，并给出总持续时间。
7. Worked Example: A Simple Project | 示例：一个简单项目
Consider a project with the following activities and durations (in days):
考虑一个具有以下活动和持续时间（以天为单位）的项目：
Activity
Duration
Predecessors
A
3
–
B
4
A
C
2
A
D
5
B, C
E
1
C
F
3
D, E
Perform a forward pass. Set EST(A) = 0, so EFT(A) = 0 + 3 = 3. Then EST(B) = EST(C) = 3. EFT(B) = 3 + 4 = 7; EFT(C) = 3 + 2 = 5. Activity D has predecessors B and C, so EST(D) = max(7,5) = 7, EFT(D) = 7 + 5 = 12. Activity E has predecessor C, so EST(E) = 5, EFT(E) = 5 + 1 = 6. Activity F has predecessors D and E, so EST(F) = max(12,6) = 12, EFT(F) = 12 + 3 = 15. The minimum project completion time is 15 days.
Now perform a backward pass. Set LFT(F) = 15, so LST(F) = 15 − 3 = 12. Activity D has successor F, so LFT(D) = 12, LST(D) = 12 − 5 = 7. Activity E has successor F, so LFT(E) = 12, LST(E) = 12 − 1 = 11. Activity C has successors D and E, so LFT(C) = min(7,11) = 7, LST(C) = 7 − 2 = 5. Activity B has successor D, so LFT(B) = 7, LST(B) = 7 − 4 = 3. Activity A has successors B and C, so LFT(A) = min(3,5) = 3, LST(A) = 3 − 3 = 0.
The critical path is the longest path through the network in terms of total duration. It determines the minimum time needed to complete the project. If any critical activity is delayed by a certain amount of time, the project completion will be delayed by the same amount, unless corrective action is taken.
There may be more than one critical path in a network. When multiple critical paths exist, all of them must have the same total duration. Activities that are on at least one critical path are critical; activities that are on no critical path have positive float and are non-critical.
Students often confuse earliest and latest times, especially in the backward pass. Remember that the backward pass works from the end to the start, and you must take the minimum of successors’ LSTs when calculating an activity’s LFT. A common error is to use the maximum instead.
Another frequent mistake is forgetting that total float can be calculated either as LST − EST or LFT − EFT. Always check both values; if they are not equal, you have made an arithmetical error.
另一个常见错误是忘记总浮动时间可以通过 LST − EST 或 LFT − EFT 计算。始终检查两个值；如果它们不相等，则说明存在算术错误。
When writing the critical path in the exam, always list activities in their correct sequence and include arrows between them. Also, clearly state the total duration, as this is often worth a mark.
10. The Role of Critical Activities in Resource Management | 关键活动在资源管理中的作用
Identifying critical activities is not only an exam skill; it is also essential for real-world project management. Project managers focus most attention on critical activities because any delay in these tasks directly extends the project deadline. Non-critical activities, with their positive float, can be scheduled flexibly within their float windows, allowing for better resource levelling.
If resources are over-allocated, a manager may decide to delay a non-critical activity to reduce peak demand. However, delaying a critical activity is never an option without extending the whole project. Understanding this distinction is a key learning outcome in Decision Mathematics.
To summarise, the steps to find critical activities are:
总结起来，寻找关键活动的步骤是：
English: Draw the activity network using precedence information.
中文：使用先后关系信息绘制活动网络。
English: Perform a forward pass to calculate EST and EFT.
中文：执行前向扫描来计算 EST 和 EFT。
English: Perform a backward pass to calculate LFT and LST.
中文：执行后向扫描来计算 LFT 和 LST。
English: Compute total float for each activity.
中文：计算每个活动的总浮动时间。
English: Identify activities with zero total float as critical.
中文：将总浮动时间为零的活动识别为关键活动。
English: Trace the critical path(s) along these activities.
中文：沿着这些活动追踪关键路径。
Total Float = LST − EST = LFT − EFT
Mastering these calculations unlocks a significant portion of the Edexcel Decision Mathematics examination, and provides a powerful tool for analysing real-life projects.
📚 Dummy Activities in Critical Path Analysis | 关键路径分析中的虚拟活动
In Edexcel A-Level Decision Mathematics 1 (D1), critical path analysis is a vital modelling tool for scheduling complex projects. One of the most frequently examined and commonly misunderstood ideas is the dummy activity. A dummy activity has zero duration and uses no resources, but it is essential for preserving logical dependencies in an activity-on-arc network. This article explains what dummy activities are, when to use them, how to draw them correctly, and how to avoid common mistakes.
In an activity-on-arc network, each real activity is drawn as a solid arrow from one event node to another. A dummy activity is drawn as a dashed arrow and is used only to show a dependency. It has no duration, no cost, and no resource requirement. In Edexcel D1, dummies are mainly needed to ensure that the network correctly represents every precedence relationship without violating the rules of graph drawing.
Dummy activities solve two graphical and logical problems. First, if two or more activities share exactly the same start node and end node, the diagram would have parallel edges with the same endpoint pair, which makes the activities impossible to identify uniquely. Second, when an activity depends on two predecessors but another activity depends on only one of those predecessors, a simple arrow cannot express this partial dependency without introducing a false relationship.
3. The Two Classical Cases for Dummies | 使用虚拟活动的两种经典情形
Case 1: Unique endpoint pair. Suppose activities A and B both start at node 1 and finish at node 2. To separate them, draw A from 1 to 3, draw B from 1 to 2, and insert a dummy from 2 to 3. Now A and B have different end nodes, and the dummy from 2 to 3 means that the event at node 3 depends on B as well; this does not add any time or resource.
情形一：唯一端点对。假设活动 A 和 B 都从节点 1 开始并在节点 2
Published by TutorHao | A-Level Revision Series | aleveler.com
📚 Chapter Review 5: Straight Line Graphs | 第五章复习：直线图
This revision guide covers the key ideas in Edexcel A-Level Pure Mathematics Chapter Review 5: straight line graphs. You will revise gradient, midpoint, distance, equations of lines, parallel and perpendicular conditions, intersections, and modelling.
The gradient of a straight line joining two points is found by dividing the change in y by the change in x. Always subtract the coordinates in the same order.
连接两点的直线斜率用 y 的变化量除以 x 的变化量来计算。两个坐标必须按相同顺序相减。
m = (y₂ − y₁) / (x₂ − x₁)
The midpoint is the point exactly halfway between the two endpoints. Its coordinates are the average of the x-coordinates and the average of the y-coordinates.
中点位于两个端点正中间。它的坐标是 x 坐标的平均值和 y 坐标的平均值。
M = ((x₁ + x₂)/2, (y₁ + y₂)/2)
A positive gradient rises from left to right, while a negative gradient falls. Zero gradient gives a horizontal line, and a vertical line has undefined gradient.
正斜率从左到右上升，负斜率从左到右下降。斜率为零时直线水平，垂直直线的斜率无定义。
2. Equation of a Straight Line | 直线方程
The equation y = mx + c uses m for gradient and c for the y-intercept, which is the point where the line crosses the y-axis.
方程 y = mx + c 中 m 表示斜率，c 表示 y 轴截距，即直线与 y 轴相交的点。
y = mx + c
When you know one point and the gradient, use the point-gradient form y − y₁ = m(x − x₁). You can then rearrange it into the required form.
当已知一个点和斜率时，使用点斜式 y − y₁ = m(x − x₁)。然后可以整理成题目要求的形式。
y − y₁ = m(x − x₁)
To find the equation when given two points, first find the gradient, then
Published by TutorHao | A-Level Revision Series | aleveler.com
📚 Using a Minimum Spanning Tree Method to Find a Lower Bound | 用最小生成树方法求下界
In Edexcel Decision Mathematics 1, the travelling salesperson problem (TSP) asks for the shortest possible tour that visits every vertex exactly once and returns to the start. Finding the exact optimal tour can be time-consuming, so we use upper and lower bounds to narrow down the possible tour length. A lower bound is a value that no valid tour can have a weight below. This article explains how a minimum spanning tree (MST) can be used to construct a reliable lower bound for the TSP.
1. The Travelling Salesperson Problem and Bounds | 旅行商问题与界限
The TSP is a classic optimisation problem. A tour must include every vertex once and return to the starting point, so it forms a Hamiltonian cycle. In a complete graph with n vertices, there are (n − 1)! / 2 possible tours, which makes complete enumeration impractical for large n.
To solve TSP problems in exam conditions, we usually find an upper bound using a heuristic method such as the nearest neighbour algorithm, and a lower bound using the minimum spanning tree method. If the upper bound and lower bound are equal, then the tour used to find the upper bound is provably optimal.
2. Why a Minimum Spanning Tree Gives a Lower Bound | 为什么最小生成树给出下界
Consider any optimal TSP tour. If we delete one vertex from the tour, we also delete the two edges that connect that vertex to its two neighbours in the tour. The remaining edges still connect all the other vertices, and because the original tour was a cycle, removing two edges and one vertex leaves behind a path, which is a special type of tree.
This remaining structure is a spanning tree on the vertices that were not deleted. Its total weight must be at least the weight of the minimum spanning tree (MST) on those vertices. The two deleted edges must have total weight at least the sum of the two shortest possible edges that could connect the deleted vertex back to the graph. Adding these two minimum contributions gives a valid lower bound for the whole tour.
The standard Edexcel D1 method is to choose one vertex, delete it from the graph, and find the MST of the remaining vertices. Then we add the weights of the two smallest edges that were incident to the deleted vertex. The result is a lower bound for the TSP.
This technique works because any TSP tour must enter and leave the deleted vertex exactly once, using two incident edges. The rest of the tour forms a spanning tree on the remaining vertices. Therefore, the tour weight is always greater than or equal to the sum of the MST weight and the two shortest incident edges.
4. Step 1: Choose a Vertex to Delete | 步骤1：选择要删除的顶点
You can choose any vertex to delete, and the method will still produce a lower bound. However, some vertices give better bounds than others. In an exam question, you may be told which vertex to delete, or you may be asked to try several vertices and select the largest lower bound.
Choosing a vertex with relatively large edges to the rest of the graph is often useful because the two shortest edges from it will still be included in the bound. If a vertex has one very small edge, deleting it may produce a weak bound, so repeating the process for other vertices is important.
5. Step 2: Find the MST of the Remaining Vertices | 步骤2：求剩余顶点的最小生成树
After deleting the chosen vertex, apply Kruskal’s algorithm or Prim’s algorithm to the remaining vertices. With Kruskal’s algorithm, list all remaining edges in increasing order of weight, then repeatedly add the smallest edge that does not form a cycle until all remaining vertices are connected.
删除所选顶点后，对剩余顶点应用 Kruskal 算法或 Prim 算法。使用 Kruskal 算法时，按权重递增的顺序列出所有剩余边，然后反复添加不会形成环的最小边，直到所有剩余顶点都连通。
It is essential to use only the edges that do not involve the deleted vertex. The MST weight is the sum of the selected edge weights. A tree on n vertices needs exactly n − 1 edges, so if five vertices remain after deletion, the MST must contain four edges.
必须只使用不涉及被删除顶点的边。MST 权重是所选边权重的总和。n 个顶点上的树恰好需要 n − 1 条边，因此如果删除后剩余五个顶点，则 MST 必须包含四条边。
6. Step 3: Add the Two Shortest Edges to the Deleted Vertex | 步骤3：加上连接到被删除顶点的两条最短边
From the original graph, identify all edges incident to the deleted vertex. Choose the two with the smallest weights. It does not matter whether these two edges share the same endpoint or not, because they simply represent the cheapest possible way to enter and leave the deleted vertex.
The lower bound is then calculated as: Lower bound = MST weight of remaining vertices + weight of shortest incident edge + weight of second shortest incident edge.
7. Worked Example: Finding a Lower Bound | 例题：求一个下界
Consider a complete graph on six vertices A, B, C, D, E, F. The edge weights are shown in the table below. We will delete vertex A and find a lower bound for the TSP.
考虑一个六个顶点 A、B、C、D、E、F 的完全图。边权重如下表所示。我们将删除顶点 A 并求 TSP 的一个下界。
Edge
Weight
Edge
Weight
AB
5
BD
6
AC
7
BE
7
AD
9
BF
5
AE
4
CD
4
AF
6
CE
3
BC
8
CF
9
DE
5
DF
7
EF
6
After deleting vertex A, the remaining vertices are B, C, D, E, F. The edges among these vertices in ascending order of weight are: CE = 3, CD = 4, DE = 5, BF = 5, BD = 6, EF = 6, BE = 7, DF = 7, BC = 8, CF = 9.
Using Kruskal’s algorithm, we select CE = 3 and CD = 4. The next smallest is DE = 5, but adding DE would form the cycle C-D-E, so it is rejected. We then select BF = 5 and BD = 6. At this point we have four edges for five vertices, so the MST is complete. The total MST weight is 3 + 4 + 5 + 6 = 18.
使用 Kruskal 算法，我们选择 CE = 3 和 CD = 4。下一个最小边是 DE = 5，但添加 DE 会形成环 C-D-E，因此被拒绝。接着我们选择 BF = 5 和 BD = 6。此时五个顶点已有四条边，因此 MST 完成。MST 总权重为 3 + 4 + 5 + 6 = 18。
The edges incident to deleted vertex A have weights AB = 5, AC = 7, AD = 9, AE = 4, AF = 6. The two shortest are AE = 4 and AB = 5, with total weight 9.
与被删除顶点 A 关联的边权重为 AB = 5、AC = 7、AD = 9、AE = 4、AF = 6。两条最短边是 AE = 4 和 AB = 5，总权重为 9。
Therefore, the lower bound for this TSP is MST weight 18 + two shortest incident edge weights 9 = 27.
Lower bound = 18 + 4 + 5 = 27
因此，该 TSP 的下界为 MST 权重 18 + 两条最短关联边权重 9 = 27。
8. Improving the Bound by Trying Different Vertices | 尝试不同顶点改进下界
Because the lower bound depends on which vertex is deleted, deleting a different vertex may produce a larger lower bound. A larger lower bound is better because it is closer to the true optimal tour length. You should repeat the MST method for several vertices and record each bound.
For example, deleting vertex B would require finding the MST of A, C, D, E, F and adding the two shortest edges incident to B. The procedure is identical, but the resulting value may be higher or lower than 27. The best lower bound is the maximum of all the bounds found.
例如，删除顶点 B 需要求 A、C、D、E、F 的 MST，并加上与 B 关联的两条最短边。过程完全相同，但得到的值可能高于或低于 27。最佳下界是找到的所有下界中的最大值。
9. Using the Maximum Lower Bound | 使用最大下界
If you have also found an upper bound for the same TSP using a heuristic such as the nearest neighbour algorithm, compare the two values. The maximum lower bound and the minimum upper bound give an interval that must contain the optimal tour length.
If the maximum lower bound equals the minimum upper bound, then that common value is the exact optimal tour weight. In exam problems, this equality often confirms that the tour used for the upper bound is optimal.
One common mistake is to include the deleted vertex in the MST calculation. Remember that the MST is found only on the remaining vertices after deletion. Another error is to add only one edge back to the deleted vertex, but a TSP tour must
Published by TutorHao | A-Level Revision Series | aleveler.com
📚 The Classical and Practical Travelling Salesman Problems | 经典与实用旅行商问题
The travelling salesman problem is one of the most important optimisation problems in decision mathematics. It asks for the cheapest closed route that starts at a given point, visits a set of locations, and returns to the starting point. In the Edexcel specification, the problem is studied in two forms: the classical travelling salesman problem, where every vertex must be visited exactly once, and the practical travelling salesman problem, where repeated visits are allowed because the network may not be complete.
1. What Is the Travelling Salesman Problem? | 什么是旅行商问题？
The travelling salesman problem, often abbreviated as TSP, is a routing problem in a weighted network. A salesperson must leave a home city, visit a list of cities, and return home. The aim is to make the total distance or cost as small as possible.
In Edexcel Decision Mathematics, a solution is called a tour or Hamiltonian cycle if it visits every vertex exactly once and returns to the start. The classical and practical versions differ in how strictly this ‘exactly once’ rule is applied.
2. Classical TSP: Definition and Assumptions | 经典TSP：定义与假设
The classical travelling salesman problem assumes a complete network. This means there is a direct edge between every pair of vertices. Each edge has a known weight, such as distance, time, or cost, and the network is usually undirected and symmetric.
A valid classical tour is a Hamiltonian cycle. It must visit every vertex exactly once and return to the starting vertex. The objective is to find the Hamiltonian cycle with the smallest total weight.
For a complete graph with n vertices, there are (n − 1)! / 2 possible Hamiltonian cycles if the graph is undirected. Checking every cycle quickly becomes impractical, so algorithms such as nearest neighbour and minimum spanning tree bounds are used.
3. Practical TSP: When the Network Is Not Complete | 实用TSP：网络不完整时
In real applications, the network often is not complete. Some pairs of locations may have no direct road or rail link. The practical travelling salesman problem allows the route to travel along any available edges and to visit vertices more than once.
The only requirements are that the route must visit every vertex at least once, return to the starting vertex, and have the smallest possible total weight. A practical route is therefore not necessarily a Hamiltonian cycle.
4. Converting a Practical TSP into a Classical TSP | 将实用TSP转化为经典TSP
A practical travelling salesman problem can be converted into a classical travelling salesman problem by building a complete shortest-distance table. First, use Dijkstra’s algorithm to find the shortest path between every pair of vertices in the original network.
Record these shortest distances in a square table. This table is complete because every pair of vertices now has a value. The shortest distances also satisfy the triangle inequality, which means the direct table value between two vertices is no greater than any indirect route through another vertex.
Once the complete shortest-distance table is formed, solve it as a classical TSP. Each selected edge in the classical tour corresponds to a shortest path in the original practical network, so the route can be translated back.
5. Finding an Upper Bound with the Nearest Neighbour Algorithm | 用最近邻算法求上界
Any valid tour gives an upper bound for the optimal tour length. The nearest neighbour algorithm is a quick constructive method. It starts at a chosen vertex, then repeatedly moves to the nearest unvisited vertex, and finally returns to the start.
The total weight of this tour is an upper bound. Starting from different vertices can produce different tours, so it is useful to try several starting points and take the smallest resulting tour as the best upper bound.
6. Finding a Lower Bound Using a Minimum Spanning Tree | 用最小生成树求下界
A lower bound can be calculated by deleting one vertex, say A. In any Hamiltonian cycle, the part connecting all vertices except A must contain a spanning tree of those remaining vertices. Therefore its weight is at least the weight of the minimum spanning tree, or MST, on the remaining vertices.
The tour must also enter and leave A using two distinct edges. The total weight of these two edges is at least the sum of the two smallest edges incident to A. This gives the formula:
Lower bound = MST weight on V − {A} + two smallest edge weights from A
This value is a lower bound for the optimal classical tour length. For practical TSP, the same calculation is applied to the complete shortest-distance table.
该值是经典最优回路长度的下界。对于实用TSP，同样的计算应用于完全最短距离表。
7. Choosing the Best Lower Bound | 选择最佳下界
Since any vertex can be deleted in the lower bound calculation, you should repeat the process for several different vertices. The largest lower bound obtained is the most useful, because it is closest to the optimal value.
If an upper bound and a lower bound are equal, the corresponding tour is proven optimal. This is an important technique in exam questions that ask you to justify optimality.
如果上界与下界相等，则对应的回路被证明是最优的。这是考试题中要求证明最优性的重要技巧。
8. Worked Example: Classical TSP | 经典TSP例题
Five vertices A, B, C, D, E have the following symmetric distance table in kilometres:
📚 Using a Minimum Spanning Tree Method to Find an Upper Bound | 用最小生成树方法求上界
In the Edexcel A-Level Further Mathematics Decision Mathematics 1 module, the travelling salesman problem requires you to find a short route visiting every vertex exactly once and returning to the start. Since exact methods are often too slow, exam questions ask for upper and lower bounds for the optimal tour length. This article explains how to use a minimum spanning tree method to construct a valid tour and hence obtain an upper bound.
A minimum spanning tree method for an upper bound is used on a complete weighted network, where every pair of vertices is joined by an edge. The goal is to build a Hamiltonian cycle, which is a cycle visiting every vertex exactly once before returning to the start. The total weight of that cycle is an upper bound for the travelling salesman problem because the optimal tour cannot be longer than any feasible tour you find.
2. Key Idea: From MST to Hamiltonian Cycle | 核心思想：从最小生成树到哈密顿回路
First find a minimum spanning tree of the network using Prim’s algorithm or Kruskal’s algorithm. Then traverse this tree in a depth-first search, recording each vertex the first time you visit it. Finally, return directly from the last recorded vertex to the starting vertex. This produces a Hamiltonian cycle using original graph edges, and its length is an upper bound.
首先使用 Prim 算法或 Kruskal 算法找到网络的最小生成树。然后对这个树进行深度优先搜索，记录每个顶点第一次被访问的顺序。最后从最后一个记录的顶点直接返回起点。这样就得到一条使用原图边权的哈密顿回路，其长度即为一个上界。
The method works because a minimum spanning tree connects all vertices cheaply. The depth-first traversal converts that cheap connection structure into an ordered vertex list, and the final direct return closes the cycle. It does not always give the optimal tour, but it always gives a feasible tour.
3. Step 1: Find the Minimum Spanning Tree | 第一步：求最小生成树
Use Kruskal’s algorithm by sorting all edges in ascending order of weight. Add the shortest edge that does not create a cycle. Continue until all vertices are connected and exactly n − 1 edges have been added, where n is the number of vertices. Alternatively, use Prim’s algorithm from a chosen starting vertex.
使用 Kruskal 算法时，将所有边按权值从小到大排序。依次加入不形成回路的最短边。继续这一过程，直到所有顶点都被连接并且恰好加入了 n − 1 条边，其中 n 是顶点数。也可以从选定的起点使用 Prim 算法。
In the worked example below, the vertices are A, B, C, D, E, and the edge weights are shown in the table. Kruskal’s algorithm gives the MST edges BC, AC, CE, CD with total weight 2 + 3 + 3 + 4 = 12.
4. Step 2: Depth-First Search of the MST | 第二步：对最小生成树进行深度优先搜索
A depth-first search starts at a chosen vertex and follows one branch of the tree as far as possible before backtracking. When a vertex has unvisited neighbours, go to the next unvisited neighbour. When a dead end is reached, backtrack to the most recent vertex that still has an unvisited neighbour.
At each vertex, the order of neighbour choice may be alphabetical, by increasing edge weight, or as specified in the question. Different choices can produce different tours, so always state the order you are using.
5. Step 3: List Vertices in First-Visit Order | 第三步：按首次访问顺序列出顶点
During the depth-first search, write down a vertex only when it is visited for the first time. Do not write it again when backtracking through it. The final list is the order of first visits. This list determines your candidate Hamiltonian cycle.
For example, starting at A and using alphabetical order at C, the depth-first search of the MST with edges A–C, C–B, C–D, C–E gives the first-visit order A, C, B, D, E.
例如，从 A 出发，在 C 处按字母顺序选择，对边为 A–C、C–B、C–D、C–E 的最小生成树进行深度优先搜索，得到首次访问顺序 A、C、B、D、E。
6. Step 4: Close the Cycle and Calculate Length | 第四步：闭合回路并计算长度
After listing all vertices, return directly from the last vertex to the first vertex. This direct edge must exist because the network is complete. Then calculate the tour length by adding the weights of the consecutive edges in the cycle.
The tour length is an upper bound for the optimal travelling salesman tour. Write the answer as: optimal tour length ≤ tour length found.
该路线长度是最优旅行商路线的一个上界。答案写作：最优路线长度 ≤ 所求路线长度。
7. Worked Example: Distance Table | 示例：距离表
The following complete network has five vertices A, B, C, D, E. Use the minimum spanning tree method to find an upper bound for the optimal tour length.
以下完全网络有五个顶点 A、B、C、D、E。使用最小生成树方法求最优路线长度的上界。
Vertex
A
B
C
D
E
A
—
4
3
5
6
B
4
—
2
7
5
C
3
2
—
4
3
D
5
7
4
—
4
E
6
5
3
4
—
Sort edges for Kruskal: BC = 2, AC = 3, CE = 3, AB = 4, CD = 4, DE = 4, AD = 5, BE = 5, AE = 6, BD = 7. Add BC, AC, CE, CD. The MST has total weight 12.
8. Worked Example: Depth-First Traversal and Upper Bound | 示例：深度优先遍历与上界
Start the depth-first search at A. The MST is A–C, C–B, C–D, C–E. At C, use alphabetical order, so visit B first, then D, then E. The first-visit order is A, C, B, D, E.
从 A 开始深度优先搜索。最小生成树为 A–C、C–B、C–D、C–E。在 C 处按字母顺序，先访问 B，然后 D，再 E。首次访问顺序为 A、C、B、D、E。
Return from E directly to A to close the cycle. The candidate tour is A–C–B–D–E–A. Its length is calculated as follows.
Therefore the optimal tour length is at most 22, so an upper bound is 22. If the question asks for the best possible upper bound from different depth-first search orderings, you can try all valid orderings and select the smallest tour length found.
The depth-first search of a minimum spanning tree gives a sequence that visits every vertex at least once, and recording first visits removes repeated vertices. Since the original network is complete, you can join consecutive vertices in the first-visit list directly. The result is a Hamiltonian cycle, so it is a feasible tour.
The optimal tour is the shortest of all Hamiltonian cycles. Any feasible tour length must be greater than or equal to the optimal length, so the calculated tour length is an upper bound. A smaller upper bound is better, but any valid upper bound is accepted unless the question demands the best one.
One common mistake is writing down a vertex every time it is passed during backtracking. This creates repeated vertices in the tour, which is not a Hamiltonian cycle. Only record the first visit to each vertex.
Another mistake is using an edge that is not in the original graph to close the cycle. The network must be complete, so the direct return edge exists, but always check the distance table. Also do not use the MST weight as the upper bound; you must calculate the original edge weights along the tour.
In the exam, show the sorted edges for Kruskal or the Prim table, draw the MST, draw or list the depth-first search order, then show the final tour and its length. Clear working helps secure method marks even if a small arithmetic error occurs.
考试中，展示 Kruskal 的排序边或 Prim 表格，画出最小生成树，画出或列出深度优先搜索顺序，然后展示最终路线及其长度。清晰的步骤有助于即使出现小的计算错误也能拿到方法分。
11. Quick Comparison with Nearest Neighbour | 与最近邻法快速比较
The nearest neighbour algorithm chooses the cheapest unvisited vertex from the current vertex. It is faster, but it often produces a tour that can be locally trapped. The minimum spanning tree method uses global cheap connections first and then converts the tree into a cycle, so it is less likely to miss very cheap edges.
Both methods produce upper bounds. In Edexcel D1, you may be asked to compare two upper bounds or to explain why the minimum spanning tree method is suitable. A smaller upper bound is closer to the true optimal tour, so it is more useful.
To find an upper bound using a minimum spanning tree method: find the MST, perform a depth-first search from a chosen start vertex, list vertices in first-visit order, return directly to the start, and calculate the tour length. This gives a valid Hamiltonian cycle, so its length is an upper bound for the optimal travelling salesman tour.
Practice with different complete networks and check your depth-first search order carefully. In the exam, always state your ordering rule and show your working for full marks.
The nearest neighbour algorithm is a fast, greedy route-building method. It is particularly important in the Edexcel A Level Computer Science specification when solving the travelling salesman problem (TSP), where an exact solution is often computationally infeasible.
最近邻算法是一种快速、贪心的路径构建方法。在 Edexcel A Level 计算机科学大纲中，它在求解旅行商问题（TSP）时尤为重要，因为精确解往往在计算上不可行。
1. Overview and Exam Context | 概述与考试背景
In Edexcel A Level Computer Science, the nearest neighbour algorithm is a standard example of a greedy heuristic. It is used to produce a route, or tour, through a graph in which every pair of vertices is connected by a weighted edge. The most common application is the travelling salesman problem, where the goal is to visit every vertex exactly once and return to the start with the smallest possible total weight.
在 Edexcel A Level 计算机科学中，最近邻算法是贪心启发式算法的标准示例。它用于在每对顶点都由加权边相连的图中生成一条路线或回路。最常见的应用是旅行商问题，目标是恰好访问每个顶点一次并返回起点，使总权重尽可能小。
Exam questions may ask candidates to trace the algorithm on a distance matrix, write pseudocode, state the time complexity, or discuss why the result is not necessarily optimal. Marks are typically awarded for a clear sequence of visited
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
📚 Chapter Review 4: Graphs and Transformations | 第4章复习：函数图像与变换
This chapter review consolidates the key skills for Edexcel A-Level Pure Mathematics Chapter 4: recognising and sketching cubic, quartic and reciprocal graphs, and applying transformations to any given function y = f(x). The focus is on efficient curve sketching and writing new equations after translations, stretches and reflections.
本章复习巩固爱德思 A-Level 纯数学第4章的核心技能：识别并绘制三次、四次和倒数函数图像，以及对任意给定函数 y = f(x) 进行图像变换。重点是高效绘制曲线以及写出平移、伸缩和反射后的新方程。
1. Sketching Cubic Graphs | 绘制三次函数图像
A cubic curve has the general form y = ax³ + bx² + cx + d. The sign of a controls the end behaviour: if a > 0, the curve falls to −∞ on the left and rises to +∞ on the right; if a < 0, this is reversed.
三次曲线的一般式为 y = ax³ + bx² + cx + d。系数 a 的正负决定两端走势：若 a > 0，曲线左侧趋向 −∞、右侧趋向 +∞；若 a < 0 则相反。
To sketch a cubic, find the y-intercept at (0, d) and factorise where possible to locate x-intercepts. A repeated factor gives a stationary point on the x-axis, while a triple factor gives an inflection point that crosses the axis.
绘图时先找出 y 轴截距 (0, d)，并尽可能因式分解以确定 x 轴截距。重复因式表示 x 轴处有静止点；三重因式表示过 x 轴处为拐点。
For example, y = (x − 2)(x + 3)² has a root at x = 2 where the curve crosses the x-axis, and a repeated root at x = −3 where the curve touches the x-axis and turns.
例如，y = (x − 2)(x + 3)² 在 x = 2 处有一个根且曲线穿过 x 轴，在 x = −3 处有重根，曲线在 x 轴处相切并转向。
2. Sketching Quartic Graphs | 绘制四次函数图像
A quartic graph y = ax⁴ + bx³ + cx² + dx + e is shaped like a W or U depending on repeated roots. If a > 0, both ends rise to +∞; if a < 0, both ends fall to −∞.
四次函数图像 y = ax⁴ + bx³ + cx² + dx + e 根据重根不同可呈 W 形或 U 形。若 a > 0，两端都上升至 +∞；若 a < 0，两端都下降至 −∞。
Repeated factors such as (x − p)² create a bounce at the x-axis, while a single factor creates a crossing. A triple factor in a quartic
Published by TutorHao | A-Level Revision Series | aleveler.com
📚 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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²).
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.
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.
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.
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.
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.
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.
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.
📚 Using the Route Inspection Algorithm | 使用路径检查算法（中国邮递员算法）
The route inspection algorithm, often called the Chinese postman algorithm, is a graph theory method used to find the shortest route that traverses every edge in a network at least once and returns to the start vertex. In A-Level Computer Science and Decision Mathematics, this algorithm models real-world tasks such as refuse collection, postal delivery, gritting roads, and network maintenance. The central idea is to make a non-Eulerian graph Eulerian by adding the least possible extra distance in the form of repeated edges.
1. What is the Route Inspection Algorithm? | 什么是路径检查算法？
The route inspection problem asks: given a connected weighted graph, find the minimum-weight closed walk that includes every edge at least once. A walk that covers every edge exactly once is an Eulerian circuit and exists only if every vertex has even degree. The route inspection algorithm identifies which edges must be repeated in order to create such a circuit when the original graph does not already have one.
Before applying the algorithm, you must be confident with basic graph terminology. The degree of a vertex is the number of edges incident to it. A vertex is odd if its degree is odd, and even if its degree is even. A walk is a sequence of edges where consecutive edges share a vertex. A circuit is a closed walk. An Eulerian circuit traverses every edge exactly once, while a semi-Eulerian trail traverses every edge exactly once but starts and ends at different vertices.
Closed walk using every edge exactly once / 恰好经过每条边一次的闭合行走
Semi-Eulerian trail
半欧拉迹
Trail using every edge exactly once, different start and end / 恰好经过每条边一次但起点终点不同的迹
3. Eulerian Graphs and Closed Routes | 欧拉图与闭合路线
A connected graph is Eulerian if every vertex has even degree. In this case, an Eulerian circuit exists, so the route inspection answer is simply the total weight of all edges. No edge needs to be repeated. You can find the circuit using Fleury’s algorithm or by tracing edges and removing them once used, but for exam purposes you may only need the total length.
If a connected graph has exactly two odd vertices, it is semi-Eulerian and has an Eulerian trail but no Eulerian circuit. To return to the start, the two odd vertices must become even by duplicating a path connecting them. The least extra distance is the shortest path between those two odd vertices. The route inspection length is total weight + shortest path weight.
5. Pairing Odd Vertices and Repeated Edges | 配对奇顶点与重复边
When a graph has more than two odd vertices, the number of odd vertices is always even. The algorithm requires pairing all odd vertices so that every odd vertex is connected by a repeated shortest path to exactly one other odd vertex. These repeated paths add extra edges and make every vertex even. The challenge is to choose the pairing with the smallest total additional weight.
6. The Route Inspection Algorithm Step by Step | 路径检查算法逐步解析
Step 1: List all vertices and calculate their degrees. Identify which vertices are odd.
步骤 1：列出所有顶点并计算它们的度数。标出哪些顶点是奇顶点。
Step 2: If there are no odd vertices, the graph is Eulerian and the minimum route length is the sum of all edge weights.
步骤 2：如果没有奇顶点，则图是欧拉图，最短路线长度就是所有边权重之和。
Step 3: If there are exactly two odd vertices, find the shortest path between them using Dijkstra’s algorithm or inspection. Add this path as repeated edges. Total length = sum of edge weights + shortest path weight.
Step 4: If there are more than two odd vertices, list all possible pairings of odd vertices. For each pairing, find the sum of the shortest path weights for the pairs. Choose the pairing with the smallest total.
Step 5: Duplicate the edges along the chosen shortest paths so every vertex becomes even. Then find an Eulerian circuit through the enlarged graph. The total route length is the original weight + added repeated weight.
Consider a graph with vertices A, B, C, D and weighted edges AB = 5, BC = 4, CD = 6, DA = 3, AC = 7. The degrees are: deg(A) = 3, deg(B) = 2, deg(C) = 3, deg(D) = 2. Vertices A and C are odd. The sum of all edge weights is 25. The shortest path from A to C is the direct edge AC = 7 because AB + BC = 9 and AD + DC = 9. Therefore the route inspection length is 25 + 7 = 32, and edge AC must be repeated.
考虑一个图，顶点为 A、B、C、D，加权边为 AB = 5、BC = 4、CD = 6、DA = 3、AC = 7。度数分别为：deg(A) = 3、deg(B) = 2、deg(C) = 3、deg(D) = 2。顶点 A 和 C 是奇顶点。所有边权重之和为 25。从 A 到 C 的最短路径是直接边 AC = 7，因为 AB + BC = 9、AD + DC = 9。因此路径检查路线长度为 25 + 7 = 32，边 AC 必须重复。
8. Worked Example with Multiple Pairings | 多组配对示例
Suppose a graph has four odd vertices A, B, C and D. The shortest distances between every pair have been calculated
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
In Edexcel Decision Mathematics, Eulerian graphs provide a powerful way to model routes that cover every edge of a network exactly once. This article explains the definitions, degree conditions, algorithms and exam-style applications you need.
A graph G = (V, E) consists of vertices (nodes) and edges (arcs) joining pairs of vertices. A trail is a sequence of edges in which no edge is repeated; a circuit is a closed trail.
图 G = (V, E) 由顶点（节点）和连接顶点对的边（弧）组成。路径（trail）是指没有重复边的边序列；回路（circuit）是闭合的路径。
In A-Level questions, graphs may be simple, multiple or directed. For Eulerian graphs, the usual focus is on undirected connected graphs, but directed versions appear in Further Mathematics.
A connected graph is Eulerian if it contains an Eulerian circuit: a closed trail that uses every edge exactly once. A graph with an Eulerian circuit is called an Eulerian graph.
Equivalently, a graph is Eulerian if you can start at a vertex, travel along every edge exactly once, and return to the starting vertex without lifting your pen.
等价地说，如果可以从某个顶点出发，沿每条边恰好走一次，并回到起点，且不抬笔，那么该图就是欧拉图。
3. Eulerian trails and circuits | 欧拉路径与回路
An Eulerian trail uses every edge exactly once but does not need to end where it started. An Eulerian circuit is a closed Eulerian trail. Every Eulerian circuit is an Eulerian trail, but not conversely.
For example, the graph with vertices A, B, C and edges AB, BC, CA, AD, DC has an Eulerian trail from B to D but no Eulerian circuit.
例如，顶点为 A、B、C，边为 AB、BC、CA、AD、DC 的图具有从 B 到 D 的欧拉路径，但没有欧拉回路。
4. Semi-Eulerian graphs | 半欧拉图
A connected graph is semi-Eulerian if it contains an Eulerian trail but no Eulerian circuit. This means you can cover every edge exactly once, but the start and end vertices must be different.
For a connected graph, Euler’s theorem gives a simple test. A connected graph is Eulerian if and only if every vertex has even degree.
对于连通图，欧拉定理给出一个简单判定。连通图是欧拉图当且仅当每个顶点的度数都是偶数。
A connected graph is semi-Eulerian if and only if exactly two vertices have odd degree. In that case, the Eulerian trail must start at one odd-degree vertex and end at the other.
If a graph has more than two odd-degree vertices, it is neither Eulerian nor semi-Eulerian. You would need to repeat some edges to cover the network.
如果图中超过两个奇度顶点，则它既不是欧拉图也不是半欧拉图。你需要重复某些边才能遍历整个网络。
Degrees (connected graph)
中文：度数（连通图）
Classification
中文：分类
All even
全部为偶数
Eulerian
欧拉图
Exactly two odd
恰好两个奇数
Semi-Eulerian
半欧拉图
More than two odd
超过两个奇数
Neither
都不是
6. Connectedness and isolated vertices | 连通性与孤立顶点
The degree condition only works for connected graphs. A disconnected graph with all even degrees is not Eulerian because you cannot travel between components.
Isolated vertices with degree 0 are even-degree vertices. If the rest of the graph is connected, isolated vertices may be ignored when checking Eulerian properties.
度数为 0 的孤立顶点属于偶度顶点。如果图的其余部分是连通的，在判断欧拉性质时可以忽略孤立顶点。
7. Fleury’s algorithm | Fleury 算法
Fleury’s algorithm constructs an Eulerian circuit or trail by never crossing a bridge unless there is no alternative. A bridge is an edge whose removal increases the number of connected components.
Start at an appropriate vertex: any vertex for an Eulerian circuit, or one of the two odd-degree vertices for a semi-Eulerian trail. At each step, choose a non-bridge edge if possible.
This algorithm is often tested with small networks where you must explain why a particular edge cannot be used until later.
该算法常在小网络上考查，要求解释为什么某条边必须留到后面才能使用。
8. Hierholzer’s algorithm | Hierholzer 算法
Hierholzer’s algorithm builds an Eulerian circuit by merging edge-disjoint cycles. Start from any vertex, follow unused edges until returning to the start, forming a cycle.
If unused edges remain, find a vertex on the current circuit with unused incident edges, then start a new cycle from that vertex and splice it into the original circuit.
This algorithm is efficient for computer implementations, but exam questions usually ask for one valid Eulerian circuit rather than a specific algorithm.
该算法在计算机实现中很高效，但考试题目通常只要求给出一个有效的欧拉回路，而不要求指定算法。
9. Route inspection problem | 路线检查问题
The route inspection problem, sometimes called the Chinese postman problem, asks for the shortest route that covers every edge at least once and returns to the start.
路线检查问题，有时称为中国邮递员问题，要求找到至少覆盖每条边一次并返回起点的最短路线。
If the graph is Eulerian, the optimum route is simply an Eulerian circuit, and its length equals the sum of all edge weights.
如果图是欧拉图，最优路线就是欧拉回路，其长度等于所有边的权重之和。
If the graph is not Eulerian, you must add repeated edges between odd-degree vertices to make all degrees even. The aim is to minimise the total weight of the repeated edges.
如果图不是欧拉图，则必须在奇度顶点之间添加重复边，使所有度数变为偶数。目标是使重复边的总权重最小。
For Edexcel exams, you need to identify odd-degree vertices, consider pairings, and choose the minimum-weight pairing to determine the length
Published by TutorHao | A-Level Revision Series | aleveler.com
Prim’s algorithm is a greedy method for finding the minimum spanning tree of a connected, weighted, undirected graph. It builds the tree one vertex at a time, always adding the cheapest edge that connects the current tree to a vertex outside the tree.
Prim 算法是一种贪心算法，用于在连通、带权、无向图中寻找最小生成树。它每次扩展一个顶点，总是添加连接当前树与树外顶点的权重最小的边。
1. Minimum Spanning Trees | 最小生成树
A minimum spanning tree, or MST, is a subset of edges that connects every vertex in a graph together without any cycles and has the smallest possible total edge weight. An MST with V vertices always contains exactly V – 1 edges.
最小生成树（MST）是指将图中所有顶点连接起来且不含回路的一棵边子集，并且这些边的总权重尽可能小。对于有 V 个顶点的图，最小生成树恰好包含 V – 1 条边。
Prim’s algorithm is useful because many real-world problems can be modelled as finding a minimum spanning tree, such as designing road networks, laying cables, or building low-cost communication links.
Prim 算法非常实用，因为许多现实问题都可以建模为寻找最小生成树，例如设计道路网络、铺设电缆或建立低成本的通信连接。
2. The Core Idea of Prim’s Algorithm | Prim 算法的核心思想
Prim’s algorithm starts at an arbitrary vertex and treats this vertex as the initial tree. At each step, it looks at every edge that connects a vertex already in the tree to a vertex outside the tree, and it selects the edge with the minimum weight. That edge and the new vertex are then added to the tree.
Prim 算法从任意一个顶点开始，把这个顶点当作初始的树。每一步，它查看所有连接已在树中的顶点与树外顶点的边，并选择权重最小的那条边。然后将这条边和新的顶点加入树中。
This process repeats until all vertices have been included. Because the algorithm always picks the cheapest available connection and never revises earlier decisions, it is classified as a greedy algorithm.
2. While there are still unvisited vertices, select the unvisited vertex with the smallest key value. Add the edge connecting this vertex to the current tree, and mark the vertex as visited.
3. After visiting a vertex, examine all its neighbours that are not yet visited. If the weight of the edge to a neighbour is smaller than the neighbour’s current key value, update that key value and record the current vertex as its parent.
4. Repeat steps 2 and 3 until every vertex is visited. The resulting set of edges used to visit each vertex forms the minimum spanning tree.
4. 重复步骤 2 和 3，直到所有顶点都被访问。最终用于访问每个顶点的边的集合就构成最小生成树。
4. Worked Example | 示例演算
Consider the following weighted graph with vertices A, B, C and D. The edge weights are AB = 4, AC = 2, BC = 1, BD = 5 and CD = 3. Start Prim’s algorithm at vertex A.
考虑一个包含顶点 A、B、C 和 D 的带权图。边的权重为 AB = 4、AC = 2、BC = 1、BD = 5 和 CD = 3。从顶点 A 开始执行 Prim 算法。
The tables below show the visited set, the chosen edge and the current total cost after each step.
下表展示了每一步的已访问集合、选择的边以及当前总成本。
Step
Visited set
Chosen edge
Weight
Total
0
{A}
—
—
0
1
{A, C}
AC
2
2
2
{A, C, B}
CB
1
3
3
{A, C, B, D}
CD
3
6
The minimum spanning tree consists of edges AC, CB and CD, with total weight 2 + 1 + 3 = 6.
最小生成树由边 AC、CB 和 CD 组成，总权重为 2 + 1 + 3 = 6。
5. Data Structures and Implementation | 数据结构与实现
To implement Prim’s algorithm efficiently, we need three main structures: a key array to store the current minimum distance from the tree to each vertex, a parent array to record the edge that connects each vertex to the tree, and a priority queue or similar structure to select the next unvisited vertex with the smallest key.
为了高效地实现 Prim 算法，我们需要三种主要结构：一个 key 数组，用于存储从当前树到每个顶点的最小距离；一个 parent 数组，用于记录连接每个顶点与树的边；以及一个优先队列或类似结构，用于选择下一个 key 值最小的未访问顶点。
A typical high-level implementation can be expressed using the following update rule after adding a vertex u:
在加入顶点 u 之后，典型的高层实现可以用下面的更新规则表示：
if v is unvisited and weight(u, v) < key[v] then key[v] ← weight(u, v), parent[v] ← u
For small graphs, a simple array and linear scan can be used, which is easier to trace in an exam. For larger graphs, a binary heap priority queue reduces the time needed to find the minimum key value.
The time complexity of Prim’s algorithm depends on how the graph is stored and how the next vertex is selected.
Prim 算法的时间复杂度取决于图的存储方式以及如何选择下一个顶点。
If the graph is stored as an adjacency matrix and we use a simple linear scan to find the minimum key, the complexity is O(V²), where V is the number of vertices. This approach is simple and works well for dense graphs.
如果图用邻接矩阵存储，并且使用简单的线性扫描来查找最小 key 值，那么时间复杂度为 O(V²)，其中 V 是顶点数。这种方法简单，并且适用于稠密图。
If the graph is stored as an adjacency list and a binary heap is used as the priority queue, the complexity is O(E log V), where E is the number of edges. This is generally better for sparse graphs. With a Fibonacci heap, the complexity can be improved to O(E + V log V).
如果图用邻接表存储，并使用二叉堆作为优先队列，时间复杂度为 O(E log V)，其中 E 是边数。对于稀疏图，这种方式通常更好。如果使用斐波那契堆，复杂度可以进一步优化为 O(E + V log V)。
7. Correctness of Prim’s Algorithm | Prim 算法的正确性
Prim’s algorithm is correct because of the cut property. A cut partitions the vertices into two disjoint sets; the cut property states that for any cut, the minimum-weight edge crossing the cut belongs to some minimum spanning tree.
Prim 算法之所以正确，是因为切分性质。一个切分将顶点分为两个不相交的集合；切分性质指出，对于任意一个切分，横跨该切分的最小权重边一定属于某个最小生成树。
At every step, Prim’s algorithm considers the cut between the set of visited vertices and the set of unvisited vertices. It adds the minimum-weight edge crossing this cut. By the cut property, this edge is safe to include in an MST. Therefore, after V – 1 iterations, the algorithm has constructed a valid minimum spanning tree.
在每一步，Prim 算法考虑已访问顶点集合与未访问顶点集合之间的切分。它加入横跨这个切分的最小权重边。根据切分性质，这条边可以安全地包含在最小生成树中。因此，经过 V – 1 次迭代后，算法就构造出了一棵有效的最小生成树。
8. Prim’s vs Kruskal’s Algorithm | Prim 与 Kruskal 算法比较
Both Prim’s algorithm and Kruskal’s algorithm find the same minimum spanning tree weight, but they build the tree in different ways. Prim’s algorithm grows a single tree from a starting vertex, whereas Kruskal’s algorithm sorts all edges by weight and adds the cheapest edge that does not create a cycle.
Prim 算法和 Kruskal 算法都能得到相同的最小生成树总权重，但它们的建树方式不同。Prim 算法从一个起始顶点开始生长一棵树，而 Kruskal 算法将所有边按权重排序，然后添加不会形成回路的最便宜边。
Feature
Prim’s algorithm
Kruskal’s algorithm
Approach
Grow one tree from a start vertex
Build forest and merge components
Best for
Dense graphs
Sparse graphs
Time complexity
O(V²) with adjacency matrix, O(E log V) with heap
O(E log E) or O(E log V)
Data structure needed
Priority queue or key array
Union-find / disjoint set
In exam questions, you should choose the algorithm that is easier to apply to the given graph. If the graph is drawn with a clear starting point, Prim’s algorithm is usually faster to trace manually. If the edges are already listed, Kruskal’s algorithm may be simpler.
One common mistake is updating a key value without checking whether the vertex is already visited. This can lead to the same vertex being added twice or an incorrect edge being selected. Always separate the visited set from the unvisited set.
Another mistake is choosing the smallest edge globally instead of the smallest edge crossing the cut. Prim’s algorithm only considers edges that connect the current tree to an outside vertex, not any edge anywhere in the graph.
When tracing Prim’s algorithm in an exam, always draw the current tree and list the candidate crossing edges at each step. Show key values in a table and record which vertex and edge are selected. This makes your reasoning clear and helps avoid arithmetic slips.
在考试中追踪 Prim 算法时，始终画出当前的树，并在每一步列出候选的横跨边。在表格中显示 key 值，并记录选择了哪个顶点和哪条边。这会让你的推理过程更清晰，并帮助避免计算错误。
10. Exam-Style Practice Question | 考试风格练习题
Consider the weighted graph below. The vertices are P, Q, R, S and T. The edge weights are PQ = 7, PR = 5, QR = 3, QS = 4, RS = 2, RT = 6, ST = 5 and QT = 9. Starting at vertex P, use Prim’s algorithm to construct a minimum spanning tree. Show each step clearly.
Solution: Start with P and choose PR = 5. From the visited set {P, R}, the candidate edges are PQ = 7, RQ = 3, RT = 6 and RS = 2. Choose RS = 2. From {P, R, S}, candidates are PQ = 7, RQ = 3, RT = 6, SQ = 4 and ST = 5. Choose RQ = 3. From {P, R, S, Q}, candidates are QT = 9, QS = 4 already visited, RT = 6 and ST = 5. Choose ST = 5. The MST has weight 5 + 2 + 3 + 5 = 15 with edges PR, RS, RQ and ST.
Prim’s algorithm is a greedy algorithm for finding a minimum spanning tree. It grows the tree one vertex at a time by repeatedly adding the cheapest edge that connects a visited vertex to an unvisited vertex. With clear step-by-step tracing, you can confidently solve MST questions in the Edexcel A-Level Computer Science exam.
Prim 算法是一种用于寻找最小生成树的贪心算法。它通过不断添加连接已访问顶点与未访问顶点的最便宜边，每次扩展一个顶点。只要按照清晰的步骤逐步追踪，你就能在 Edexcel A-Level 计算机科学考试中自信地解决最小生成树问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com