Shortest paths in a diagraph with an underestimated arc weight

Authors

  • L. Ciupala Transilvania University of Brasov, Romania
  • A. Deaconu Transilvania University of Brasov, Romania
  • L. Majercsik Transilvania University of Brasov, Romania

DOI:

https://doi.org/10.31926/but.mif.2022.2.64.1.13

Keywords:

graph algorithms, shortest paths, incremental algorithms

Abstract

There are many real-world problems that can be modeled and solved as shortest path problems. Among them, single-pair shortest path problems appear most frequently. Sometimes the weighted digraph, in which the shortest path problem is stated, suffers a minor data change (for instance, an arc weight might increase by a given amount a) due to the changes occurring in the corresponding real-life problem. In this case, one needs to solve the shortest path problem in the modified digraph. If shortest paths are already determined in the initial digraph, these can be used as a starting point when determining shortest paths in the modified digraph or a known shortest path algorithm can be applied, from scratch, in the modified digraph. We will describe an algorithm that determines the shortest paths from a given source node s in the new weighted digraph starting from the already known shortest paths in the original weighted digraph.

Author Biographies

L. Ciupala, Transilvania University of Brasov, Romania

Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science

A. Deaconu, Transilvania University of Brasov, Romania

Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science

L. Majercsik, Transilvania University of Brasov, Romania

Faculty of Mathematics and Computer Science

Downloads

Published

2022-07-06

Issue

Section

COMPUTER SCIENCE