Postmen deliver letters down roads. The Chinese Postman Problem is to find the shortest route in a network that uses every arc (directed edge) and gets back to where they started (closed problem) or doesn't go back (open problem). There are many further variations on the problem, but we are concerned with weighted directed graphs with (possible) parallel arcs, so-called weighted multidigraphs -- what the world wide web is made out of from its HTML links, which are directed and may be repeated. We allow weights because we might, for example, be interested in how long a user takes to explore a web site, so the weights could be measured in seconds.

Here is a simple graph, and below are postman tours of the graph that were output by the Java program you can get from this site.

The following is a closed tour of minimal weight, taking each arc to have equal weight.

The following is an open tour of minimal weight, where an open tour visits every arc but does not necessarily return to where it started. The 'virtual arcs' are an artifact of the way the tour is worked out: the algorithm works by finding the best way to place two virtual arcs on a graph and solving the closed problem that uses them - hence vertex 4 is not really part of the graph!

Resources available

The complete paper is available in PostScript and PDF. It will appear in due course in Software Practice & Experience.

In Java

Code is available in Java as CPP.java.

If you want see how to extract the code used in the paper from the Java source file, look up warp.

In Mathematica

Mathematica notebook. Best if you set your browser preferences to recognise ".nb" to be run by Mathematica.
HTML version (readable if you do not have access to Mathematica).

The Mathematica files also include the definition of the Nokia phone used in the paper.

You can obtain a Mathematica reader from Wolfram Research. You can probably set up you web browser so that Mathematica notebooks are automatically opened in the reader. If you have Mathematica itself, notebooks can be executed to run the algorithm as well.

Other web sites

See also the pages at the Algorithm Design Manual, which covers many useful algorithms.

One form of flattery is plagiarism: see a poster "ON EXERCISING EVERY LINK OF A WEB-SITE WITH MINIMAL EFFORT" by Vaidyanathan Sivaraman presented at The International Conference on High Performance Computing (HiPC), 2002. Or see this local copy, made April 2003: in MS Word or PDF.