The Ninth DIMACS Implementation Challenge:
The Shortest Path Problem

November 13 - 14, 2006
DIMACS Center, Rutgers University, Piscataway, NJ

Camil Demetrescu, University of Rome "La Sapienza"
Andrew Goldberg, Microsoft Research
David Johnson, AT&T Labs - Research,

Special thanks go to Microsoft Research for its contribution to this meeting.


Shortest path problems are ones of the most fundamental combinatorial optimization problems with many applications, both direct and as subroutines in other combinatorial optimization algorithms. Algorithms for these problems have been studied since 1950's and still remain an active area of research.

One goal of this Challenge is to create a reproducible picture of the state of the art in the area of shortest path algorithms. To this end we are identifying a standard set of benchmark instances and generators, as well as benchmark implementations of well-known shortest path algorithms.

Another goal is to enable current researchers to compare their codes with each other, in hopes of identifying the more effective of the recent algorithmic innovations that have been proposed.

The final goal is to publish proceedings containing results presented at the Challenge workshop, and a book containing the best of the proceedings papers.

Problems addressed

The Challenge addresses a wide range of shortest path problems, including all sensible combinations of the following:

Implementations on any platform of interest, for example desktop machines, parallel machines, supercomputers, and handheld devices, are encouraged.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on November 28, 2005