# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 5 Computational Comparison
### Public Transport Graphs
\begin{table}
\begin{tabular}{l r r r r r r r} \hline \hline  & \multicolumn{4}{c}{**Original Instances (No Walking)**} & \multicolumn{4}{c}{**With 1 km Walks**} \\ \cline{2-9}
**City** & \(n\) & \(k\) & \(c_{\text{max}}^{-}\) & \(c_{\text{max}}^{+}\) & \(\bar{\chi}\) & \(m\) & \(m\) \\ \hline London Underground & 302 & 13 & 6 & 6 & 9 * & 812 \({}^{\dagger}\) & 812 \({}^{\dagger}\) \\ Kuopio & 549 & 33 & 13 & 13 & 18 * & 1626 & 10,436 \\ Antofagasta & 650 & 17 & 14 & 14 & 16 * & 2547 & 26,291 \({}^{\dagger}\) \\ Luxembourg & 1367 & 222 & 59 & 59 & 77 * & 6163 & 18,153 \({}^{\dagger}\) \\ Rennes & 1407 & 50 & 7 & 7 & 8 * & 2159 & 29,219 \({}^{\dagger}\) \\ Grenoble & 1547 & 52 & 4 & 4 & 5 * & 1943 & 37,529 \({}^{\dagger}\) \\ Turku & 1850 & 103 & 35 & 35 & 35 * & 7080 & 54,230 \\ Venice & 1874 & 873 & 90 & 90 & 90 * & 16,561 & 42,983 \\ Belfast & 1917 & 102 & 31 & 27 & 31 * & 6041 & 64,635 \({}^{\dagger}\) \\ Palermo & 2176 & 94 & 17 & 17 & 17 * & 5298 \({}^{\dagger}\) & 91,962 \({}^{\dagger}\) \\ Nantes & 2353 & 97 & 9 & 8 & 9 * & 4080 & 58,130 \\ Canberra & 2764 & 123 & 35 & 35 & 38 & 7121 & 57,687 \({}^{\dagger}\) \\ Toulouse & 3329 & 104 & 9 & 9 * & 5067 & 78,557 \({}^{\dagger}\) \\ Bordeaux & 3435 & 81 & 8 & 8 & 9 * & 5829 & 91,087 \({}^{\dagger}\) \\ Dublin & 4571 & 143 & 23 & 23 & 25 & 12,165 & 132,729 \\ Berlin & 4601 & 575 & 59 & 59 & 60 & 22,922 & 59,108 \\ Winnipeg & 5079 & 90 & 33 & 33 & 40 * & 10,642 & 211,124 \({}^{\dagger}\) \\ Prague & 5147 & 356 & 21 & 21 & 24 * & 14,807 & 90,035 \\ Detroit & 5683 & 40 & 8 & 8 & 8 * & 6460 & 195,584 \({}^{\dagger}\) \\ Athens & 6768 & 240 & 18 & 18 & 18 * & 14,741 & 259,923 \({}^{\dagger}\) \\ Helsinki & 6986 & 498 & 64 & 64 & 64 * & 27,718 & 223,382 \\ Lisbon & 7073 & 868 & 32 & 29 & 33 * & 23,354 & 243,792 \({}^{\dagger}\) \\ Adelaide & 7548 & 517 & 82 & 82 & 82 * & 32,018 & 197,062 \({}^{\dagger}\) \\ Rome & 7869 & 337 & 17 & 17 & 18 * & 19,164 & 287,964 \\ Brisbane & 9645 & 401 & 60 & 60 & 60 * & 20,849 & 249,537 \\ Paris & 11,950 & 878 & 10 & 10 & 11 & 20,810 & 511,248 \({}^{\dagger}\) \\ Melbourne & 19,493 & 405 & 18 & 18 & 18 * & 28,738 & 498,084 \\ Sydney & 24,063 & 736 & 42 & 42 & 50 & 55,616 & 714,902 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of the 28 real-world problem instances. In columns indicating the number of edges \(m\), daggers (\(\dagger\)) indicate strongly connected graphs. For instances with 1 km walks, an extra edge colour is required, meaning that \(k\) and \(\bar{\chi}\) should be incremented by one. The meaning of the asterisks (\({}^{\bullet}\)) is described in the text. Finally, Table 2 also contains information on the _minimum_ number of colours \(\bar{\chi}\) needed to represent these graphs, as explained in Section 3.3. In all cases \(\bar{\chi}\) is less than \(k\); quite drastically so with some of the larger instances such as Paris, Melbourne and Sydney. These figures were gained by converting the transport networks into conflicts graphs and then running a backtracking version of the DSatur heuristic for graph colouring for a maximum of one hour per instance [26; 30]. Asterisks in Table 2 indicate the proven minimum number of colours for these graphs (the chromatic number). All other figures are upper bounds on this number. The charts in Figure 10 summarise the results with these instances. In the majority of cases, the use of [PERSON]'s algorithm with Kirby-Potts graphs gives the shortest average run times. Run times of our extended algorithms are therefore stated as a proportion of these times. (A proportion increase of one indicates a 100% increase in run time). As shown, when walks between access points are not included in the graphs, their relative sparsity allows Extended-Dijkstra-V1 to execute run more quickly than V2 in nearly all cases. However, once walks of up to 1 km are included, the increased density sees V2 running more quickly. Figure 10: Comparison of run times for the real-world problem instances allowing no walks (**top**), and walks of up to 1 km (**bottom**).