# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 2 Shortest Path Problems and Algorithms for Solving Them
### Single Source  
We first consider the \"single source\" shortest path problem, where our aim is to produce a shortest path tree rooted at a source vertex \(s\). Perhaps the most well-known method in this regard is [PERSON]'s algorithm, which was reportedly designed in just twenty minutes by its creator [6; 7]. [PERSON]'s algorithm is only suitable for graphs in which all edge weights are nonnegative and operates by maintaining a set \(D\) of so-called \"distinguished vertices\". Initially, only the source vertex \(s\) is distinguished; during a run further vertices are then added to \(D\) one by one. A \"label\" \(L(v)\) is also stored for each vertex \(v\) in the graph. During execution, \(L(v)\) stores the length of the shortest \(s\)-\(v\)-path that uses distinguished vertices only. On termination of a run, \(L(v)\) will then store the length of the shortest \(s\)-\(v\)-path in the graph. If a vertex \(v\) has a label \(L(v)=\infty\), then no \(s\)-\(v\)-path is possible. In its most basic form, [PERSON]'s algorithm can be described in just three steps:  
1. Set \(L(v)=\infty\) for all \(v\in V\). Now set \(D=\emptyset\) and \(L(s)=0\). 2. Choose a vertex \(u\in V\) such that: (a) it value for \(L(u)\) is minimal; (b) \(L(u)<\infty\); and (c) \(u\
otin D\). If no such vertex exists, then end; otherwise insert \(u\) into \(D\) and go to Step 3. 3. For all neighbours \(v\in\Gamma(u)\) that are not in \(D\), if \(L(u)+w(u,v)<L(v)\) then set \(L(v)=L(u)+w(u,v)\). Return to Step 2. Stated in this form, observe that one vertex is added to \(D\) in each iteration, giving \(\mathcal{O}(n)\) iterations in total. Within each iteration we then need to identify the minimum label amongst vertices not in \(D\) (an \(\mathcal{O}(n)\) operation) and then update \(\mathcal{O}(n)\) vertex labels. This leads to an overall complexity of \(\mathcal{O}(n^{2})\). For sparse graphs, run times of [PERSON]'s algorithm can be significantly improved by making use of a priority queue [5]. During execution, this priority queue is used to hold the label values of all vertices that have been considered by the algorithm but that are not yet marked as distinguished. It should also allow the vertex with the minimum label within this queue to be identified in constant time. In addition, it is also desirable to maintain a _predecessor_ array, which will allow the construction of shortest paths (vertex sequences) between \(s\) and all reachable vertices. This more advanced version of [PERSON]'s algorithm is given in the pseudocode of Algorithm 1. As shown, the Dijkstra procedure uses four data structures, \(D\), \(L\), \(P\) and \(Q\). The first three of these contain \(n\) elements and will typically allow direct access (e.g., by using arrays). \(D\) is used to mark the distinguished vertices, \(L\) is used to hold the labels, and \(P\) holds the predecessor of each vertex in the shortest path tree. The priority queue is denoted by \(Q\). As shown, in each iteration \(Q\) is used to identify the undistinguished vertex \(u\) with the minimal label value. In the remaining instructions, \(u\) is then removed from \(Q\) and marked as distinguished, and adjustments are then made to the labels of undistinguished neighbours of \(u\) (and the corresponding entries in \(Q\)) as applicable. ```
DijkSstra (\(s\in V\)) for all\(v\in V\)  Set \(L(v)=\infty\); \(D(v)=\textbf{false}\); and \(P(v)=\textsc{null}\)  Set \(L(s)=0\) and \(Q=\{(s,L(s))\}\) while\(Q\
eq\varnothing\)  Let \((u,x)\) be the element in \(Q\) with minimum value for \(x\)  Remove \((u,x)\) from \(Q\) and set \(D(u)=\textbf{true}\) for all\(v\in\Gamma(u)\) such that \(D(v)=\textbf{false}\)do if\(L(u)+w(u,v)<L(v)\)then if\(L(v)\
eq\infty\)then remove \((v,L(v))\) from \(Q\)  Set \(L(v)=L(u)+w(u,v)\); \(P(v)=u\); and insert \((v,L(v))\) into \(Q\)
```  
**Algorithm 1** [PERSON]'s algorithm for producing a shortest-path tree from a source vertex \(s\in V\). The asymptotic running time of DijkSstra now depends mainly on the data structure used to represent \(Q\).