, Running time (ms), SB* vs

, Running time (ms), PSB vs. SB (c) Nbr. of stored trees

, SB vs. SB* (e) Running time (ms), SB vs. PSB (f) Nbr. of stored trees, PSB vs. SB FIGURE 1: Comparison of the running time of SB versus SB* (Fig. 1a) and SB versus PSB (Fig. 1b) on Rome

, All computations have been done on a computer equipped with 2 quad-core 3.20GHz Intel Xeon W5580 processors and 64GB of RAM. Our simulations show that our improvement SB* of SB algorithm allows to decrease the running-time by a factor between 1,5 and 2 in average. In particular, for both networks, SB* algorithm is, for most of the queries, faster than SB algorithm (Figures (1a) and (1d)). The simulations comparing PSB and SB algorithms show a significant reduction of the working memory (number of stored trees) when using PSB (Figures (1c) and (1f)). In term of running time, SB algorithm is slightly faster in average but Figures (1b) and (1e) indicate that globally, Fig. 1d and Fig. 1e on Colorado), and comparison of the number of stored trees for SB versus PSB (Fig. 1c) on Rome, (resp. Fig. 1f on Colorado)

C. Demetrescu, A. Goldberg, and D. Johnson,

D. Eppstein, Finding the k shortest paths, SIAM Journal on Computing, vol.28, issue.2, pp.652-673, 1998.

G. Feng, Finding k shortest simple paths in directed graphs : A node classification algorithm, Networks, vol.64, issue.1, pp.6-17, 2014.

D. Kurz and P. Mutzel, A sidetrack-based algorithm for finding the k shortest simple paths in a directed graph, Int. Symp. on Alg. and Comp. (ISAAC), vol.64, pp.1-49, 2016.

J. Y. Yen, Finding the k shortest loopless paths in a network, Management Science, vol.17, issue.11, pp.712-716, 1971.