# Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties
## 5 Computational Comparison  
In this section we consider the CPU times required to calculate shortest path trees on various types of edge-coloured graphs. In particular, we wish to assess the relative performances of our extended Dijkstra methods in comparison to using [PERSON]'s original algorithm on Kirby-Potts expanded graphs. Note that we do not include the time taken to perform Kirby-Potts expansions in these results. This is because the decision on how a graph is represented and stored will often be made by the user beforehand and might therefore be considered a separate process. However, this will not always be the case as we discuss in Section 5.4. In our experiments, we will seek shortest paths in which transfer penalties are not incurred at terminal vertices. This is useful in applications such as public transport, where a passenger will arrive at the source vertex by means outside of the network (e.g., by foot), and will then leave the network on arrival at their destination. To make this modification on an edge-coloured graph we can simply set all transfer penalties at the source vertex \(s\) to zero before running the shortest path algorithm using an arbitrary in-colour \(l\in C^{-}(s)\) (in cases where the source vertex \(s\) does not feature an in-colour (\(C^{-}(s)=\varnothing\)), then a dummy in-colour can be temporarily added to the graph.). The length of the shortest \(s\)-\(v\)-path in \(G\) is then indicated by the minimum value among the labels of \(v\). For a Kirby-Potts expanded graph \(G^{\prime}\), a similar process is used: first, the weights of all transfer edges in the cluster defined by \(s\) are temporarily set to zero; next Dijkstra is executed from an arbitrary in-vertex within this cluster; finally, the minimum label value among all in-vertices in \(v\)'s cluster is identified. Three types of problem instances are considered in our tests: random graphs, planar graphs, and real-world public transport networks. The latter are considered in more detail in Section 5.3. Our random graphs were generated by randomly placing \(n\) vertices into the unit square. All potential edges \((u,v,i)\) were then considered in turn and added to the graph with a fixed probability of \(d/k\), where \(d\) is a density parameter representing the average number of edges travelling from each vertex \(u\) to each vertex \(v\). During this process, care was also taken to ensure that the graph contained a random \((n-1)\)-cycle, making the graph strongly connected. The second graph type, planar graphs, were considered to give a general indication of algorithm performance on transport networks. Recall that planar graphs are those that can be drawn on a plane so that no edges cross. In that sense, like road networks, they are quite sparse, with vertex degrees being fairly low. Note that when things like roads physically intersect on land, there will often be an opportunity to transfer from one to the other; hence, the underlying graph will be planar. However, this is not always the case, such as when one road crosses another via a bridge, so the analogy is not exact. Planar graphs were formed by again randomly placing \(n\) vertices into the unit square. A Delaunay triangulation was then generated from these vertices, with the edges of this triangulation being used to form a pool of potential edges for the graph (that is, for each edge \(\{u,v\}\) in the triangulation, all directed and coloured edges \((u,v,i)\) and \((v,u,i)\) (for \(i\in\{1,\ldots,k\}\)) were added to the pool). Edges were then selected randomly from this pool and added to the graph until the desired graph density was reached. Again, we also ensured that the resultant graph was strongly connected: in this case by including all edges from a bidirectional minimum spanning tree. For both random and planar graphs, edge weights were calculated using the Euclidean distances between vertices plus \(x\) per cent where, for each edge, \(x\) was selected randomly in the range \((-10,10)\).