  The Constraint Shortest Path (CSP) problem is as follows. An $n$-vertex graph
is given, each edge/arc assigned two weights. Let us call them "cost" and
"length" for definiteness. Finding a min-cost upper-bounded length path between
a given pair of vertices is required. The problem is NP-hard even when the
lengths of all edges are the same. Therefore, various approximation algorithms
have been proposed in the literature for it. The constraint on path length can
be accounted for by considering one edge weight equals to a linear combination
of cost and length. By varying the multiplier value in a linear combination, a
feasible solution delivers a minimum to the function with new weights. At the
same time, Dijkstra's algorithm or its modifications are used to construct the
shortest path with the current weights of the edges. However, with
insufficiently large graphs, this approach may turn out to be time-consuming.
In this article, we propose to look for a solution, not in the original graph
but specially constructed hierarchical structures (HS). We show that the
shortest path in the HS is constructed with $O(m)$-time complexity, where $m$
is the number of edges/arcs of the graph, and the approximate solution in the
case of integer costs and lengths of the edges is found with $O(m\log n)$-time
complexity. The a priori estimate of the algorithm's accuracy turned out to
depend on the parameters of the problem and can be significant. Therefore, to
evaluate the algorithm's effectiveness, we conducted a numerical experiment on
the graphs of roads of megalopolis and randomly constructed unit-disk graphs
(UDGs). The numerical experiment results show that in the HS, a solution close
to optimal one is built 10--100 times faster than in the methods which use
Dijkstra's algorithm to build a min-weight path in the original graph.
