Scaling Algorithms for the Shortest Paths Problem

摘要

In this paper the authors study the shortest paths problem where arc lengths canbe both positive and negative. This is a fundamental combinatorial optimization problem that often comes up in applications and as a subproblem in algorithms for many network problems. The authors assume that the length function is integral, as is the case in most applications.