An efficient algorithm for perturbed shortest path problems

Titelangaben

Grüne, Lars ; Junge, Oliver:
An efficient algorithm for perturbed shortest path problems.
In: Proceedings in Applied Mathematics and Mechanics. Bd. 7 (2007) Heft 1 . - S. 1025003-1025004.
ISSN 1617-7061
DOI: https://doi.org/10.1002/pamm.200700714

Volltext

Link zum Volltext (externe URL):

Abstract

We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a min-max version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur.