The Chinese Postman Problem (also known as the Route Inspection Problem).

Finds the shortest closed walk that traverses every edge of an undirected graph at least once. For Eulerian graphs, this is simply the Eulerian circuit. For graphs with odd-degree vertices, the algorithm:

1. Finds all odd-degree vertices
2. Computes shortest paths between all pairs of odd vertices
3. Finds a minimum-weight perfect matching on the odd vertices
4. Duplicates the matched shortest-path edges to make the graph Eulerian
5. Extracts an Eulerian circuit from the augmented multigraph

Complexity

• Finding odd vertices: O(V)
• All-pairs shortest paths: O(k × (E + V log V)) where k = number of odd vertices
• Minimum-weight perfect matching: O(k² × 2^k) via DP (efficient for small k)
• Eulerian circuit: O(E)

Examples

iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
iex> {:ok, _path, weight} = Yog.Pathfinding.ChinesePostman.chinese_postman(graph)
iex> weight
4