# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 3 Shortest Paths with Vertex Transfer Penalties  
As we have seen, a multitude of efficient algorithms exist for the shortest path problem in edge-weighted graphs. However, in many real world applications complications can arise due to the occurrence of \"transfer penalties\" at the vertices. Consider the graph in Figure 2, for example. This might depict some small public transport system with edge colours representing transport lines and weights representing travel times. Now suppose that we want to find the shortest path from vertex \(v_{1}\) to \(v_{9}\). By inspection, this is \((v_{1},v_{4},v_{5},v_{9})\) with a length of \(2+1+2=5\). However, this path involves changing lines at \(v_{4}\) which, in reality, might also incur some time penalty (e.g., if the commut \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Algorithm** & \
\begin{tabular}{l} **Worst Case Run-** \\ **Time Bound** \\ \end{tabular} &
\begin{tabular}{l} **Neg.** \\ **Weights?** \\ \end{tabular} & **Comments** \\ \hline _Single Source:_ & & & \\ Dijkstra (basic form) & \(\mathcal{O}(n^{2})\) & No & Optimal bound for dense graphs. \\ [PERSON] (binary heap) & \(\mathcal{O}(m\lg n)\) & No & More efficient than the basic form with sparse graphs. \\ [PERSON] (Fibonacci heap) & \(\mathcal{O}(m+n\lg n)\) & No & More efficient than the basic form with sparse graphs. \\ Bellman–Ford & \(\mathcal{O}(nm)\) & Yes & Also able to detect the presence of negative cycles. \\ [PERSON] & \(\mathcal{O}(nm)\) & Yes & Often faster than Bellman–Ford, but same worst case bound. \\ [PERSON] & \(\mathcal{O}(m+n\sqrt{\lg W})\) & No & Useful when the maximum edge weight \(W\) is small. \\ Gabow–Tarjan & \(\mathcal{O}(\sqrt{nm}\lg(nW))\) & Yes & Useful when the maximum edge weight \(W\) is small. \\ \hline _All Pairs:_ & & \\ Floyd–Warshall & \(\Theta(n^{3})\) & Yes & Bound exhibited with all graphs. Detects negative cycles. \\ [PERSON] (\(n\) applications) & \(\mathcal{O}(nD)\) & No & [PERSON]’s algorithm is run from each source \(s\in V\). \\ [PERSON] & \(\mathcal{O}(nm)+\mathcal{O}(nD)\) & Yes & Bellman–Ford is used to convert all edge weights to non-negative values. [PERSON] is then applied \(n\) times. \\ \hline _Single-Source Single-Target:_ & & \\ Dijkstra (any form) & \(\mathcal{O}(D)\) & No & Can halt as soon as the target vertex becomes distinguished. \\ A* & \(\mathcal{O}(D)\) & No & If a suitable (and admissible) heuristic is used, usually \\ [PERSON] & \(\mathcal{O}(KnD)\) & No & Produces the \(K\) shortest paths between source and target. \\ [PERSON] & \(\mathcal{O}(nm)\) & No & Produces pairs of edge- or vertex-disjoint paths between source and target. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Review summary of shortest path algorithms for edge-weighted graphs. Here, \(D\) represents the worst case run time bound of the chosen variant of [PERSON]’s algorithm. vehicles). If this penalty is more than three units, then the shortest path from \(v_{1}\) to \(v_{9}\) now becomes \((v_{1},v_{4},v_{7},v_{8},v_{9})\) with a length of eight. To incorporate vertex transfer penalties, consider the following model, which extends the one given in Section 2. Let \(G=(V,E)\) be an edge-weighted, loop-free, directed multigraph using \(k\) different _edge colours_. As before, \(V\) is the set of \(n\) vertices and \(E\) is a set of \(m\) directed, coloured, and weighted edges (\(E\subseteq\{(u,v,i):u,v\in V\wedge u\
eq v\wedge i\in\{1,\dots,k\}\}\). The weight of an edge of colour \(i\) travelling from vertex \(u\) to vertex \(v\) is now denoted by \(w(u,v,i)\). The following notation is also useful and is exemplified in Figure 2:  
**Definition 1**. : _Let \(E^{-}(v)=\{(u,v,i):(u,v,i)\in E\}\) be the set of edges of which the endpoint is vertex \(v\), and \(C^{-}(v)=\{i:\exists(u,v,i)\in E^{-}(v)\}\) be the set of distinct colours that enter \(v\).