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.