📚 Using the Route Inspection Algorithm | 使用路线检查算法
In many real-world situations, such as postal delivery, road gritting, or refuse collection, a worker must travel along all the streets of a network at least once and return to the starting point. The Route Inspection Algorithm, also known as the Chinese Postman Algorithm, provides an optimal way to find the shortest closed walk that covers every edge in a weighted undirected graph. This article explains the algorithm step by step, illustrates it with a worked example, and discusses its efficiency and applications for Edexcel A-Level Computer Science.
在许多实际情况中，例如邮件投递、道路撒盐或垃圾收集，工作人员必须至少经过网络中的所有街道一次并返回起点。路线检查算法（也称为中国邮递员算法）提供了在带权无向图中找到覆盖每条边的最短闭合行走的最优方法。本文逐步解释该算法，通过一个例题加以说明，并讨论其效率和应用，以配合爱德思A-Level计算机科学课程。
1. Introduction to the Problem | 问题引入
The Route Inspection Algorithm solves the problem of finding a minimum-weight closed walk that traverses every edge of a connected weighted graph at least once. If the graph is Eulerian (all vertices have even degree), any Eulerian circuit is a solution with zero repeated edges. However, many practical graphs contain vertices of odd degree, which forces the walk to revisit some edges. The algorithm determines which edges to duplicate so that the total added weight is minimised.
路线检查算法解决的问题是找到一个经过连通带权图中每条边至少一次且总权重最小的闭合行走。如果图是欧拉图（所有顶点度数为偶数），任何欧拉回路都是没有重复边的解。然而，许多实际图包含奇度顶点，迫使行走必须重复某些边。该算法确定需要复制哪些边，以使总新增权重最小。
2. Key Concepts: Eulerian Graphs and Trails | 关键概念：欧拉图与欧拉迹
A graph is Eulerian if every vertex has an even degree. In an Eulerian graph, there exists an Eulerian circuit – a closed trail that uses each edge exactly once. If exactly two vertices have odd degree, the graph has an Eulerian trail but not a circuit. For the route inspection problem, the ideal scenario is an Eulerian graph. When odd-degree vertices exist, we must artificially add edges (or duplicate existing edges) to make all degrees even, allowing an Eulerian circuit to be formed.
如果一个图的每个顶点度数均为偶数，则该图是欧拉图。在欧拉图中，存在一条欧拉回路——一条恰好使用每条边一次的闭合迹。如果恰好有两个奇度顶点，该图有一条欧拉迹但没有回路。对于路线检查问题，理想情况是图本身为欧拉图。当存在奇度顶点时，我们必须人为添加边（或复制已有的边）使所有顶点度数为偶数，从而可以构造欧拉回路。
3. Formal Statement of the Chinese Postman Problem | 中国邮递员问题的形式化描述
Given a connected undirected graph with positive edge weights, the Chinese Postman Problem (CPP) asks for the shortest closed walk that includes every edge at least once. The solution always involves making the graph Eulerian by duplicating a set of edges whose total weight is minimised. The walk length equals the total weight of all original edges plus the total weight of the duplicated edges.
给定一个边具有正权重的连通无向图，中国邮递员问题要求找到一条包含每条边至少一次的最短闭合行走。该问题的解总是通过复制一组总权重最小的边使图成为欧拉图。行走长度等于所有原始边的总权重加上被复制边的总权重。
4. Overview of the Route Inspection Algorithm | 路线检查算法概览
The algorithm proceeds in four main steps: (1) Identify all vertices with odd degree. (2) If no odd-degree vertices exist, the graph is already Eulerian; stop and find any Eulerian circuit. Otherwise, find a minimum-weight perfect matching among the odd-degree vertices, where the weight of a matching pair is the shortest path distance between them in the original graph. (3) Duplicate the edges along each shortest path corresponding to the matching. (4) In the resulting Eulerian multigraph, find an Eulerian circuit. This circuit is the optimal route.
算法主要分为四个步骤：（1）找出所有奇度顶点。（2）如果没有奇度顶点，图已经是欧拉图；停止并寻找任意一条欧拉回路。否则，在奇度顶点之间找到最小权重的完美匹配，其中一对匹配的权值等于原始图中它们之间的最短路径距离。（3）沿着每条对应于匹配的最短路径复制边。（4）在得到的欧拉多重图中找到一条欧拉回路。这条回路就是最优路线。
5. Step 1: Identifying Odd-Degree Vertices | 步骤1：识别奇度顶点
Start by listing all vertices and calculating their degrees. A vertex degree is simply the number of edges incident to it. Any vertex whose degree is an odd number must be handled. By the handshaking lemma, the number of odd-degree vertices in any graph is always even. This guarantees that a perfect matching is possible.
首先列出所有顶点并计算其度数。顶点度数即与其相连的边的数量。任何度数为奇数的顶点都需要处理。根据握手引理，任何图中奇度顶点的个数总是偶数，这保证了完美匹配是可能的。
6. Step 2: Finding the All-Pairs Shortest Paths | 步骤2：计算所有配对的最短路径
Before matching odd vertices, we must know the shortest distance between every pair of them. If a direct edge exists, its weight may not be the shortest route if a cheaper indirect path exists. Use Dijkstra's algorithm or, for small graphs, inspection to build a distance table for the odd vertices. For n odd vertices, this table has n(n - 1)/2 entries.
在配对奇度顶点之前，我们必须知道每对奇度顶点之间的最短距离。如果存在直接边，如果有更廉价的间接路径，它的权值可能不是最短的。使用迪杰斯特拉算法，或对于小图通过观察，为奇度顶点建立一个距离表。对于 n 个奇度顶点，这个表有 n(n-1)/2 个条目。
7. Step 2 continued: Minimum Weight Perfect Matching | 步骤2续：最小权重完美匹配
We must pair up all odd vertices such that the sum of shortest distances among the pairs is minimised. For a small number of odd vertices (typically up to 8–10 in exam problems), this can be done exhaustively by listing all possible pairings, calculating the total weight for each, and selecting the minimum. For two odd vertices, simply take the shortest path between them.
我们必须将所有的奇度顶点两两配对，并使得各对之间最短距离的总和最小。对于数量较少的奇度顶点（考试题目中通常最多8–10个），可以通过列举所有可能的配对，计算每种配对的总权值，并选择最小值来穷举完成。只有两个奇度顶点时，直接取它们之间的最短路径。
8. Step 3: Duplicating Edges Along Matching Paths | 步骤3：沿匹配路径复制边
Once the optimal matching is determined, duplicate every edge on each chosen shortest path. If a path passes through the same edge multiple times in different matchings, duplicate it multiple times. After duplication, every vertex in the new multigraph will have an even degree. The total weight of duplicated edges is exactly the matching total weight, and this is the minimum extra length required to make the graph Eulerian.
一旦确定了最优匹配，就复制每条被选中的最短路径上的每条边。如果一条路径在不同的匹配中多次经过同一条边，则多次复制该条边。复制之后，新多重图中的每个顶点都将具有偶数度。被复制边的总权值正好等于匹配总权值，并且这是使图成为欧拉图所需的最小额外长度。
9. Step 4: Finding an Eulerian Circuit | 步骤4：寻找欧拉回路
Now that the graph is Eulerian, we can construct an Eulerian circuit using Fleury's algorithm or a depth-first search based approach. The circuit will traverse each original edge and each duplicated edge exactly once. The total length of the walk is the sum of all original edge weights plus the extra duplicated weight. This walk represents the optimal route for the route inspection problem.
既然图已经是欧拉图，我们可以使用弗勒里算法或基于深度优先搜索的方法构造一条欧拉回路。该回路将遍历每条原始边和每条复制边恰好一次。行走的总长度是所有原始边的权重之和加上额外的复制权重。这条行走代表了路线检查问题的最优路线。
10. Worked Example: A Small Street Network | 例题解析：一个小型街道网络
g(B) = 3, deg(C) = 3, deg(D) = 3. All four vertices are odd, so we need a matching of four vertices. List the shortest distances between every pair using the given weights and noting that any direct edge is the shortest path. The distance matrix is:
考虑一个具有顶点 A, B, C, D 和以下带权边的图：AB = 4, AC = 5, AD = 6, BC = 3, BD = 7, CD = 2。首先计算度数：deg(A) = 3, deg(B) = 3, deg(C) = 3, deg(D) = 3。所有四个顶点都是奇度，所以我们需要四个顶点的匹配。使用给定权值列出每对顶点之间的最短距离，并注意任何直接边就是最短路径。距离矩阵为：
| A | B | C | D | |
| A | 0 | 4 | 5 | 6 |
| B | 4 | 0 | 3 | 7 |
| C | 5 | 3 | 0 | 2 |
| D | 6 | 7 | 2 | 0 |
um is 6, so we pair A with B using edge AB, and C with D using edge CD. Duplicate edges AB and CD. Now the degrees become: A=4, B=4, C=4, D=4. The total original weight is 4+5+6+3+7+2 = 27. Total duplicated weight = 6. Optimal route length = 27 + 6 = 33. An Eulerian circuit can then be found, e.g., A – B – C – D – C – A – D – B – A (traversing duplicated edges as needed).
有三种可能的配对：(AB, CD), (AC, BD) 和 (AD, BC)。计算总和：(AB + CD) = 4 + 2 = 6，(AC + BD) = 5 + 7 = 12，(AD + BC) = 6 + 3 = 9。最小值为6，因此我们将 A 与 B 通过边 AB 配对，C 与 D 通过边 CD 配对。复制边 AB 和 CD。此时度数变为：A=4, B=4, C=4, D=4。所有原始边的总权重为 4+5+6+3+7+2 = 27。复制边的总权重为 6。最优路线长度为 27 + 6 = 33。然后可以找到一条欧拉回路，例如 A – B – C – D – C – A – D – B – A（根据需要遍历复制边）。
Note that the duplicated edges AB and CD each appear twice. The circuit uses every resulting edge exactly once, which ensures no unnecessary repetition.
注意复制边 AB 和 CD 各出现了两次。该回路恰好使用每条结果边一次，确保了没有不必要的重复。
11. Complexity and Considerations for Exam Questions | 复杂度与考试注意事项
The most computationally intense step is the minimum weight perfect matching when there are many odd vertices. For a large graph, this is solved using the blossom algorithm with polynomial time. In A-Level exams, graphs are designed to have at most six odd-degree vertices, allowing exhaustive enumeration. It is essential to show clearly: listing odd vertices, constructing shortest distance table, enumerating all matchings, selecting the minimum, duplicating edges, and drawing or describing the final Eulerian circuit.
计算量最大的一步是当存在许多奇度顶点时的最小权重完美匹配。对于大型图，可以使用开花算法在多项式时间内求解。在A-Level考试中，图的奇度顶点通常不超过六个，因此可以采用穷举法。清晰的展示至关重要：列出奇度顶点，构造最短距离表，枚举所有配对，选择最小匹配，复制边，并画出或描述最终的欧拉回路。
12. Conclusion and Real-World Applications | 结论与实际应用
The Route Inspection Algorithm elegantly solves the problem of finding the shortest route that covers all edges of a network. It is used in logistics, street cleaning, mail delivery, and any scenario where arcs must be traversed entirely. Mastering this algorithm requires a solid understanding of graph degrees, shortest paths, matching, and Eulerian circuits. By following the structured steps, students can confidently tackle examination questions and appreciate the algorithm's practical value.
路线检查算法巧妙地解决了寻找覆盖网络所有边的最短路线的问题。它被用于物流、街道清扫、邮件投递以及任何必须遍历全部弧线的场景。掌握该算法需要扎实理解图度数、最短路径、匹配和欧拉回路。通过遵循结构化的步骤，学生可以自信地解答考试题目，并领会该算法的实际价值。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图