DIJKSTRA-BASED ALGORITHMS FOR THE SHORTEST PATH PROBLEM WITH EDGES OF NEGATIVE LENGTH

Abstract In this paper, we propose three O(n0S(m;n)) algorithms for finding the shortest paths from a vertex in a conservative network with edges of negative length, where S(m;n) is the complexity of Dijkstra’s method for a digraph with m edges and n vertices, and n0 is the number of vertices incident to negative edges. Our study is motivated by S. Fujishige’s method, which has a running time that is similar to that of our proposed method. He dealt with the problem of, when the given length function is decreased, updating the shortest paths from all the vertices in a vertex set to all of the given vertices, which is a problem slightly different from ours. His contribution was to solve the problem by applying a simple Dijkstra’s method with less initial data than those of a previously proposed algorithm by S. Goto and A. Sangiovanni-Vincentelli. Fujishige introduced the subproblem of computing the shortest paths from a vertex v, subject to the constraint that negative edges are only contained in edges incident to v, and pointed out that the problem can be solved by consecutive applications of Dijkstra’s method to a series of such subproblems, given the length of the shortest path between each pair of vertices as prior information. Our approaches are more general purpose than Fujishige’s. In fact, ours are not limited to only updating the shortest paths, but also require no such prior information. Each of our algorithms also makes use of the concept of reduced length functions that he employed. We further show that when our algorithms incorporate an additional routine, they only apply Dijkstra’s method at most n0=2 times for a specific class of instances whose subgraphs induced by negative edges are undirected forests