The Chinese Postman Problem: Find the shortest closed walk that visits every edge at least once.
If the graph is Eulerian, the answer is the Euler circuit (visit each edge exactly once).
If not Eulerian (odd-degree vertices exist), you must repeat some edges.
Algorithm: Find all vertices with odd degree (always an even count)
Pair them up to minimize total distance
Add shortest paths between paired vertices
Now the graph is Eulerian; find the circuit
This transforms a non-Eulerian graph into an Eulerian one with minimum added weight.