Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Intuition
4.
Approach
4.1.
Worked Example of Chinese Postman or Route Inspection Problem
4.2.
Implementation in C++
4.2.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What are Route Inspection Problems?
5.2.
What is the application of the Route Inspection Problem?
5.3.
What will be the complexity of the Route Inspection Problem?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Chinese Postman or Route Inspection Problem

Author Sonu Deo
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Chinese Postman or Route Inspection Problem is a variation of the Eulerian circuit problem for undirected graphs. An Euler Circuit is a closed cycle or circuit that covers every edge of the graph once starting and ending position is the same. Chinese Postman or Route Inspection problem is defined for the connected and undirected graph. 

Route inspection problem

In this article, we will learn the Chinese Postman or Route Inspection Problem, in which we have to find the shortest path that visits every edge of the graph at least once.

Problem Statement

We will be given an undirected graph, and we have to find the shortest cyclic path that will visit all the vertices or edges of the graph at least once.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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

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:

Working example

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.

Working example with shortest path

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;
}

 

Input:

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

 

Output:

7042

 

Complexity Analysis


Time Complexity: O(2N * 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 2n, and traversing each of those sets will take O(N) time.

Space Complexity: O(2N)
Because of the mem array, we have to store the weights for every set of nodes in the graph and the number will be 2n, 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(2N * N)
Space Complexity: O(2N)

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!

Previous article
Check if Graph is Bipartite
Next article
Prim’s MST for Adjacency List Representation
Live masterclass