An efficient algorithm for perturbed shortest path problems

L. Grüne, O. Junge: An efficient algorithm for perturbed shortest path problems
in: Proceedings of the 6th International Congress on Industrial and Applied Mathematics (ICIAM 07) and GAMM Annual Meeting, Zürich, Switzerland, 2007, 1025003 - 1025004

Smart-Link: http://www.iciam07.ch/
DOI: 10.1002/pamm.200700714
Download as PDF


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.

Chair -

|  University of Bayreuth -