Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Algorithms for finding shortest paths in networks with vertex transfer penalties

Lewis, Rhyd ORCID: 2020. Algorithms for finding shortest paths in networks with vertex transfer penalties. Algorithms 13 (11) , 269. 10.3390/a13110269

[thumbnail of algorithms-13-00269 (1).pdf]
PDF - Published Version
Download (1MB) | Preview


In this paper we review many of the well-known algorithms for solving the shortest path problem in edge-weighted graphs. We then focus on a variant of this problem in which additional penalties are incurred at the vertices. These penalties can be used to model things like waiting times at road junctions and delays due to transfers in public transport. The usual way of handling such penalties is through graph expansion. As an alternative, we propose two variants of Dijkstra’s algorithm that operate on the original, unexpanded graph. Analyses are then presented to gauge the relative advantages and disadvantages of these methods. Asymptotically, compared to using Dijkstra’s algorithm on expanded graphs, our first variant is faster for very sparse graphs but slower with dense graphs. In contrast, the second variant features identical worst-case run times. Keywords: shortest path problems; Dijkstra’s algorithm; transfer penalties; public transport

Item Type: Article
Date Type: Published Online
Status: Published
Schools: Mathematics
Additional Information: Attribution 4.0 International (CC BY 4.0)
Publisher: MDPI
ISSN: 1999-4893
Date of First Compliant Deposit: 23 October 2020
Date of Acceptance: 18 October 2020
Last Modified: 05 May 2023 21:17

Citation Data

Cited 14 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics