Graph · 40 of 43
Chinese Postman or Route Inspection
Walk down every path in the park at least once and come back to the gate, walking as little as possible.
- Simple way
- time O(V^3 + k!)
room O(V^2) - Clever way
- time O(V^3 + 2^k * k)
room O(V^2 + 2^k)
The problem, simply
You get a connected map of corners joined by two-way roads, and every road has a length. You must walk along every road at least once and end where you started.
Give back the smallest total distance. Here V is the number of corners, E the number of roads, and k the number of corners where an odd number of roads meet.
A story to remember it
Picture it
Eight roads with total length 26. Corners 1, 2, 3 and 4 each touch three roads, which is odd.
- checking
Examples
Four odd corners
- In
V = 6, roads = [[0,1,4],[0,2,3],[1,2,2],[1,3,5],[2,4,6],[3,4,1],[3,5,2],[4,5,3]]- Out
29
All roads add to 26. The cheapest pairing is 1 with 2 (cost 2) and 3 with 4 (cost 1). 26 + 3 = 29.
Two odd corners
- In
V = 4, roads = [[0,1,3],[0,3,5],[1,2,2],[2,3,4],[1,3,1]]- Out
16
All roads add to 15. Only corners 1 and 3 are odd, and the shortest walk between them is the road of length 1. 15 + 1 = 16.
Every corner is even
- In
V = 4, roads = [[0,1,1],[1,2,1],[2,3,1],[3,0,1]]- Out
4
A square. You can walk each road exactly once and come home. No extra walking.
One road
- In
V = 2, roads = [[0,1,7]]- Out
14
Both ends are odd. Pair them, and the shortest walk between them is the road itself. Walk there and back.
Way 1: the simple way
The sum of all roads is always paid. The only question is the extra. So:
- Add up all road lengths.
- Count roads at each corner and list the odd corners. There is always an even number of them.
- Find the shortest walk between every two corners with Floyd-Warshall: for every middle corner
m, check if going throughmis shorter. - Try every way to pair up the odd corners. Take the first unpaired corner, try each partner, and recurse on the rest. Keep the cheapest total.
class PostmanBrute {
public static int shortestRoute(int V, int[][] roads) {
final int INF = Integer.MAX_VALUE / 2;
int[][] dist = new int[V][V];
for (int[] row : dist) Arrays.fill(row, INF);
for (int i = 0; i < V; i++) dist[i][i] = 0;
int[] degree = new int[V];
int total = 0;
for (int[] r : roads) {
dist[r[0]][r[1]] = Math.min(dist[r[0]][r[1]], r[2]);
dist[r[1]][r[0]] = dist[r[0]][r[1]];
degree[r[0]]++;
degree[r[1]]++;
total += r[2]; // every road is walked once anyway
}
for (int m = 0; m < V; m++) // shortest walk between every pair
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = Math.min(dist[i][j], dist[i][m] + dist[m][j]);
List<Integer> odd = new ArrayList<>();
for (int i = 0; i < V; i++) if (degree[i] % 2 == 1) odd.add(i);
return total + pairUp(odd, new boolean[odd.size()], dist);
}
static int pairUp(List<Integer> odd, boolean[] used, int[][] dist) {
int first = 0;
while (first < odd.size() && used[first]) first++;
if (first == odd.size()) return 0; // everyone has a partner
used[first] = true;
int best = Integer.MAX_VALUE;
for (int j = first + 1; j < odd.size(); j++) {
if (used[j]) continue;
used[j] = true;
best = Math.min(best, dist[odd.get(first)][odd.get(j)] + pairUp(odd, used, dist));
used[j] = false;
}
used[first] = false;
return best;
}
}How long it takes: Floyd-Warshall is O(V^3). The number of pairings is (k - 1) * (k - 3) * ... * 1, which grows like a factorial, so O(k!) as a simple bound. Extra room: the distance table, O(V^2).
Way 2: the clever way
Trying every pairing repeats work. Whether you paired {1, 3} first or {3, 1}, the leftover problem "pair up 2 and 4" is the same. So write down the best cost for each set of already paired corners, and build bigger sets from smaller ones.
- Steps 1 to 3 are the same: total, odd corners, Floyd-Warshall.
- Number the odd corners
0tok - 1. A set of them is a number whose bits say who is paired. This is a bitmask. best[0] = 0. Go through the sets from small numbers to large. In each set, find the first unpaired corner and try each other unpaired corner as its partner, writingbest[bigger set] = min(..., best[set] + dist).- The answer is
total + best[all paired].
Pair up the odd corners with a table of best costs
01 / 11
Add up every road once: 4 + 3 + 2 + 5 + 6 + 1 + 2 + 3 = 26. Any route must pay at least this much.
- all roads
- 26
- looking now
- checking
- done
- answer
- rejected
- path
- just added
class PostmanBitmask {
public static int shortestRoute(int V, int[][] roads) {
final int INF = Integer.MAX_VALUE / 2;
int[][] dist = new int[V][V];
for (int[] row : dist) Arrays.fill(row, INF);
for (int i = 0; i < V; i++) dist[i][i] = 0;
int[] degree = new int[V];
int total = 0;
for (int[] r : roads) {
dist[r[0]][r[1]] = Math.min(dist[r[0]][r[1]], r[2]);
dist[r[1]][r[0]] = dist[r[0]][r[1]];
degree[r[0]]++;
degree[r[1]]++;
total += r[2];
}
for (int m = 0; m < V; m++)
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = Math.min(dist[i][j], dist[i][m] + dist[m][j]);
List<Integer> odd = new ArrayList<>();
for (int i = 0; i < V; i++) if (degree[i] % 2 == 1) odd.add(i);
int k = odd.size();
if (k == 0) return total; // already walkable in one loop
int[] best = new int[1 << k]; // best[set] = cheapest pairing of that set
Arrays.fill(best, INF);
best[0] = 0;
for (int mask = 0; mask < (1 << k); mask++) {
if (best[mask] == INF) continue;
int first = 0;
while (first < k && (mask >> first & 1) == 1) first++;
if (first == k) continue; // everyone is paired
for (int j = first + 1; j < k; j++) {
if ((mask >> j & 1) == 1) continue;
int next = mask | (1 << first) | (1 << j);
int cost = best[mask] + dist[odd.get(first)][odd.get(j)];
best[next] = Math.min(best[next], cost);
}
}
return total + best[(1 << k) - 1];
}
public static void main(String[] args) {
int[][] roads = {{0, 1, 4}, {0, 2, 3}, {1, 2, 2}, {1, 3, 5}, {2, 4, 6}, {3, 4, 1}, {3, 5, 2}, {4, 5, 3}};
System.out.println(shortestRoute(6, roads)); // 29
}
}How long it takes: Floyd-Warshall O(V^3), plus 2^k sets with O(k) work each, O(V^3 + 2^k * k). Extra room: the distance table and the table of sets, O(V^2 + 2^k).
Watch out for
- If every corner is even, the answer is the sum of all roads. Return early.
- The number of odd corners is always even, because every road adds 2 to the total count of road ends.
- The map must be connected. If it is not, no single closed walk can cover everything.
- Use
Integer.MAX_VALUE / 2as infinity so that adding two of them does not wrap around.
What interviewers ask next
- Why does the doubling work? After adding the extra walks, every corner has an even number of road ends. Euler showed that a connected map with all even corners has a closed walk using each road exactly once.
- How would you print the actual route? Add the doubled roads to the map, then build the closed walk with Hierholzer's algorithm: walk until stuck, then splice in loops from corners that still have unused roads.
- What if you may start and end at different corners? With exactly two odd corners, start at one and end at the other, and the answer is only the sum of the roads.
- Is there a polynomial solution for many odd corners? Yes, minimum weight perfect matching with Edmonds' blossom algorithm in
O(V^3). The bitmask way is what fits in an interview. - What about one-way streets? Then you balance in-roads and out-roads with a minimum cost flow instead of pairing.
Remember this
Grown-up words: corners are vertices, roads are weighted edges, the number of roads at a corner is its degree, a closed walk that uses every road once is an Euler circuit, pairing the odd corners is a minimum weight perfect matching, and the table over sets of corners is bitmask dynamic programming.