ALCOMFT-TR-02-42

Kurt Mehlhorn, Volker Priebe, Guido Schäfer and Naveen Sivadasan
All-Pairs Shortest-Paths Computation in the Presence of Negative Cycles
MPI. Work packages 2 and 4. May 2002.

Abstract: We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(mn + n² log(n)), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance mu(v,w) between each pair v,w of vertices even in the presence of negative cycles, where mu(v,w) is defined as the infimum of the costs of all directed paths from v to w.

Postscript file: ALCOMFT-TR-02-42.ps.gz (104 kb).