Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths
by
Luboš Brim,
Ivana Černá,
Pavel Krčál,
Radek Pelánek,
This is a full version of the paper presented at FST&TCS 2001. May 2001, 19 pages.
FIMU-RS-2001-01.
Available as Postscript,
PDF.
Abstract:
A distributed algorithm for single source shortest path
problem in an
arbitrary directed graph which can contain negative length cycles is
presented. The new algorithm is a label-correcting one and uses a novel
way for detection of negative length cycles. It works on a network of
processors with disjoint memory that communicate via message passing.
Correctness of the algorithm is proved. The algorithm is work-efficient as
its worst time complexity is O(n^3/p), where p is the number of processors.