📚 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.
路径检查算法，通常称为中国邮递员算法，是一种图论方法，用于寻找至少遍历网络中每条边一次并返回起点的最短路线。在 A-Level 计算机科学和决策数学中，该算法用于建模垃圾清运、邮政投递、道路撒盐和网络维护等实际任务。其核心思想是通过添加尽可能少的额外路程（以重复边形式），使非欧拉图变为欧拉图。
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.
路径检查问题要求：给定一个连通加权图，找出至少包含每条边一次的最小权重闭合行走。恰好覆盖每条边一次的行走称为欧拉回路，仅当每个顶点的度数为偶数时才存在。路径检查算法用于在原图不存在欧拉回路时，确定必须重复哪些边以构造这样的回路。
2. Key Graph Theory Terms | 关键图论术语
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.
在应用算法之前，必须熟悉基本图术语。顶点的度是与该顶点相连的边数。度数为奇数的顶点称奇顶点，度数为偶数的顶点称偶顶点。行走是一系列边，相邻边共享顶点。回路是闭合行走。欧拉回路恰好经过每条边一次，而半欧拉迹恰好经过每条边一次，但起点和终点不同。
| English term | 中文术语 | Meaning / 含义 |
|---|---|---|
| Degree | 度数 | Number of edges incident to a vertex / 与顶点相连的边数 |
| Odd vertex | 奇顶点 | Vertex with odd degree / 度数为奇数的顶点 |
| Even vertex | 偶顶点 | Vertex with even degree / 度数为偶数的顶点 |
| Eulerian circuit | 欧拉回路 | 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.
如果连通图的每个顶点都是偶顶点，则该图是欧拉图。此时存在欧拉回路，因此路径检查的答案就是所有边的总权重，无需重复任何边。可以使用弗勒里算法构造回路，或通过每次走过一条边并删除已使用的边来跟踪，但考试中通常只需要总长度。
4. When a Graph is Not Eulerian | 当图不是欧拉图时
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.
步骤 3：如果恰好有两个奇顶点，使用 Dijkstra 算法或观察法找到它们之间的最短路径。将该路径作为重复边添加。总长度 = 边权重总和 + 最短路径权重。
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.
步骤 4：如果奇顶点多于两个，列出所有可能的奇顶点配对。对每种配对，计算各对顶点最短路径权重之和。选择总和最小的配对。
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.
步骤 5：沿所选最短路径复制边，使每个顶点都变为偶顶点。然后在扩大后的图中找出欧拉回路。路线总长度为原始权重 + 增加的重复权重。
7. Worked Example: Simple Network | 示例：简单网络
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
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导