Parallel Point-to-Point Shortest Paths and Batch Queries

We propose Orionet, efficient parallel implementations of Point-to-Point Shortest Paths (PPSP) queries using bidirectional search (BiDS) and other heuristics, with an additional focus on batch PPSP queries. We present a framework for parallel PPSP built on existing single-source shortest paths (SSSP) frameworks by incorporating novel pruning conditions. As a result, we develop efficient parallel PPSP algorithms based on early termination, bidirectional search, A* search, and bidirectional A*---all with simple and efficient implementations.