Chinese Postman or Route Inspection
Problem Statement
Given a weighted undirected connected graph, find the minimum weight closed walk that traverses every edge at least once. This is the Chinese Postman Problem — imagine a postman who must traverse every street and return to the post office, minimizing total distance.
Example:
- Input:
V = 4, edges = [(0,1,3),(0,3,5),(1,2,2),(2,3,4),(1,3,1)] - Output:
17(sum of all edges = 15, plus we need to traverse some edges twice)
Noob-Friendly Explanation
Imagine you're a mail carrier who must walk along every street in a neighbourhood and return home. Each street has a distance. If every intersection connects to an even number of streets, you can walk each street exactly once — perfect! But if some intersections have an odd number of streets, you'll need to walk some streets twice.
The Chinese Postman problem finds the shortest route that covers all streets. The key insight: find intersections with odd degree, pair them up optimally, and add shortest paths between pairs to make all degrees even, then find the Eulerian circuit.
Approach 1: Brute Force
Intuition
If the graph is Eulerian (all vertices have even degree), the answer is simply the sum of all edge weights. Otherwise, find all vertices with odd degree and try all possible pairings, computing the shortest paths between each pair. Pick the pairing with minimum total extra cost.
Algorithm
- Compute sum of all edge weights.
- Find all odd-degree vertices.
- Compute shortest paths between all pairs (Floyd-Warshall).
- Try all possible perfect matchings of odd-degree vertices.
- Answer = sum of all edges + minimum matching cost.
import java.util.*;
public class ChinesePostmanBrute {
public static int solve(int V, int[][] edges) {
int[][] dist = new int[V][V];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE / 2);
for (int i = 0; i < V; i++) dist[i][i] = 0;
int totalWeight = 0;
int[] degree = new int[V];
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
dist[u][v] = Math.min(dist[u][v], w);
dist[v][u] = Math.min(dist[v][u], w);
degree[u]++;
degree[v]++;
totalWeight += w;
}
// Floyd-Warshall
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// Find odd-degree vertices
List<Integer> oddVertices = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (degree[i] % 2 != 0) {
oddVertices.add(i);
}
}
if (oddVertices.isEmpty()) return totalWeight;
// Try all perfect matchings (brute force)
int minExtra = matchBrute(oddVertices, dist, 0, new boolean[oddVertices.size()]);
return totalWeight + minExtra;
}
static int matchBrute(List<Integer> odds, int[][] dist, int idx, boolean[] used) {
while (idx < odds.size() && used[idx]) idx++;
if (idx >= odds.size()) return 0;
used[idx] = true;
int min = Integer.MAX_VALUE;
for (int j = idx + 1; j < odds.size(); j++) {
if (!used[j]) {
used[j] = true;
int cost = dist[odds.get(idx)][odds.get(j)]
+ matchBrute(odds, dist, idx + 1, used);
min = Math.min(min, cost);
used[j] = false;
}
}
used[idx] = false;
return min;
}
public static void main(String[] args) {
int V = 4;
int[][] edges = {{0,1,3},{0,3,5},{1,2,2},{2,3,4},{1,3,1}};
System.out.println("Minimum route: " + solve(V, edges));
}
}Complexity Analysis
- Time Complexity: O(2^V * V²) - exponential matching of odd-degree vertices
- Space Complexity: O(V²) - for the distance matrix
Approach 2: Optimal (Bitmask DP on Odd Vertices)
Intuition
Use bitmask DP to find the minimum weight perfect matching of odd-degree vertices. Let K be the number of odd-degree vertices. dp[mask] = minimum cost to match all vertices in the bitmask. This is much faster than trying all permutations.
Algorithm
- Compute shortest paths (Floyd-Warshall).
- Find K odd-degree vertices.
- Use bitmask DP:
dp[mask]= min cost to perfectly match vertices in mask. - For each mask, pick the lowest unmatched vertex, try pairing it with every other unmatched vertex.
- Answer = total edge weight +
dp[(1<<K)-1].
import java.util.*;
public class ChinesePostmanOptimal {
public static int solve(int V, int[][] edges) {
int[][] dist = new int[V][V];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE / 2);
for (int i = 0; i < V; i++) dist[i][i] = 0;
int totalWeight = 0;
int[] degree = new int[V];
for (int[] e : edges) {
int u = e[0], v = e[1], w = e[2];
dist[u][v] = Math.min(dist[u][v], w);
dist[v][u] = Math.min(dist[v][u], w);
degree[u]++;
degree[v]++;
totalWeight += w;
}
// Floyd-Warshall
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// Find odd-degree vertices
List<Integer> odds = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (degree[i] % 2 != 0) {
odds.add(i);
}
}
if (odds.isEmpty()) return totalWeight;
int K = odds.size();
int[] dp = new int[1 << K];
Arrays.fill(dp, Integer.MAX_VALUE / 2);
dp[0] = 0;
for (int mask = 0; mask < (1 << K); mask++) {
if (dp[mask] >= Integer.MAX_VALUE / 2) continue;
// Find first unmatched vertex
int first = -1;
for (int i = 0; i < K; i++) {
if ((mask & (1 << i)) == 0) {
first = i;
break;
}
}
if (first == -1) continue;
// Try pairing first with every other unmatched vertex
for (int second = first + 1; second < K; second++) {
if ((mask & (1 << second)) == 0) {
int newMask = mask | (1 << first) | (1 << second);
int cost = dist[odds.get(first)][odds.get(second)];
dp[newMask] = Math.min(dp[newMask], dp[mask] + cost);
}
}
}
return totalWeight + dp[(1 << K) - 1];
}
public static void main(String[] args) {
int V = 4;
int[][] edges = {{0,1,3},{0,3,5},{1,2,2},{2,3,4},{1,3,1}};
System.out.println("Minimum route: " + solve(V, edges));
}
}Complexity Analysis
- Time Complexity: O(2^K * K² + V³) - bitmask DP over K odd vertices + Floyd-Warshall, where K is the number of odd-degree vertices (K ≤ V, always even)
- Space Complexity: O(V² + 2^K) - for distance matrix and DP array