When a shortest path (SP) or shortest paths tree (SPT) algorithm is used as a subprocedure of another more complex problem (e.g., the (multi-)constrained shortest path (CSP and MCSP), multi-constrained path (MCP) and the constrained minimum Steiner tree (CMST) problems), it often happens that paths with a total cost greater than a given bound are not used to determine a solution to the original problem.
As a result of the existence of these bounds, and because the Dijkstra algorithm discovers paths in increasing order of cost, we propose to stop the SP/SPT searches 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/SPT search, thereby reducing the runtime of the overlay algorithm without impacting its output. We refer to this adaptation of Dijkstra as bounded Dijkstra (BD).
We evaluate BD in the particular case of its usage for CSP algorithms. A path has to be found from a single source node to a single destination node. The goal is to find the path minimizing a given metric (usually called cost) while making sure that a second given metric (sometimes referred to as delay, or simply as the constrained metric) is lower than a given constraint bound. A solution is said feasible if it satisfies the constraint bound. Metric values are considered positive and additive.
A routing request consists of a source node, a destination node and a constraint bound value.
Out of the 19 CSP algorithms presented in our evaluation of CSP algorithms, we consider the 16 that can make use of BD. Details on how each of these algorithms can use BD and the reasons for which the others cannot can be found in Section IV of #1.
BD allows to reduce the runtime of algorithms without impact their output. As a result, for each algorithm, we evaluate the runtime impact of BD by means of the runtime ratio between the runtime of the algorithm without BD and the runtime of the algorithm with BD. For example, for a given request, a runtime ratio of 4 means that the algorithm is 4 times slower when not using BD or, alternatively, BD reduced the runtime of the algorithm by 75%.
We evaluate BD on a square grid topology by varying the following three parameters.
The impact of BD on each algorithm is evaluated along the three dimensions described here above. More details on the evaluation setup (amount of runs, requests generation, cost and delay metric values, etc.) can be found in Section V-A of #1.