Speeding up dynamic shortest path lorithms

"Speeding up dynamic shortest path algorithms"

published in INFORMS J. on Computing

We provide here online supplementary material for the paper

"Speeding up dynamic shortest path algorithms".

This material includes all C language source code for all dynamic shortest path algorithms described in the paper, C language source code of Dijkstra's algorithm used in the experiments, scripts used to run the experiments, pseudo-codes for all algorithms whose pseudo-codes are not provided in the paper, and tables with detailed computational results of the random and unit arc weight increase experiments.

Pseudo-codes and tables are displayed as PDF files. [ Download a free PDF Reader from Adobe ]

[ Download the C-language source code for the shortest path algorithms and scripts for running the experiments. ]
Read README file for more detail. The DSP algorithms are in file DSPalgorithms.h.

[ Download the C-language source code for Goldberg's shortest path problem instance generators. ]

[ View the PDF file of the tables with the experimental results for random arc weight changes. ]

[ View the PDF file of the tables with the experimental results for unit arc weight changes. ]

Click on the algorithm name to view pseudo-code with discussion:

Pseudo-codes for dynamic SP algorithms	Standard (std)	Reduced heap (rh)
Increase	stdT₊^RR	rhT₊^RR
	stdT₊^KT	rhT₊^KT
	stdT₊^D	rhT₊^D
Decrease	stdT_-^RR	rhT_-^RR
Decrease	stdT_-^KT	rhT_-^KT

Online supplementary material for the paper

"Speeding up dynamic shortest path algorithms"