pith. sign in

arxiv: 1907.09041 · v1 · pith:JCWT5T6Rnew · submitted 2019-07-21 · 💻 cs.DS · math.CO

Combining the Connection Scan Algorithm with Contraction Hierarchies

Jacob Turner This is my paper

Pith reviewed 2026-05-24 18:13 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords Connection Scan AlgorithmContraction Hierarchiesshortest pathstime-dependent routingpublic transportation networksgraph preprocessingdirected graphs
0
0 comments X

The pith

The Connection Scan Algorithm can be combined with Contraction Hierarchies to improve shortest-path query speed over bi-directional Dijkstra or A* search.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a way to merge the Connection Scan Algorithm, originally for timetable-based public transport, with Contraction Hierarchies created by preprocessing. This merged approach finds minimally weighted routes in weighted directed graphs more efficiently than standard searches on the hierarchies alone. A reader would care because many real applications, from navigation to transport planning, rely on repeated shortest-path calculations in networks that change with time. The work keeps the focus on preserving correctness while gaining performance in the time-dependent case.

Core claim

The paper claims that Contraction Hierarchies, which create a hierarchy of shortcut edges through preprocessing, can be used to restrict and accelerate the Connection Scan Algorithm without sacrificing correctness, yielding faster queries than bi-directional Dijkstra or A* on the same hierarchies.

What carries the argument

The adaptation of the Connection Scan Algorithm to scan only within the levels of a Contraction Hierarchy, using the hierarchy's upward and downward edges to limit the search space.

If this is right

  • Shortest-path queries in public-transportation networks with timetables become faster.
  • The preprocessing step that builds Contraction Hierarchies directly supports the scan-based search.
  • Correctness is preserved while search is restricted to relevant hierarchy levels.
  • The method applies to weighted digraphs beyond pure timetable data.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach might reduce memory traffic during queries by limiting which hierarchy levels are examined.
  • Similar combinations could be tested on other scan-based or label-setting algorithms.
  • The technique may generalize to dynamic updates if the hierarchies can be maintained incrementally.

Load-bearing premise

The Connection Scan Algorithm can be adapted to exploit Contraction Hierarchies without losing correctness or introducing prohibitive overhead in the time-dependent setting.

What would settle it

A concrete time-dependent network where the combined algorithm either returns a non-optimal route or runs slower than bi-directional Dijkstra on the same Contraction Hierarchies.

Figures

Figures reproduced from arXiv: 1907.09041 by Jacob Turner.

Figure 1
Figure 1. Figure 1: The Connection Scan Algorithm. on which arcs were added during preprocessing and what shortest path they are a stand-in for. Since the number of arcs searched by Dijkstra’s algorithm is greatly reduced, the preprocessing stage can give significant speed-ups. The preprocessing strikes a nice compromise between no preprocessing and the computation of the pair￾wise shortest path look-up table in the following… view at source ↗
Figure 2
Figure 2. Figure 2: The Generalized Connection Scan Algorithm. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The Modified CSA algorithm for querying Contraction Hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
read the original abstract

Since the first solutions finding minimally weighted routes in weighted digraphs, a plethora of literature has appeared improving the performance of shortest-path queries for use in real-world applications. In this paper, we detail how an advanced pre-processing technique for routing algorithms (which create objects known as Contraction Hierarchies) may be combined with the connection scan algorithm, an algorithm originally designed to work with public transportation networks using time tables. This provides an improvement over bi-directional Dijkstra or A${}^*$ search on Contraction Hierarchies.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper proposes combining the Connection Scan Algorithm (originally for timetable-based public transport networks) with Contraction Hierarchies (a preprocessing technique for shortest-path queries on weighted digraphs). The central claim is that this CSA+CH combination yields faster queries than bidirectional Dijkstra or A* search performed on Contraction Hierarchies.

Significance. If the claimed performance improvement holds while preserving correctness in the time-dependent setting, the work would contribute a practical algorithmic variant to the route-planning literature. Both CSA and CH are established techniques; a sound integration could be useful for real-world timetable routing applications. No machine-checked proofs, reproducible code, or parameter-free derivations are present to credit.

major comments (1)
  1. [Abstract] Abstract: The manuscript asserts that the CSA+CH combination 'provides an improvement' over bidirectional Dijkstra or A* on CH, yet supplies neither a derivation of correctness, pseudocode for the adaptation, nor any experimental data or runtime comparisons. This absence is load-bearing for the central claim, as the performance benefit cannot be assessed from the provided text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and constructive feedback. We agree with the assessment that the current manuscript version requires substantial additions to support its central claim and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The manuscript asserts that the CSA+CH combination 'provides an improvement' over bidirectional Dijkstra or A* on CH, yet supplies neither a derivation of correctness, pseudocode for the adaptation, nor any experimental data or runtime comparisons. This absence is load-bearing for the central claim, as the performance benefit cannot be assessed from the provided text.

    Authors: We acknowledge that the provided manuscript text is limited to a high-level abstract and does not contain a correctness derivation, pseudocode for the CSA+CH adaptation, or any experimental runtime comparisons. In the revised manuscript we will add: (1) a dedicated section with pseudocode for the combined algorithm, (2) a proof sketch establishing correctness when CSA is run on the CH-preprocessed graph in the time-dependent timetable setting, and (3) experimental results comparing query times against bidirectional Dijkstra and A* on the same CH instances. These additions will directly address the load-bearing gap identified by the referee. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an algorithmic combination of CSA and CH for time-dependent routing, with the central claim being an empirical performance improvement over bidirectional Dijkstra/A* on CH. No equations, fitted parameters, predictions, or self-referential definitions appear in the provided text. The derivation consists of algorithmic descriptions rather than any reduction of outputs to inputs by construction. No load-bearing self-citations or uniqueness theorems are invoked. The result is self-contained as a description of a new algorithm variant.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are introduced; the paper is an algorithmic integration description.

pith-pipeline@v0.9.0 · 5597 in / 891 out tokens · 26214 ms · 2026-05-24T18:13:13.630846+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 1 internal anchor

  1. [1]

    Car or public transport - two worlds

    Hannah Bast. Car or public transport - two worlds. In Efficient Algorithms, pages 355–367. Springer, 2009

    work page 2009

  2. [2]

    Combining hierarchical and goal- directed speed-up techniques for dijkstra’s algorithm

    Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Do- minik Schultes, and Dorothea Wagner. Combining hierarchical and goal- directed speed-up techniques for dijkstra’s algorithm. Journal of Experi- mental Algorithmics (JEA) , 15:2–3, 2010

    work page 2010

  3. [3]

    On a routing problem

    Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87–90, 1958

    work page 1958

  4. [4]

    Round-based public transit routing

    Daniel Delling, Thomas Pajor, and Renato Werneck. Round-based public transit routing. Society for Industrial and Applied Mathematics, January 2012

    work page 2012

  5. [5]

    In- triguingly simple and fast transit routing

    Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. In- triguingly simple and fast transit routing. In International Symposium on Experimental Algorithms, pages 43–54. Springer, 2013

    work page 2013

  6. [6]

    A note on two problems in connexion with graphs

    Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271, 1959

    work page 1959

  7. [7]

    Network flow theory

    Lester R Ford Jr. Network flow theory. Technical report, RAND CORP SANTA MONICA CA, 1956

    work page 1956

  8. [8]

    Fibonacci heaps and their uses in improved network optimization algorithms

    Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3):596–615, 1987

    work page 1987

  9. [9]

    Contraction hierarchies: Faster and simpler hierarchical routing in road networks

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In International Workshop on Experimental and Efficient Algo- rithms, pages 319–333. Springer, 2008

    work page 2008

  10. [10]

    Exact routing in large road networks using contraction hierarchies

    Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vet- ter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388–404, 2012

    work page 2012

  11. [11]

    A formal basis for the heuristic determination of minimum cost paths

    Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics , 4(2):100–107, 1968. 11

    work page 1968

  12. [12]

    Multiobjective a* search with consistent heuristics

    Lawrence Mandow and Jos´ e Luis P´ erez De La Cruz. Multiobjective a* search with consistent heuristics. Journal of the ACM (JACM) , 57(5):27, 2010

    work page 2010

  13. [13]

    Partitioning graphs to speedup dijkstra’s algorithm

    Rolf H M¨ ohring, Heiko Schilling, Birk Sch¨ utz, Dorothea Wagner, and Thomas Willhalm. Partitioning graphs to speedup dijkstra’s algorithm. Journal of Experimental Algorithmics (JEA) , 11:2–8, 2007

    work page 2007

  14. [14]

    The shortest path through a maze

    Edward F Moore. The shortest path through a maze. In Proc. Int. Symp. Switching Theory, 1959 , pages 285–292, 1959

    work page 1959

  15. [15]

    Shortest path algorithms in transportation models: classical and innovative aspects

    Stefano Pallottino and Maria Grazia Scutella. Shortest path algorithms in transportation models: classical and innovative aspects. In Equilibrium and advanced transportation modelling, pages 245–281. Springer, 1998

    work page 1998

  16. [16]

    Search Space Contraction in Canonical Labeling of Graphs

    Adolfo Piperno. Search space contraction in canonical labeling of graphs. arXiv preprint arXiv:0804.4881 , 2008

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  17. [17]

    Highway hierarchies hasten exact shortest path queries

    Peter Sanders and Dominik Schultes. Highway hierarchies hasten exact shortest path queries. In European Symposium on Algorithms, pages 568–

    work page

  18. [18]

    Engineering highway hierarchies

    Peter Sanders and Dominik Schultes. Engineering highway hierarchies. In European Symposium on Algorithms, pages 804–816. Springer, 2006

    work page 2006

  19. [19]

    Structure in communication nets

    Alfonso Shimbel. Structure in communication nets. In Proceedings of the symposium on information networks , volume 4. Polytechnic Institute of Brooklyn Nueva York, 1954

    work page 1954

  20. [20]

    A multicriteria pareto-optimal path algorithm

    Chi Tung Tung and Kim Lin Chew. A multicriteria pareto-optimal path algorithm. European Journal of Operational Research, 62(2):203–209, 1992. 12

    work page 1992