Offensive Security Researcher & Quantum Cryptography Analyst

Postman Problem Algorithm: Working, Explanation, and Route Optimization

Abdul Wahab Junaid
Postman problem algorithm and working of this algorithm

Postman problem algorithm and working of this algorithm

I want to explain this algorithm through its very literal motivating story: imagine I am a postal carrier who must walk down every street on my route, deliver mail, and return to the post office, while covering the least total distance possible. The Chinese Postman Problem (CPP), also called the Route Inspection Problem, asks me to find the shortest closed walk in a graph that traverses every edge at least once. Unlike the Traveling Salesperson Problem, which is about visiting every node, this is about covering every edge — and that distinction is what makes it solvable in polynomial time rather than being NP-hard.

History and Background

The problem was first studied by the Chinese mathematician Meigu Guan (also transliterated as Kwan Mei-Ko) in 1962, which is why it carries the name “Chinese Postman Problem” in his honor. Guan showed how the problem connects to Euler’s classical work on the Seven Bridges of Königsberg (1736), which first established the conditions under which a graph has a closed walk traversing every edge exactly once (an Eulerian circuit). The insight that ties the two together — using Edmonds’ 1965 blossom algorithm for minimum-weight perfect matching — allowed the CPP to be solved efficiently for graphs that aren’t already Eulerian.

Problem Statement

I define the problem as: given a connected, weighted graph $G = (V, E)$, find a closed walk of minimum total weight that traverses every edge at least once, starting and ending at the same vertex.

Core Concepts

How It Works

  1. I check whether the graph is connected — if not, the problem has no valid solution in the classic formulation.
  2. I compute the degree of every vertex and identify the set of odd-degree vertices.
  3. If there are no odd-degree vertices, the graph is already Eulerian, and I simply find the Eulerian circuit directly (via Hierholzer’s algorithm, for instance) — this is my optimal route.
  4. If there are odd-degree vertices, I compute the shortest-path distance between every pair of them.
  5. I find a minimum-weight perfect matching over these odd-degree vertices, pairing them up to minimize total added distance.
  6. For each matched pair, I duplicate the edges along their shortest path in the original graph, which makes their degrees even.
  7. With every vertex now at even degree, the (multi-)graph is Eulerian, so I find its Eulerian circuit — that circuit is the postman’s optimal route.

Working Principle

The core logic hinges on a classical graph-theory fact: a connected graph has an Eulerian circuit if and only if every vertex has even degree. When some vertices have odd degree, I know I’ll be forced to re-traverse (duplicate) some edges to “fix” the parity, since every time I enter and leave a vertex it must be through a pair of edges — an odd-degree vertex, sooner or later, requires an extra pass. The problem then becomes: which edges should I duplicate, at minimum extra cost, to make every vertex even? That’s exactly a minimum-weight perfect matching problem on the odd-degree vertices, using shortest-path distances as matching costs.

Mathematical Foundation

A graph has an Eulerian circuit if and only if:

$$ \deg(v) \equiv 0 \pmod{2} \quad \text{for all } v \in V $$

The number of odd-degree vertices in any graph is always even, guaranteed by the handshake lemma:

$$ \sum_{v \in V} \deg(v) = 2|E| $$

If $O$ is the set of odd-degree vertices, I want the perfect matching $M$ on $O$ minimizing:

$$ \sum_{(u,v) \in M} d(u,v) $$

where $d(u,v)$ is the shortest-path distance between $u$ and $v$ in $G$. The total cost of the postman’s route is then:

$$ \text{Total Cost} = \sum_{e \in E} w(e) + \sum_{(u,v) \in M} d(u,v) $$

Diagrams

flowchart TD
    Start([Start]) --> Degree[Compute vertex degrees]
    Degree --> OddCheck{Any odd-degree vertices?}
    OddCheck -- No --> Euler[Find Eulerian circuit directly]
    OddCheck -- Yes --> Pairs[Compute shortest paths between odd vertices]
    Pairs --> Match[Find minimum-weight perfect matching]
    Match --> Dup[Duplicate matched shortest-path edges]
    Dup --> Euler
    Euler --> End([Return optimal postman route])

Pseudocode

function ChinesePostman(Graph):
    if Graph is not connected:
        return "No solution: graph disconnected"

    oddVertices = [v for v in Graph.vertices if degree(v) is odd]

    if oddVertices is empty:
        return EulerianCircuit(Graph)

    // Build a complete graph over oddVertices with shortest-path weights
    for each pair (u, v) in oddVertices:
        distance[u][v] = ShortestPath(Graph, u, v)

    matching = MinimumWeightPerfectMatching(oddVertices, distance)

    for each (u, v) in matching:
        path = ShortestPathEdges(Graph, u, v)
        duplicate all edges in path within Graph

    return EulerianCircuit(Graph)

Step-by-Step Example

Using the graph above: A–B(2), B–C(3), C–D(2), D–A(3), A–C(4).

Time Complexity

Space Complexity

I need $O(V^2)$ space to store pairwise shortest-path distances among odd vertices, $O(V+E)$ for the graph itself (which grows slightly after edge duplication), and $O(V)$ for degree tracking and matching state — overall space is $O(V^2)$, dominated by the distance matrix among odd vertices.

Correctness Analysis

The correctness rests on two established theorems: first, Euler’s theorem guarantees that a connected graph admits a closed walk traversing every edge exactly once if and only if all vertices have even degree. Second, since the number of odd-degree vertices is always even (by the handshake lemma), they can always be perfectly paired. Minimizing the total distance of duplicated paths directly minimizes the extra distance the postman must re-walk, because every unit of “extra” distance in the optimal solution corresponds to exactly one edge being traversed more than once, and those redundant traversals must connect odd-degree vertices in pairs to restore even parity — which is precisely what minimum-weight perfect matching optimizes.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 4  // A=0, B=1, C=2, D=3
#define INF INT_MAX

// Simple Floyd-Warshall to get all-pairs shortest paths
void floydWarshall(int dist[V][V]) {
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

int main() {
    int graph[V][V] = {
        {0,   2,   4,   3},
        {2,   0,   3,   INF},
        {4,   3,   0,   2},
        {3,   INF, 2,   0}
    };
    int degree[V] = {0};
    int totalWeight = 0;

    // Compute degrees and total edge weight (count each undirected edge once)
    for (int i = 0; i < V; i++) {
        for (int j = i + 1; j < V; j++) {
            if (graph[i][j] != INF && graph[i][j] != 0) {
                degree[i]++;
                degree[j]++;
                totalWeight += graph[i][j];
            }
        }
    }

    printf("Vertex degrees:\n");
    int oddVertices[V], oddCount = 0;
    for (int i = 0; i < V; i++) {
        printf("Vertex %d: degree %d\n", i, degree[i]);
        if (degree[i] % 2 != 0) oddVertices[oddCount++] = i;
    }

    int dist[V][V];
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
    floydWarshall(dist);

    // For this small example (exactly 2 odd vertices), the matching is trivial
    int extra = 0;
    if (oddCount == 2) {
        extra = dist[oddVertices[0]][oddVertices[1]];
        printf("Odd vertices %d and %d matched, extra distance = %d\n",
               oddVertices[0], oddVertices[1], extra);
    } else if (oddCount > 0) {
        printf("More than 2 odd vertices — requires full minimum-weight matching.\n");
    }

    printf("Total edge weight: %d\n", totalWeight);
    printf("Optimal postman route cost: %d\n", totalWeight + extra);

    return 0;
}

Sample Input and Output

Input: the graph above (A, B, C, D with the given edge weights).

Output:

Vertex degrees:
Vertex 0: degree 3
Vertex 1: degree 2
Vertex 2: degree 3
Vertex 3: degree 2
Odd vertices 0 and 2 matched, extra distance = 4
Total edge weight: 14
Optimal postman route cost: 18

This matches my manual walkthrough.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version