The shortest path problem in a graph for an executor with limited resources

Abstract

The article highlights Dijkstra’s algorithm, the possibility of its modification and a generalized vision of the modifications’ possibility. Attention was especially paid to the analysis of the problem of finding the shortest path with limited resources. The research is performed in order to expand the vision of the application possibilities of the Floyd's and Dijkstra’s algorithms with additional parameters. At the same time, various generalizations of the shortest path problem are rarely considered. The purpose of this paper is to draw the attention of scientists and university professors to one of the natural generalizations of the problem. Related problems using a multi-source algorithm were explored by Shiming Wang when investigating the paths of road networks to reduce the time spent between stops , Peter W. Eklund's work on modifying the algorithm, which includes static and dynamic heuristic components and several source nodes. The modified algorithm is applied in a 3D Spatial Information System (SIS) for routing emergency service vehicles. Our generalization is that we consider an executor of the algorithm (wayfarer) with limited resources that are being spent on the way these resources can be replenished in some vertices of the graph. It is required to find the shortest path along which the executor can reach the target vertex correctly spending and replenishing his resources. Along with these algorithms, some of their special cases are also considered. For example, it is directed graph transitive closure algorithm. Furthermore, the formulation of the shortest path problem is presented as a problem of matrix multiplication over closed semirings. The paper considers generalizations of the Floyd's and Dijkstra's algorithms for the case of both a single limited resource and multiple resources.