Chapter 3

Dial's Algorithm

Dial's algorithm is an optimization of Dijkstra's algorithm designed for graphs with bounded, small integer edge weights. It avoids the use of priority queues by using a simple array of buckets, one for each possible distance value up to a maximum budget [Dial1969, page 632]. This results in a significant performance gain in both theoretical and practical terms when the query budget $B$ is small.

Algorithm Description

The algorithm maintains an array of buckets indexed by distance. Each bucket stores nodes whose tentative distance to the query point equals that index. We iterate through the buckets in increasing order, visiting nodes in the current bucket and exploring their incoming edges.

As in the adapted Dijkstra's algorithm, note that we explore incoming edges at each step, to find shortest paths to the query point.

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

Time Complexity

The time complexity of Dial's algorithm is $\mathcal{O}(V + E + B)$, where $E$ is the number of edges, $V$ is the number of vertices, and $B$ is the maximum distance budget.

This is because each node is processed at most once, each edge is considered at most once, and each bucket is accessed at most once. This is a substantial improvement over Dijkstra's $\mathcal{O}((E + V)\log V)$ complexity when using standard binary heaps [Cormen2009, page 506], assuming a low $B$.

Importantly, this improvement hinges on the assumption that edge weights and the budget $B$ are reasonably small, which holds in our real world application. For unbounded edge weights or unbounded time budgets $B$, Dial's algorithm is not applicable.

Space Complexity

The space complexity of Dial's algorithm arises from three main components: the bucket array, the graph representation, and the visited node map. The bucket array contains $B + 1$ buckets, where $B$ is the maximum distance budget. In the worst case, each edge can cause its target vertex to be placed in a bucket, leading to $\mathcal{O}(E)$ total bucket entries. Thus, the bucket array requires $\mathcal{O}(E + B)$ space.

The graph, stored in adjacency list form, uses $\mathcal{O}(V + E)$ space. Additionally, maintaining the visited map requires $\mathcal{O}(V)$ space to track the shortest distance (and possibly parent) for each vertex.

Summing all components, the overall space complexity of Dial's algorithm is $\mathcal{O}(V + E + B)$.

Empirical Performance

In practice, Dial's algorithm significantly reduces query time compared to Dijkstra's algorithm. The bar chart below shows the average query time using both algorithms, demonstrating a speedup of nearly 3× when using Dial's approach.