TY - GEN

T1 - Constrained Shortest Path and Hierarchical Structures

AU - Ерзин, Адиль Ильясович

AU - Плотников, Роман

AU - Ладыгин, Илья Сергеевич

N1 - Conference code: 16

PY - 2023/2/5

Y1 - 2023/2/5

N2 - The Constrained Shortest Path (CSP) problem is as follows. An n-vertex graph is given, two weights are assigned to each edge: “cost” and “length”. It is required to find a min-cost bounded-length path between a given pair of vertices. 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 aggregated edge weight equals to the linear combination of the cost and length. By varying the value of the Lagrange multiplier in the linear combination, a feasible solution delivers a minimum to the objective function with new weights. At the same time, as usually, the Dijkstra’s algorithm or its modifications are used to construct a shortest path with the current weights of the edges. However, in the large graphs, this approach may turn out to be time-consuming. In this paper, we propose to search a solution, not in the original graph but in the 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 is found with O(m log n)-time complexity. In result of a priori analysis of the algorithm its accuracy estimation 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 graph of roads of megalopolis and randomly constructed metric unit-disk graphs (UDGs). The numerical experiment results show that in the HS, solution is built 10–100 times faster than in the methods which use Dijkstra’s like algorithm to build a min-weight path in the original graph.

AB - The Constrained Shortest Path (CSP) problem is as follows. An n-vertex graph is given, two weights are assigned to each edge: “cost” and “length”. It is required to find a min-cost bounded-length path between a given pair of vertices. 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 aggregated edge weight equals to the linear combination of the cost and length. By varying the value of the Lagrange multiplier in the linear combination, a feasible solution delivers a minimum to the objective function with new weights. At the same time, as usually, the Dijkstra’s algorithm or its modifications are used to construct a shortest path with the current weights of the edges. However, in the large graphs, this approach may turn out to be time-consuming. In this paper, we propose to search a solution, not in the original graph but in the 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 is found with O(m log n)-time complexity. In result of a priori analysis of the algorithm its accuracy estimation 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 graph of roads of megalopolis and randomly constructed metric unit-disk graphs (UDGs). The numerical experiment results show that in the HS, solution is built 10–100 times faster than in the methods which use Dijkstra’s like algorithm to build a min-weight path in the original graph.

KW - Complexity

KW - Constrained shortest path

KW - Hierarchical structures

KW - Polynomial algorithms

KW - Simulation

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85148487363&origin=inward&txGid=c70b00abe9bebb235487e7bfd721c7bf

UR - https://www.mendeley.com/catalogue/f1d6dc3f-5cb1-32d2-8303-bfb26f455095/

U2 - 10.1007/978-3-031-24866-5_29

DO - 10.1007/978-3-031-24866-5_29

M3 - Conference contribution

SN - 9783031248658

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 394

EP - 410

BT - Learning and Intelligent Optimization - 16th International Conference on Learning and Intelligent Optimization, Proceedings

A2 - Goos, Gerhard

A2 - Hartmanis, Juris

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th International Conference on Learning and Intelligent Optimization

Y2 - 5 June 2022 through 10 June 2022

ER -