Page 35 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2015 2nd Student Computer Science Research Conference. Koper: University of Primorska Press, 2015
P. 35
ng trees to speed up the Floyd-Warshall algorithm
Marko Grgurovicˇ
UP DIST
University of Primorska
marko.grgurovic@famnit.upr.si
ABSTRACT in such networks is a classic problem in algorithmic graph
theory. Two of the most common variants of the problem are
A classic problem in algorithmic graph theory is to find the single-source shortest path (SSSP) problem and the all-
shortest paths, and a common variant is the all-pairs short- pairs shortest path problem (APSP). In the SSSP variant,
est path problem (APSP). We consider non-negatively weighted we are tasked with finding the path with the least total
APSP. Due to its simplicity and efficiency, the Floyd-Warshall length from a fixed node s ∈ V to every other node in the
algorithm is frequently used to solve APSP in practice. network. Similarly, the APSP problem asks for the shortest
path between every pair of nodes u, v ∈ V . In this paper we
We propose a combination of the Floyd-Warshall algorithm will focus exclusively on the APSP variant of the problem.
with a hourglass-like tree structure, which reduces the num-
ber of path combinations that have to be examined. Only The asymptotically fastest APSP algorithm for dense graphs
those path combinations that provably cannot change the runs in O(n3 log log3 n/ log2 n) time [2]. For non-negative
values in the shortest path matrix are omitted. The result- arc length functions and for sparse graphs, there exist asymp-
ing algorithm is simple to implement and uses no fancy data totically fast algorithms for worst case inputs [10, 12, 11],
structures. and algorithms which are efficient average-case modifications
of Dijkstra’s algorithm [6, 3, 9]. In fact, it turns out that
In empirical tests, the new algorithm is faster than the Floyd- any SSSP algorithm can be asymptotically sped up in the
Warshall algorithm for random complete graphs on 256 − average-case setting when solving APSP [1].
4096 nodes by factors of 3.5 − 4.8x. When we inspect the
number of path combinations examined compared to the In practice, the Floyd-Warshall algorithm is frequently used,
Floyd-Warshall algorithm, they are reduced by a factor of along with variations of Dijkstra’s algorithm when the graph
12 − 90x. All code was written in C. is sparse. One can also approach APSP through funny ma-
trix multiplication, and practical improvements have been
Categories and Subject Descriptors devised to this end through the use of sorting [8]. There exist
many optimizations for the Floyd-Warshall algorithm, rang-
F.2.2 [Theory of Computation]: Nonnumerical Algorithms ing from better cache performance [13], optimized program-
and Problems generated code [4], to parallel variants for the GPU [5, 7].
General Terms In spite of intensive research on efficient implementations
of the Floyd-Warshall algorithm, the authors are not aware
Algorithms, Theory of any improvement to the number of path combinations
examined by the algorithm. In this paper, we propose a
Keywords modification of the Floyd-Warshall algorithm that combines
it with a hourglass-like tree structure, which reduces the
Dynamic programming, shortest path number of paths that have to be examined. Only those path
combinations that provably cannot change the values in the
1. INTRODUCTION shortest path matrix are omitted. The resulting algorithm
is simple to implement, uses no fancy data structures and
Let N = (V, A, ) be a directed network where we refer to in our tests is faster than the Floyd-Warshall algorithm for
V = {v1, v2, ..., vn} as the set of nodes and A as the set random complete graphs on 256 − 4096 nodes by factors
of arcs (directed edges). To simplify notation we will write ranging from 2.5−8.5x. When we inspect the number of path
|V | = n and |A| = m. The function : A → R maps combinations examined however, our modification reduces
arcs to (possibly negative) lengths. Finding shortest paths the number by a staggering factor of 12 − 90x.
2. ALGORITHM
The simplest improvement over Floyd-Warshall involves the
use of a tree, denoted as OUTk, which is the shortest path
tree containing paths that begin in node vk and end in some
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 35
Ljubljana, Slovenia, 6 October
Marko Grgurovicˇ
UP DIST
University of Primorska
marko.grgurovic@famnit.upr.si
ABSTRACT in such networks is a classic problem in algorithmic graph
theory. Two of the most common variants of the problem are
A classic problem in algorithmic graph theory is to find the single-source shortest path (SSSP) problem and the all-
shortest paths, and a common variant is the all-pairs short- pairs shortest path problem (APSP). In the SSSP variant,
est path problem (APSP). We consider non-negatively weighted we are tasked with finding the path with the least total
APSP. Due to its simplicity and efficiency, the Floyd-Warshall length from a fixed node s ∈ V to every other node in the
algorithm is frequently used to solve APSP in practice. network. Similarly, the APSP problem asks for the shortest
path between every pair of nodes u, v ∈ V . In this paper we
We propose a combination of the Floyd-Warshall algorithm will focus exclusively on the APSP variant of the problem.
with a hourglass-like tree structure, which reduces the num-
ber of path combinations that have to be examined. Only The asymptotically fastest APSP algorithm for dense graphs
those path combinations that provably cannot change the runs in O(n3 log log3 n/ log2 n) time [2]. For non-negative
values in the shortest path matrix are omitted. The result- arc length functions and for sparse graphs, there exist asymp-
ing algorithm is simple to implement and uses no fancy data totically fast algorithms for worst case inputs [10, 12, 11],
structures. and algorithms which are efficient average-case modifications
of Dijkstra’s algorithm [6, 3, 9]. In fact, it turns out that
In empirical tests, the new algorithm is faster than the Floyd- any SSSP algorithm can be asymptotically sped up in the
Warshall algorithm for random complete graphs on 256 − average-case setting when solving APSP [1].
4096 nodes by factors of 3.5 − 4.8x. When we inspect the
number of path combinations examined compared to the In practice, the Floyd-Warshall algorithm is frequently used,
Floyd-Warshall algorithm, they are reduced by a factor of along with variations of Dijkstra’s algorithm when the graph
12 − 90x. All code was written in C. is sparse. One can also approach APSP through funny ma-
trix multiplication, and practical improvements have been
Categories and Subject Descriptors devised to this end through the use of sorting [8]. There exist
many optimizations for the Floyd-Warshall algorithm, rang-
F.2.2 [Theory of Computation]: Nonnumerical Algorithms ing from better cache performance [13], optimized program-
and Problems generated code [4], to parallel variants for the GPU [5, 7].
General Terms In spite of intensive research on efficient implementations
of the Floyd-Warshall algorithm, the authors are not aware
Algorithms, Theory of any improvement to the number of path combinations
examined by the algorithm. In this paper, we propose a
Keywords modification of the Floyd-Warshall algorithm that combines
it with a hourglass-like tree structure, which reduces the
Dynamic programming, shortest path number of paths that have to be examined. Only those path
combinations that provably cannot change the values in the
1. INTRODUCTION shortest path matrix are omitted. The resulting algorithm
is simple to implement, uses no fancy data structures and
Let N = (V, A, ) be a directed network where we refer to in our tests is faster than the Floyd-Warshall algorithm for
V = {v1, v2, ..., vn} as the set of nodes and A as the set random complete graphs on 256 − 4096 nodes by factors
of arcs (directed edges). To simplify notation we will write ranging from 2.5−8.5x. When we inspect the number of path
|V | = n and |A| = m. The function : A → R maps combinations examined however, our modification reduces
arcs to (possibly negative) lengths. Finding shortest paths the number by a staggering factor of 12 − 90x.
2. ALGORITHM
The simplest improvement over Floyd-Warshall involves the
use of a tree, denoted as OUTk, which is the shortest path
tree containing paths that begin in node vk and end in some
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 35
Ljubljana, Slovenia, 6 October
