# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 4 Methods Avoiding Expansion
### Extended Dijkstra Version 2  
Our second adaptation operates by replicating the behaviour of [PERSON]'s algorithm on Kirby-Potts graphs. This results in a method with the more favourable growth rate of \(f_{2}\) but that also avoids the need for graph expansion. To do this, approximately twice as much working memory as Extended-Dijkstra-V1 is required because, in addition to storing values for each vertex/in-colour pair, we also need to store values for each vertex/out-colour pair. The structures \(L\), \(D\) and \(P\) are therefore replaced with the structures \(L_{\text{in}}\) and \(L_{\text{out}}\), \(D_{\text{in}}\) and \(D_{\text{out}}\), and \(P_{\text{in}}\) and \(P_{\text{out}}\).  
The complete procedure for Extended-Dijkstra-V2 is given in Algorithm 4. Note that each item in the priority queue \(Q\) is now a tuple comprising four values. The fourth value indicates whether the item refers to an \"in-label\" or and \"out-label\", which correspond to in-vertices and out-vertices in a Kirby-Potts graph. The item \((u,i,x,\textsc{IN})\in Q\) means that we are considering the vertex \(u\), incoming edges of colour \(i\)  
Figure 6: Comparison of growth rates \(f_{1}\) and \(f_{2}\) with regards to the number of edges \(m\). Rows show \(n\)-values of 100, 1000 and 10,000 respectively; columns consider values \(c_{\max}^{-}=c_{\max}^{+}\) of 3, 10, and 20 respectively.  
and that \(L_{\text{in}}(u,i)=x\). Similarly, \((u,i,x,\text{OUT})\in Q\) means we are considering vertex \(u\), outgoing edges of colour \(i\), and that \(L_{\text{out}}(u,i)=x\).
```
Extended Dijkstra-V2 \((s\in V,l\in C^{-}(s))\)  for all\(v\in V\)  for all\(i\in C^{-}(v)\)  Set \(L_{\text{in}}(v,i)=\infty\); \(D_{\text{in}}(v,i)=\textbf{false}\); and \(P_{\text{in}}(v,i)=\textsc{null}\)  for all\(i\in C^{+}(v)\)  Set \(L_{\text{out}}(v,i)=\infty\); \(D_{\text{out}}(v,i)=\textbf{false}\); and \(P_{\text{out}}(v,i)=\textsc{null}\)  Set \(L_{\text{in}}(s,l)=0\) and \(Q=\{(s,l,L_{\text{in}}(s,l),\textsc{IN})\}\) while\(Q\
eq\varnothing\)  Let \((u,i,x,y)\) be the element in \(Q\) with minimum value for \(x\)  Remove \((u,i,x,y)\) from \(Q\)  if \((y=\textsc{IN})\) then  Set \(D_{\text{in}}(u,i)=\textbf{true}\) for all\(j\in C^{+}(u)\) such that \(D_{\text{out}}(u,j)=\textbf{false}\) if\(L_{\text{in}}(u,i)+t(u,i,j)<L_{\text{out}}(u,j)\)then  if\(L_{\text{out}}(u,j)\
eq\infty\)then remove \((u,j,L_{\text{out}}(u,j),\textsc{OUT})\) from \(Q\)  Set \(L_{\text{out}}(u,j)=L_{\text{in}}(u,i)+t(u,i,j)\); \(P_{\text{out}}(u,j)=(u,i)\); and insert \((u,j,L_{\text{out}}(u,j),\textsc{OUT})\) into \(Q\) else  Set \(D_{\text{out}}(u,i)=\textbf{true}\) for all\((u,v,i)\in E^{+}(u)\) such that \(j=i\) and \(D_{\text{in}}(v,i)=\textbf{false}\) if\(L_{\text{out}}(u,i)+w(u,v,i)<L_{\text{in}}(v,i)\)then  if\(L_{\text{in}}(v,i)\
eq\infty\)then remove \((v,i,L_{\text{in}}(v,i),\textsc{IN})\) from \(Q\)  Set \(L_{\text{in}}(v,i)=L_{\text{out}}(u,i)+w(u,v,i)\); \(P_{\text{in}}(v,i)=(u,i)\); and insert \((v,i,L_{\text{in}}(v,i),\textsc{IN})\) into \(Q\)
```  
**Algorithm 4** The extended Dijkstra algorithm, version 2.  
As shown in Algorithm 4, items are selected and removed from the priority queue \(Q\) on Lines 8 and 9. If the selected item \((u,i,x,y)\) refers to an in-label (\(y=\textsc{in}\)), then only labels referring to the outgoing colours of vertex \(u\) need to be considered for update; hence, we only need to look at the transfer penalties \(t(u,i,j)\) for \(j\in C^{+}(u)\) in which \(D_{\text{out}}(u,j)\) is not distinguished (Lines 12 to 15). Similarly, if \((u,i,x,y)\) refers to an out-label (\(y=\textsc{out}\)), then we only need to consider updating the in-labels of any vertex \(v\) connected to \(u\) by an edge of colour \(i\) (Lines 18 to 21). This behaviour is identical to the way in which [PERSON] would operate with a Kirby-Potts expanded version of the graph.