# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 6 Conclusions  
This paper has proposed two new shortest path algorithms that are able to handle vertex transfer penalties without first having to perform a graph expansion. Our first method, Extended-Dijkstra-V1, exhibits an inferior growth rate compared to using [PERSON]'s algorithm on Kirby-Potts graphs; however, it has the potential to exhibit shorter run times with very sparse problem instances such as planar graphs. In contrast, our second variant Extended-Dijkstra-V2 has the same growth rate as [PERSON]'s algorithm with Kirby-Potts graphs, though in our implementations its run times do seem to be marginally higher. \begin{table}
\begin{tabular}{l r r r r r} \hline \hline \multicolumn{3}{c}{**Random Graphs**} & \multicolumn{3}{c}{**Planar Graphs**} \\ \hline  & \multicolumn{2}{c}{**Conversion Time**} & \multicolumn{2}{c}{**Conversion Time**} \\ \cline{2-6}
**Parameters** & **Mean** & **Std. dev.** & **Parameters** & **Mean** & **Std. dev.** \\ \hline \(n=1000\): & & & \(n=1000\): & & \\ \(d=0.05\), \(k=3\) & 0.006 & \(<\)0.001 & \(m=1998\), \(k=3\) & \(<\)0.001 & 0.001 \\ \(d=0.50\), \(k=3\) & 0.058 & 0.002 & \(m=9661\), \(k=3\) & 0.003 & 0.001 \\ \(d=0.95\), \(k=3\) & 0.113 & 0.001 & \(m=17,325\), \(k=3\) & 0.003 & \(<\)0.001 \\ \(d=0.05\), \(k=10\) & 0.017 & \(<\)0.001 & \(m=1998\), \(k=10\) & 0.001 & \(<\)0.001 \\ \(d=0.50\), \(k=10\) & 0.063 & 0.001 & \(m=29,781\), \(k=10\) & 0.016 & 0.002 \\ \(d=0.95\), \(k=10\) & 0.113 & 0.001 & \(m=57,564\), \(k=10\) & 0.017 & 0.001 \\ \(d=0.05\), \(k=20\) & 0.055 & 0.001 & \(m=1998\), \(k=20\) & 0.001 & 0.001 \\ \(d=0.50\), \(k=20\) & 0.108 & 0.002 & \(m=58,523\), \(k=20\) & 0.059 & 0.002 \\ \(d=0.95\), \(k=20\) & 0.162 & 0.016 & \(m=115,049\), \(k=20\) & 0.068 & 0.004 \\ \hline \(n=10,\!000\): & & & \(n=10,\!000\): & & \\ \(d=00.5\), \(k=3\) & 0.602 & 0.006 & \(m=19,\!998\), \(k=3\) & 0.008 & \(<\)0.001 \\ \(d=0.50\), \(k=3\) & 6.640 & 0.161 & \(m=96,781\), \(k=3\) & 0.028 & 0.001 \\ \(d=0.95\), \(k=3\) & 38.369 & 6.452 & \(m=173,\!565\), \(k=3\) & 0.034 & 0.001 \\ \(d=0.05\), \(k=10\) & 0.714 & 0.004 & \(m=19,\!998\), \(k=10\) & 0.009 & 0.001 \\ \(d=0.50\), \(k=10\) & 6.550 & 0.229 & \(m=298,\!341\), \(k=10\) & 0.203 & 0.006 \\ \(d=0.95\), \(k=10\) & 44.437 & 8.754 & \(m=576,\!684\), \(k=10\) & 0.232 & 0.008 \\ \(d=0.05\), \(k=20\) & 1.193 & 0.014 & \(m=19,\!998\), \(k=20\) & 0.010 & 0.001 \\ \(d=0.50\), \(k=20\) & 6.768 & 0.092 & \(m=586,\!283\), \(k=20\) & 0.689 & 0.002 \\ \(d=0.95\), \(k=20\) & 53.360 & 7.904 & \(m=1,\!152,\!569\), \(k=20\) & 0.770 & 0.016 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Number of seconds to perform Kirby-Potts expansions for random and planar graphs of differing parameters. Figures show the mean and standard deviation across twenty problem instances. During our research, we also experimented with a modified version of Extended-Dijkstra-V1 in which, when a label \((u,i)\) was marked as distinguished, all incoming edges at \(u\) with colour \(i\) were removed. The intention behind this modification was to prevent these edges from being considered more than once during the run and therefore help to improve run times. However, this method was significantly slower for two reasons: first, because a copy of the graph had to be made before each application of the algorithm; second, because of the additional costs involved in seeking and removing edges from the adjacency lists. Note that in this paper we have considered graphs in which transfer penalties \(t(u,i,j)\in T\) are static. In applications such as public transport, however, transfer penalties may also depend on the time of arrival at a vertex and the subsequent scheduled time of departure (consider trains that leave stations according to a timetabled service, for example). Previous work due to [PERSON] [PERSON] [31] and [PERSON] [32] has shown that [PERSON]'s algorithm is suitable in these time-dependent scenarios providing that the \"first-in first-out\" (FIFO) property is met.