What's the cheapest round trip?

# The Route of the Postman

The (Chinese) Postman Problem, also called Postman Tour or Route Inspection Problem, is a famous problem in Graph Theory: The postman's job is to deliver all of the town's mail using the shortest route possible. In order to do so, he (or she) must pass each street once and then return to the origin.

We model this problem using a directed graph. Edges and nodes represent streets and intersections, respectively. The length of a street is represented by the weight of the corresponding edge. By using directed edges, it's possible to also account for one-way-streets etc in the graph.

SVG Download

## Legend

 Node Edge with a weight of 50

## Which graph do you want to execute the algorithm on?

### Modify it to your desire:

• Double click in the drawing panel to create a new node.
• To create an edge, first click on the desired origin and then on the desired destination node.
• You can change edge weights by double clicking on an edge.
• Right-clicking will delete edges and nodes.

Download

### Upload an existing graph:

A occured when reading from file: the contents:

SVG Download

## Legend

 Node Edge with weight 50

## State of the Algorithm

BEGIN

1. Check for Solvability

2. Find imbalanced nodes

3. Find additional paths

4. Insert additional paths

5. Specifying the Euler Tour

END

## If you switch tabs, the execution will be terminated.

You can open another browser window to read the description in parallel.

SVG Download

## Legend

 Node Edge with weight 50

## Test Your Knowledge: What would the algorithm do?

BEGIN

1. Test for solvability

2. Find imbalanced nodes

3. Determine additional paths

4. Insert additional paths

5. Find an Euler Tour

END

## Here you can demonstrate what you have learned: How would the algorithm decide?

The algorithm will run as normal but stop every once in a while. Then you will have to decide what would be the next step.

Hint: Read the description of the algorithm one more time before trying.

## If you switch tabs, the execution will be terminated.

You can open another browser window to read the description in parallel.

SVG Download

## Legend

 Node Edge with weight 50

## Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.