  The shortest path problem in graphs is fundamental to AI. Nearly all variants
of the problem and relevant algorithms that solve them ignore edge-weight
computation time and its common relation to weight uncertainty. This implies
that taking these factors into consideration can potentially lead to a
performance boost in relevant applications. Recently, a generalized framework
for weighted directed graphs was suggested, where edge-weight can be computed
(estimated) multiple times, at increasing accuracy and run-time expense. We
build on this framework to introduce the problem of finding the tightest
admissible shortest path (TASP); a path with the tightest suboptimality bound
on the optimal cost. This is a generalization of the shortest path problem to
bounded uncertainty, where edge-weight uncertainty can be traded for
computational cost. We present a complete algorithm for solving TASP, with
guarantees on solution quality. Empirical evaluation supports the effectiveness
of this approach.
