Summer School on Shortest Paths -
Between Algorithms and Optimization

This summer school on shortest paths will span theory, practice, and applications in optimization problems. We will cover single source and all pairs shortest paths in directed and undirected graphs; with exact and approximate solutions; combinatorial techniques, the use of matrix multiplication, and exploiting integer weights; fast generation of distance oracles; dynamic versions where distances are quickly recomputed when the graph updated; and various NP-hard variants of shortest path problems. Finally, we will give an overview on how shortest paths are used as subproblems in other combinatorial optimization problems.

The summer school will be held at DIKU, University of Copenhagen on July 4-8, 2005. State-of-the-art lectures will be given by the foremost researchers in the field, ensuring a proper balance between algorithms and optimization. The lectures will be supplemented by exercises and discussions.

The next DIMACS implementation challenge will be on shortest paths. The summer school is expected to generate interesting projects on meeting this challenge.


Program and Literature

The program for the summer school is available here. A list of recommended literature is available here.


Some pictures from the Summer School have been put on the following page.

Getting to the Summer School

The school takes place in Auditorium 1, Universitetspaken 13, Copenhagen. The following map shows the location: Map. Registration takes place Monday, July 4, from 9.00 to 9.45.

From downtown Copenhagen you may take bus 42, 185, S150 (from Nørreport) or bus 15 (from Østerport).


Due to an extraordinary interest in this summer school, we have passed the limit on the number of participants. Therefore, registration was closed on April 19, 2005.

Hotel reservation

Participants must organize accommodation themselves. Accommodation is not included in the registration fee.

We recommend the following hotels:

Cab Inn
Ibsens Hotel
Comfort Hotel Østerport
More hotels and general visiting information on the Copenhagen area may be found at Wonderful Copenhagen and at

Program and Organizing Committee


Last Update: June 24, 2005 by David Pisinger/ Martin Zachariasen.