Chapter 2

Dijkstra's Algorithm

A natural starting point is to use Dijkstra's algorithm, which computes the shortest paths from a source node to all other nodes in a graph with non negative edge weights. In our setting, we are interested in the shortest paths to the query point from all possible listing locations. To achieve this, we adapt Dijkstra's algorithm to explore incoming edges.

Algorithm Description

The algorithm [Dijkstra1959, page 270] maintains a priority queue of nodes ordered by their tentative distance to the query point. It iteratively selects the node with the smallest tentative distance and updates its neighbors if a shorter path is found. This approach guarantees that each node is settled exactly once with its shortest path distance from the query node. The key steps are:

Note that this version explores incoming edges at each step, which differs from the standard formulation that explores outgoing edges. We do this because we are interested in the time it takes to navigate from a listing to our query point.

Below is an interactive visualization that demonstrates how it operates on a small graph.

Time Complexity

The overall time complexity of this algorithm depends on the priority queue used. Overall we perform $\mathcal{O}(E)$ insert operations and $\mathcal{O}(V)$ extract_min operations.

Standard priority queues like binary heaps achieve insert in $\mathcal{O}(\log V)$ time and extract_min in $\mathcal{O}(\log V)$ time [Cormen2009, page 506]. This yields an overall time complexity of $\mathcal{O}((E + V) \log V)$.

Advanced priority queues like Fibonacci heaps achieve insert in $\mathcal{O}(1)$ time and extract_min in $\mathcal{O}(\log V)$ time [Cormen2009, page 506] (amortized). This yields an overall time complexity of $\mathcal{O}(E + V \log V)$. However, Fibonacci heaps are rarely used in practice due to their implementation overhead [Cormen2009, page 507].

In this work, we use a binary heap, yielding overall algorithm time complexity of $\mathcal{O}((E + V) \log V)$.

Space Complexity

The space complexity of Dijkstra's algorithm depends primarily on the data structures used to store distances, the priority queue, and the graph itself. Storing the distance map requires $\mathcal{O}(V)$ space, as we maintain one distance per vertex. The priority queue contains at most $\mathcal{O}(V)$ elements, which also requires $\mathcal{O}(V)$ space. Additionally, storing the graph in adjacency list representation requires $\mathcal{O}(V + E)$ space. Therefore, the overall space complexity is $\mathcal{O}(V + E)$.

Empirical Performance

We benchmark this approach in our experimental setting. The bar chart below shows the average query time using Dijkstra’s algorithm.