9906 2025 eng 14 article 0 2025-08-28 -- -- Given a public transportation network, which and how many passenger routes can potentially be shortest paths, when all possible timetables are taken into account? This question leads to shortest path problems on graphs with interval costs on their arcs and is closely linked to multi-objective optimization. We introduce a Dijkstra algorithm based on polynomials over the tropical semiring that computes complete or minimal sets of efficient paths. We demonstrate that this approach is computationally feasible by employing it on the public transport network of the city of Wuppertal and instances of the benchmarking set TimPassLib, and we evaluate the resulting sets of passenger routes. EURO Journal on Transportation and Logistics 2412.14654 10.1016/j.ejtl.2025.100163 yes publish Berenike Masing Berenike Masing Niels Lindner Enrico Bortoletto MODAL-Gesamt Lindner, Niels Bortoletto, Enrico Network Optimization Masing, Berenike MODAL-MobilityLab