Experimental
Evaluation of Dynamic All Pairs Shortest Path Algorithms
Camil Demetrescu, Stefano
Emiliozzi, and Giuseppe
F. Italiano
| Introduction | ||
| This page is intended as an electronic companion of the paper: Experimental Evaluation of Dynamic All Pairs Shortest Path Algorithms, by Camil Demetrescu, Stefano Emiliozzi, and Giuseppe F. Italiano, Technical Report ALCOM-FT, ALCOMFT-TR-03-9 [download pdf, 212KB]. Here we provide the full software package (dsp-1.0) used in the experimental work, which includes: | ||
| C implementations of several static and dynamic algorithms for single-source and all-pairs shortest path problems | ||
| Generators of random and hard inputs | ||
| Real test sets in Dimacs and XML format, including: | ||
| Internet networks obtained from data collected in the University of Oregon Route Views Archive Project | ||
| US road networks obtained from data collected in the U.S. Geological Survey Digital Line Graphs | ||
| An interactive driver program for running the implemented algorithms | ||
| Scripts for running the experiments described in the paper | ||
| HTML documentation of all the implemented components | ||
| The software package is implemented in ISO89 C and is based on the Leonardo Library (LL). | ||
| License |
| The source code of dsp-1.0 is distributed under the terms of the GNU Lesser General Public License (LGPL). |
| Download |
| Download full dsp-1.0 software package, http, tar.gz, 4MB [README] [LICENSE] (the package includes portions of the Leonardo Library) |
| Documentation of main components | ||
| CAPSP | (S-DIJ) | Static all-pairs shortest paths based on Dijkstra's algorithm |
| LSP | (S-UP) | Static all-pairs shortest paths based on Demetrescu/Italiano's uniform paths algorithm |
| CDAPSP | (D-KIN) | Fully dynamic all-pairs shortest paths based on King's algorithm |
| CDAPSP_DE | (D-RRL) | Fully dynamic all-pairs shortest paths based on Ramalingam/Reps' algorithm |
| LDSP | (D-PUP) | Fully dynamic all-pairs shortest paths based on Demetrescu/Italiano's potentially uniform paths algorithm |
| CSSSP | Static single-source shortest paths based on Dijkstra's algorithm | |
| CDSSSP | Fully dynamic single-source shortest paths based on Ramalingam/Reps' algorithm | |
| CDAPSP_D | Fully dynamic all-pairs shortest paths (up to distance D) based on King's algorithm | |
| Increase-only dynamic single-source shortest paths (up to distance D) based on King's algorithm | ||
| Page maintained by Camil Demetrescu - Last updated: July 6, 2003 - [an error occurred while processing this directive] |