Geodesic
Algorithm for optimal routing in multi-service networks
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 122-127

Voir la notice de l'article provenant de la source Math-Net.Ru

The resource constrained shortest path problem (RCSP) is NP-hard extension of shortest path problem in the directed graph $G=(V,E)$. In RCSP problem, each arc $e\in E$ has a cost $w(e)$ and additional weight functions $w_r(e)$ which specify its requirements from a set of resource. Such problem allows to model a multi-service networks and search optimal route between two certain vertices. In this paper, we propose two heuristic algorithms for solving RCSP problem on big graphs. First algorithm is a modification of the famous Dijkstra's algorithm with additional labels, they allow to search the resource constrained shortest path. Unlike the known modifications, this modification does not require additional knowledge about the graph. Second algorithm adds potential functions and landmarks to the first. This modification accelerates algorithm on big graphs. Complexity of proposed algorithms corresponds to complexity of Dijkstra's algorithm. We provide computational experiments that show efficiency of proposed algorithms.
Keywords: resource constrained shortest path, big graph. 
@article{PDMA_2018_11_a37,
     author = {A. A. Soldatenko},
     title = {Algorithm for optimal routing in multi-service networks},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {122--127},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/}
}
TY  - JOUR
AU  - A. A. Soldatenko
TI  - Algorithm for optimal routing in multi-service networks
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 122
EP  - 127
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/
LA  - ru
ID  - PDMA_2018_11_a37
ER  - 
%0 Journal Article
%A A. A. Soldatenko
%T Algorithm for optimal routing in multi-service networks
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 122-127
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/
%G ru
%F PDMA_2018_11_a37
A. A. Soldatenko. Algorithm for optimal routing in multi-service networks. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 122-127. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/