  The shortest path (SP) and shortest paths tree (SPT) problems arise both as
direct applications and as subroutines of overlay algorithms solving more
complex problems such as the constrained shortest path (CSP) or the constrained
minimum Steiner tree (CMST) problems. Often, such algorithms do not use the
result of an SP subroutine if its total cost is greater than a given bound. For
example, for delay-constrained problems, paths resulting from a least-delay SP
run and whose delay is greater than the delay constraint of the original
problem are not used by the overlay algorithm to construct its solution. As a
result of the existence of these bounds, and because the Dijkstra SP algorithm
discovers paths in increasing order of cost, we can terminate the SP search
earlier, i.e., once it is known that paths with a greater total cost will not
be considered by the overlay algorithm. This early termination allows to reduce
the runtime of the SP subroutine, thereby reducing the runtime of the overlay
algorithm without impacting its final result. We refer to this adaptation of
Dijkstra for centralized implementations as bounded Dijkstra (BD). On the
example of CSP algorithms, we confirm the usefulness of BD by showing that it
can reduce the runtime of some algorithms by 75% on average.
