Page 36 - 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. 36
e w ∈ V \ {vk}, but only go through nodes in the set Arc lengths were represented using floating-point numbers
{v1, ..., vk−1}. In order to reconstruct the shortest paths, the in both cases.
Floyd-Warshall algorithm needs to maintain an additional
matrix, which specifies the path structure. In our algorithm We performed two sets of experiments, one on random com-
this information is essential, since the path structure is used plete graphs, and one on random sparse graphs. In both
during the execution. We augment the Floyd-Warshall algo- cases, we measured two quantities: number of path combi-
rithm with a matrix L[i][j] which specifies the penultimate nations examined, and actual running time. Since the results
node on the shortest path from i to j. This suffices for re- are numbers that range from very small to very large in both
constructing the shortest path tree for all paths going out cases, we display the results as a percentage of the Floyd-
of k as follows: create n trees {T1, ..., Tn}, now go through Warshall algorithm, which is always 100% in the plots, but
j = 1 to n and place Tj as the child of TL[k][j]. This takes is not drawn explicitly.
O(n) time.
The first set of experiments was for the input of random
We then have the following algorithm: complete graphs of varying sizes. The results are shown in
Figure 1. The second set of experiments was for the input of
Algorithm 1 Single-tree Algorithm. a random graph of 1024 nodes whose number of arcs varied
from 10 − 80% where 100% = n2. To make the compari-
1: procedure Single-Tree(W ) son between Floyd-Warshall and the modified versions fairer
2: Initialize L, a n × n matrix, as L[i][j] := i. in the second set of experiments, we augmented the Floyd-
3: for k := 1 to n do Warshall algorithm with a simple modification, that allowed
4: Construct OUTk. it to skip combinations i, k where W [i][k] = ∞, which re-
5: for i := 1 to n do duced the running time and number of path combinations
6: Stack := empty examined. The results of the second set of experiments are
7: Stack.push(vk) shown in Figure 2.
8: while Stack = empty do
9: vx := Stack.pop() 4. CONCLUSIONS
10: for all children vj of vx in OUTk do
11: if W [i][k] + W [k][j] < W [i][j] then In the proposed algorithm, we can observe a significant re-
12: W [i][j] := W [i][k] + W [k][j] duction in terms of path combinations examined (see left
13: L[i][j] := L[k][j] plot of Figure 1) . This quantity dominates the algorithm’s
14: Stack.push(vj) asymptotic running time and, as observed, decreases com-
15: end if pared to the cubic algorithm when inputs grow larger. It
16: end for might be possible to obtain sub-cubic asymptotic bounds in
17: end while the average-case model. Despite this reduction in path com-
18: end for binations examined, the actual time savings shown in the
19: end for right plot of Figure 1 are more modest. A variety of factors
20: end procedure contribute to this disparity, ranging from cache performance
to implementation details that have not been thoroughly
For the sake of brevity, we omit proofs. We can augment optimized. Regardless, the speedups remain significant for
Algorithm 1 with another tree. The second tree is similar practical applications, and future work could improve this
to OUTk, except that it is the incoming shortest path for further. The experiments on sparse graphs in Figure 2 show
vk. Strictly speaking, this is not a tree1, but we can reverse a reduction in path combinations examined as the graph be-
the directions of the arcs, which turns it into a tree with comes sparser, but the effect on the running time seems to
vk as the root. The augmented algorithm is referred to as be minor.
Hourglass (as opposed to Single-tree).
Overall, the Single-tree algorithm is the simplest to imple-
3. EMPIRICAL RESULTS ment and offers good performance. The Hourglass algorithm
has the potential to be even faster, but would likely require
Our implementations were written in C and compiled with a better implementation. It is also worthwhile to note that
gcc using flags -std=c99 -O3. We ran the experiments on the additional space requirements for the Single-tree algo-
an Intel i7-2600 CPU running on Windows 7. All tests were rithm are very modest, as most applications would typically
ran 20 times and averaged. require storing the path reconstruction matrix regardless.
The input graphs were pseudorandomly generated. For com- 5. REFERENCES
plete graphs, this meant assigning each arc an indepen-
dently uniformly distributed random length in the range [1] A. Brodnik and M. Grguroviˇc. Speeding up shortest
(0, 1). Sparse graphs were generated by starting with an path algorithms. In K.-M. Chao, T. sheng Hsu, and
empty graph on 1024 nodes and adding a desired number of D.-T. Lee, editors, ISAAC, volume 7676 of Lecture
arcs, which were chosen independently according to the uni- Notes in Computer Science, pages 156–165. Springer,
form random distribution, and assigned an independently 2012.
uniformly distributed random length in the range (0, 1).
[2] T. M. Chan. More algorithms for all-pairs shortest
1The hourglass name comes from placing this structure atop paths in weighted graphs. SIAM J. Comput.,
the OUTk tree, which gives it a hourglass-like shape, with 39(5):2075–2089, 2010.
vk being the neck.
[3] C. Demetrescu and G. F. Italiano. Experimental
analysis of dynamic all pairs shortest path algorithms.
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 36
Ljubljana, Slovenia, 6 October
{v1, ..., vk−1}. In order to reconstruct the shortest paths, the in both cases.
Floyd-Warshall algorithm needs to maintain an additional
matrix, which specifies the path structure. In our algorithm We performed two sets of experiments, one on random com-
this information is essential, since the path structure is used plete graphs, and one on random sparse graphs. In both
during the execution. We augment the Floyd-Warshall algo- cases, we measured two quantities: number of path combi-
rithm with a matrix L[i][j] which specifies the penultimate nations examined, and actual running time. Since the results
node on the shortest path from i to j. This suffices for re- are numbers that range from very small to very large in both
constructing the shortest path tree for all paths going out cases, we display the results as a percentage of the Floyd-
of k as follows: create n trees {T1, ..., Tn}, now go through Warshall algorithm, which is always 100% in the plots, but
j = 1 to n and place Tj as the child of TL[k][j]. This takes is not drawn explicitly.
O(n) time.
The first set of experiments was for the input of random
We then have the following algorithm: complete graphs of varying sizes. The results are shown in
Figure 1. The second set of experiments was for the input of
Algorithm 1 Single-tree Algorithm. a random graph of 1024 nodes whose number of arcs varied
from 10 − 80% where 100% = n2. To make the compari-
1: procedure Single-Tree(W ) son between Floyd-Warshall and the modified versions fairer
2: Initialize L, a n × n matrix, as L[i][j] := i. in the second set of experiments, we augmented the Floyd-
3: for k := 1 to n do Warshall algorithm with a simple modification, that allowed
4: Construct OUTk. it to skip combinations i, k where W [i][k] = ∞, which re-
5: for i := 1 to n do duced the running time and number of path combinations
6: Stack := empty examined. The results of the second set of experiments are
7: Stack.push(vk) shown in Figure 2.
8: while Stack = empty do
9: vx := Stack.pop() 4. CONCLUSIONS
10: for all children vj of vx in OUTk do
11: if W [i][k] + W [k][j] < W [i][j] then In the proposed algorithm, we can observe a significant re-
12: W [i][j] := W [i][k] + W [k][j] duction in terms of path combinations examined (see left
13: L[i][j] := L[k][j] plot of Figure 1) . This quantity dominates the algorithm’s
14: Stack.push(vj) asymptotic running time and, as observed, decreases com-
15: end if pared to the cubic algorithm when inputs grow larger. It
16: end for might be possible to obtain sub-cubic asymptotic bounds in
17: end while the average-case model. Despite this reduction in path com-
18: end for binations examined, the actual time savings shown in the
19: end for right plot of Figure 1 are more modest. A variety of factors
20: end procedure contribute to this disparity, ranging from cache performance
to implementation details that have not been thoroughly
For the sake of brevity, we omit proofs. We can augment optimized. Regardless, the speedups remain significant for
Algorithm 1 with another tree. The second tree is similar practical applications, and future work could improve this
to OUTk, except that it is the incoming shortest path for further. The experiments on sparse graphs in Figure 2 show
vk. Strictly speaking, this is not a tree1, but we can reverse a reduction in path combinations examined as the graph be-
the directions of the arcs, which turns it into a tree with comes sparser, but the effect on the running time seems to
vk as the root. The augmented algorithm is referred to as be minor.
Hourglass (as opposed to Single-tree).
Overall, the Single-tree algorithm is the simplest to imple-
3. EMPIRICAL RESULTS ment and offers good performance. The Hourglass algorithm
has the potential to be even faster, but would likely require
Our implementations were written in C and compiled with a better implementation. It is also worthwhile to note that
gcc using flags -std=c99 -O3. We ran the experiments on the additional space requirements for the Single-tree algo-
an Intel i7-2600 CPU running on Windows 7. All tests were rithm are very modest, as most applications would typically
ran 20 times and averaged. require storing the path reconstruction matrix regardless.
The input graphs were pseudorandomly generated. For com- 5. REFERENCES
plete graphs, this meant assigning each arc an indepen-
dently uniformly distributed random length in the range [1] A. Brodnik and M. Grguroviˇc. Speeding up shortest
(0, 1). Sparse graphs were generated by starting with an path algorithms. In K.-M. Chao, T. sheng Hsu, and
empty graph on 1024 nodes and adding a desired number of D.-T. Lee, editors, ISAAC, volume 7676 of Lecture
arcs, which were chosen independently according to the uni- Notes in Computer Science, pages 156–165. Springer,
form random distribution, and assigned an independently 2012.
uniformly distributed random length in the range (0, 1).
[2] T. M. Chan. More algorithms for all-pairs shortest
1The hourglass name comes from placing this structure atop paths in weighted graphs. SIAM J. Comput.,
the OUTk tree, which gives it a hourglass-like shape, with 39(5):2075–2089, 2010.
vk being the neck.
[3] C. Demetrescu and G. F. Italiano. Experimental
analysis of dynamic all pairs shortest path algorithms.
StuCoSReC Proceedings of the 2015 2nd Student Computer Science Research Conference 36
Ljubljana, Slovenia, 6 October
