|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
How to Employ Reverse Search in Distributed Single-Source Shortest Paths
by L. Brim, I. Cerna, P. Krcal and R. Pelanek
Abstract:
A distributed algorithm for the single-source shortest path problem for
directed graphs with arbitrary edge lengths is proposed. The new algorithm
is based on relaxations and uses reverse search for inspecting edges and
thus avoids using any additional data structures. At the same time the
algorithm uses a novel way to recognize a reachable negative-length cycle in
the graph which facilitates the scalability of the algorithm.