## Optimal Paths in Weighted Timed Automata

*Rajeev Alur, Salvatore La Torre, and George Pappas*
We consider the *shortest-path problem* for a timed
automaton with respect to a linear cost function which
results in a *weighted timed automaton*.
Our solution to this problem consists of reducing
this optimization problem to a (parametric)
shortest-path problem in a finite directed graph.
Such a reduction consists of a graph construction which
refines the region automaton construction due to Alur and Dill.
We present an exponential time algorithm to solve the
shortest-path problem for weighted timed automata starting from
a single state, and a doubly-exponential time algorithm to solve this
problem starting from a zone of the state space.

*Hybrid Systems: Computation and Control,
Proceedings of the Fourth International Conference*,
(HSCC'01),
Lecture Notes in Computer Science 2034, pp. 49--62, Springer, 2001.