# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 4 Methods Avoiding Expansion
### Extended Dijkstra Version 1  
Our first adaptation, Extended-Dijkstra-V1, is given in Algorithm 3. The rationale for this method can be explained by considering a cluster of dummy vertices in a Kirby-Potts expanded graph. As previously noted, vertices in each cluster of the expanded graph can be partitioned into two sets: in-vertices and out-vertices (see Figure 2(a),b). Moreover, observe that a shortest path from an in-vertex must always next pass through an out-vertex from the same cluster before moving to a different cluster. As proven in Theorem 1 below, it is therefore sufficient to simply add the length of the corresponding transfer (edge) to the path here, rather than consider the out-vertices as separate entities within the graph. The idea in our approach is to therefore use a pair \((u,i)\) for each vertex \(u\in V\) and incoming colour \(i\in C^{-}(u)\), giving \(\sum_{u\in V}|C^{-}(u)|\) pairs in total. The source is also defined by such a pair \((s,l)\), which is interpreted as meaning that the paths should start at \(s\in V\), assuming initial entry to \(s\) on an edge of colour \(l\). Similarly to the Dijkstra procedure of Algorithm 1, during execution this algorithm stores labels, predecessors and the distinguished status of each pair using the data structures \(L\), \(P\) and \(D\) respectively. At termination, all pairs reachable from the source are marked as distinguished, and the label \(L(u,i)\) holds the length of the shortest path from the source to vertex \(u\), assuming entry at \(u\) on an edge of colour \(i\). An example solution from this method is shown in Figure 5. The main differences between this approach and Dijkstra are (a) the use of vertex-colour pairs, and (b) at Lines 11 and 13 of Extended-Dijkstra-V1, where transfer penalties \(t(u,i,j)\) are added when comparing and recalculating label values. Note also that for \(k=1\) this algorithm becomes equivalent to Dijkstra. The correctness of Extended-Dijkstra-V1 is due to the following theorem. Theorem 3.1: _If all edge weights and transfer penalties in a graph are nonnegative then, for all distinguished pairs \((u,i)\), the label \(L(u,i)\) is the length of the shortest path from the source \((s,l)\) to \((u,i)\)._  
Proof. : Proof is by induction on the number of distinguished pairs. When there is just one distinguished pair, the theorem clearly holds since the length of the shortest path from \((s,l)\) to itself is \(L(s,l)=0\). For the step case, let \((v,j)\) be the next pair to be marked as distinguished by the algorithm (i.e., \(L(v,j)\) is minimal among all undistinguished pairs) and let \((u,i)\) be its predecessor. Hence the shortest \((s,l)\)-\((v,j)\)-path has length \(L(u,i)+t(u,i,j)+w(u,v,j)\). Now consider any other path \(P\) from \((s,l)\) to \((v,j)\). We need to show that the length of \(P\) cannot be less than \(L(u,i)+t(u,i,j)+w(u,v,j)\). Let \((x,a)\) and \((y,b)\) be pairs on \(P\) such that \((x,a)\) is distinguished and \((y,b)\) is not, meaning that \(P\) contains the edge \((x,y,b)\). This implies that the length of \(P\) is greater than or equal to \(L(x,a)+t(x,a,b)+w(x,y,b)\) (due to the induction hypothesis). Similarly, this figure must be greater than or equal to \(L(u,i)+t(u,i,j)+w(u,v,j)\) because, as assumed, \(L(v,j)\) is minimal among all undistinguished pairs. We now consider the computational complexity of Extended-Dijkstra-V1. As before, we assume the use of a binary heap for \(Q\) and direct access data structures for \(L\), \(D\) and \(P\). The initialisation of \(L\), \(D\), and \(P\) in Lines 1 to 5 has a worst-case complexity of \(\mathcal{O}(nc_{\max}^{-})\). For the main part of the algorithm, note that each label in \(L\) is considered and marked as distinguished exactly once and, in the worst case, we will have \(nc_{\max}^{-}\) such labels. Once a label \((u,i)\) is marked as distinguished, all incident edges \((u,v,j)\) are then considered in turn and are subject to a series of constant-time and log-time operations, as shown in Lines 12 to 15.