Chinese Postman or Route Inspection Problem

Intuition

First, let us consider an undirected graph with cycles to understand the problem better with an example.

In our example, we have considered an unweighted graph with cycles, as shown in the below image:

Undirected Graph 0340210

Now we will focus on the path that can visit all the edges of the graph at least once. There can be lots of such paths like:

1 -> 0 -> 3 -> 4 -> 0 -> 1 -> 2 ->0 -> 1 and  1-> 0 -> 3 ->4 ->0 -> 2 -> 1

In the first path, we can see that the total length of edges traversed is eight and in the second path, the length or number of edges traveled is 6. And for the Chinese Postman or Route Inspection Problem, we need to find the shortest path hence the second path is valid.

Shortest Path or Chinese postman route

It doesn’t matter whether the graph is weighted or unweighted. The Chinese Postman or route inspection path always remains the same. In the weighted graph, the minimum possible weight of the Postman tour is the sum of all edge weights that the postman visits in the Eulerian Circuit. We can not get a shorter route as the postman must visit every edge of the graph at least once.

Note: If our input graph does NOT contain any Euler Circuit, our task reduces to the following:

• In an unweighted graph, the minimum number of edges is duplicated so that the given graph converts to a graph with the Eulerian Cycle.
• In a weighted graph, the minimum total weight of edges is duplicated so that the given graph converts to a graph with the Eulerian Cycle.

Approach

A Chinese postman or route inspection path is the minimum circuit path that visits all the edges of the graph at least once. To find the minimum Chinese postman or route inspection path, we must walk through each edge of the graph at least once, and in addition, we must also travel along the least pairings of the odd vertices on one extra occasion.

Now let’s see an algorithm for finding an optimal Chinese postman route is as follows:

Step 1: At first, we will list all the odd-degree vertices f the graph.

Step 2: Now, we will list all the possible pairs of the odd vertices.

Step 3: For each odd pairing, find the edge that connects the vertices with the minimum or least weight.

Step 4: Then, we will find the pairings so that the sum of the weights of the edges is minimized.

Step 5: Now, On the original graph, we will add the edges that have been found in Step 4.

Step 6: The length of an optimal Chinese postman or route inspection path is the sum of all the edges of the graph added to the total found in Step 4.

Step 7: Finally, we can find the route corresponding to this minimum sum path can then be easily found.

Worked Example of Chinese Postman or Route Inspection Problem

In this section, we will now apply the algorithm learned above to find the optimal Chinese postman path on a real graph problem. Let’s consider an undirected weighted graph as shown below:

Step 1: At first, we will find the odd vertices in the graph, i.e., A and H.

Step 2: Since we have only two odd vertices thus, we have only one way of pairing these two odd vertices, named AH.

Step 3: The shortest way for joining A to H is by using the path AB, BF, and FH, with a total sum of 160.

Step 4: Add these edges into the original network.

Step 5: The length of the optimal Chinese postman or route inspection path is the sum of all the edges in the original network, i.e., 840 m, plus the answer found in Step 3, i.e., 160 m. Hence the sum of the optimal Chinese postman route is 1000 m.

Step 6: One possible optimal Chinese postman route is ADCGHCABDFBEFHFBA, but other possible routes with the same minimum length can be found.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;


#define N 16
#define int long long
int INF = 1e18;
int n, m;
int deg[N];
int a[N][N], d[N][N];
vector<bool> mark;
vector<int> mem(1<<15);


void dfs(int v)
{
    if (mark[v])
        return;
    mark[v] = true;
    for(int i=0;i<n;i++){
        if (a[v][i] < INF)
            dfs(i);
    }
}


int rec(int mask)
{
    int &res = mem[mask];
    if (res != -1)
        return res;
    if (mask == 0)
        return res = 0;
    res = INF;
    int i1;
    for (i1 = 0; (mask & (1 << i1)) == 0; i1++);
    for(int i2 = i1+1; i2<n; i2++){
        if (mask & (1 << i2))
            res = min(res, d[i1][i2] + rec(mask ^ (1 << i1) ^ (1 << i2)));
    }
    return res;
}


int32_t main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) a[i][j] = INF;
    }
    int sum = 0;
    for(int i=0;i<m;i++){
        int x, y, c;
        cin>>x>>y>>c;
        x--;
        y--;
        a[x][y] = min(a[x][y], c);
        a[y][x] = min(a[y][x], c);
        sum += c;
        deg[x]++, deg[y]++;
    }
    mark.assign(N, false);
    dfs(0);
    bool bad = false;
    for(int i=0;i<n;i++){
        if (!mark[i] && deg[i] > 0)
            bad = true;
    }
    if (bad)
    {
        cout<<-1;
        return 0;
    }
    memcpy(d, a, sizeof a);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    mem.assign(1<<15, -1);
    int mask = 0;
    for(int i=0;i<n;i++){
        if (deg[i] % 2 == 1)
            mask |= 1 << i;
    }
    int res = sum + rec(mask);
    cout<<res;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

4 6
1 2 10
2 3 1000
3 4 10
4 1 1000
4 2 5000
1 3 2

You can also try this code with Online C++ Compiler

Run Code

Output:

7042

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity: O(2^N * N)
Here we are traversing every set of nodes in the graph i.e, for each of N nodes we have two options one is selecting it or not to select it so the total number of different sets will be 2ⁿ, and traversing each of those sets will take O(N) time.

Space Complexity: O(2^N)
Because of the mem array, we have to store the weights for every set of nodes in the graph and the number will be 2ⁿ, as explained above.

Frequently Asked Questions

What are Route Inspection Problems?

Route inspection finds the least weight closed trail covering every edge of a network.

What is the application of the Route Inspection Problem?

The goal of the Chinese postman issue, also known as the postman tour or route inspection problem, is to identify the smallest closed circuit or path that travels around an undirected (connected) graph's whole edge.

What will be the complexity of the Route Inspection Problem?

Time Complexity: O(2^N * N)
Space Complexity: O(2^N)

Conclusion

In this article, we have discussed the Chinese Postman or Route Inspection Problem to find the shortest circuit path in an undirected graph with the Eulerian circuit. Using the concept of DFS Algorithm and dynamic programming.

Solve more such problems and enhance your knowledge with these interesting articles:

Eulerian circuit
Graph
DP-BITMASKING
Floyd-Warshal
Depth-First-Search

Visit our website to read more such blogs. Make sure you enroll in the courses we provide, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Happy Coding!