An algorithm for the solution of shortest path problems with positive and negative arc lengths

One of the most successful methods for the one-to-all shortest path problem in a directed graph is Dijkstra's method. If m is the number of arcs and n is the number of nodes of the graph there are implementations with worst case complexity 0(m + n log n) . Unfortunately this method can only be applied on graphs with nonnegative arc lengths, or costs, while sometimes, for instance if traversing some arcs yields income and therefore has negative costs, an algorithm for one-to-all shortest path problems with arbitrary arc lengths is needed. In this paper a method is described for graphs with arbitrary arc lengths. It can be considered as an extension of Dijkstra's method, using this method in two ways: for the transformation of the problem into a problem with only nonnegative arc lengths and for the solution of this new problem. The transformation is made through the solution of a linear assignment problem. If r is the number of nodes which are tails of one or more arcs with negative
length, this assignment problem can be solved by applying Dijkstra's method at most r times on small subproblems. So the worst case complexity of the problem is 0((r +1) (m + n log n)) if the algorithm described in this paper is applied. The numerical results suggest that at the moment other existing methods solve these problems in shorter computation times.