# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 2 Shortest Path Problems and Algorithms for Solving Them  
We begin with some preliminaries. Let \(G=(V,E)\) be an edge-weighted, directed graph where \(V\) is a set of \(n\) vertices and \(E\) is a set of \(m\) directed edges. In addition, let \(\Gamma(u)\) denote the set of vertices that are neighbours of \(u\) (that is, \(\Gamma(u)=\{v:\exists(u,v)\in E\}\)). The _weight_ of an edge travelling from vertex \(u\) to vertex \(v\) is denoted by \(w(u,v)\). The _length_ of a path \(P=(v_{0},v_{1},\ldots,v_{l})\) is then the sum of all weights of the constituent edges \(\sum_{i=1}^{l}w(v_{i-1},v_{i})\), where \((v_{i-1},v_{i})\in E\) for all \(i\in\{1,\ldots,l\}\). The _shortest path_ between a source vertex \(s\) and a target vertex \(t\) corresponds to the \(s\)-\(t\)-path in which the length is minimal.  
According to [PERSON] et al. (2015), three problems involving shortest paths on edge-weighted graphs can be distinguished: (a) the \"single-source single-target\" problem, which involves finding the shortest path between a particular source vertex \(s\) and target vertex \(t\); (b) the \"single source\" problem, which involves determining the shortest path from a source \(s\) to all other vertices (thereby producing a shortest path tree rooted at \(s\)); and (c) the \"all pairs\" problem, where shortest paths are identified between all pairs of vertices. Examples of (a) and (b) are shown in Figure 1.  
The following three subsections will now review many of the available algorithms for problems (a) to (c). Note that all of these algorithms are _exact_ in that they are guaranteed to find optimal solutions for all valid problem instances. They also all feature polynomial-time complexity, though some have more favourable growth rates than others. The following points should also be made.  
* Edge weights in graphs do not need to represent distances. In transportation problems for example, they could indicate predicted travel times or fuel costs; in currency conversion they could represent exchange rates. Weights can also be both positive and negative.  
Figure 1: An example graph with \(n=100\) vertices. In this case, edges are drawn with straight lines and edge weights correspond to the lengths of these lines. This graph is also symmetric in that \((u,v)\in E\) if and only if \((v,u)\in E\), with \(w(u,v)=w(v,u)\). The **(left)** figure shows a solution to the “single-source single-target” problem, where the source \(s\) is at the bottom-left and the target \(t\) is at top right. The **(right)** figure shows a solution to the “single source” problem—a shortest-path tree rooted at \(s\).  
* Shortest paths in a graph are nearly always \"simple paths\" in that they will not visit a vertex more than once. The exception to this is when a graph contains a cycle in which the edge-weight total is less than or equal to zero. If a graph contains a _negative cycle_, then the problem can be considered ill-defined because shortest paths will involve looping around this cycle indefinitely. The ability to detect negative cycles is therefore a useful feature of a shortest path algorithm.
* Graphs are not always strongly connected. That is, there may be pairs of vertices \(u,v\in V\) for which no \(u\)-\(v\)-path (and/or \(v\)-\(u\)-path) exists. If a graph is strongly connected, then a shortest path tree rooted at any vertex will also be a spanning tree.
* Although typically stated on directed graphs, shortest path problems are also appropriate for undirected graphs. In this case it is sufficient to covert the undirected graph to its directed equivalent by replacing undirected edges \(\{u,v\}\) with directed edges \((u,v)\) and \((v,u)\), while maintaining the weights (as with Figure 1).
* In real-world transportation problems, users may often specify start and end points that occur somewhere along an edge (road) as opposed to at a vertex (intersection). In such cases it is sufficient to simply create temporary vertices at these points, and adjust the surrounding edge weights accordingly.