Dial's Algorithm

A Bit of History

In 1969, Robert B. Dial published "Algorithm 360: Shortest-path forest with topological ordering" in the Communications of the ACM (CACM). Dial was working on traffic assignment and urban transportation network modeling. He observed that road networks and urban transit graphs have small integer travel times (e.g., edge weights in seconds or minutes bounded by a small maximum constant $C$). Instead of maintaining a general $O(\log V)$ priority queue heap, Dial replaced the heap with an array of buckets, yielding an $O(V \cdot C + E)$ shortest-path algorithm.

Working Principle: Bucket Queues

Standard Dijkstra's algorithm uses a priority queue to always extract the unvisited vertex with the minimum tentative distance dist[u]. Dial's algorithm replaces the heap with an array of buckets B[]:

• Let $C$ be the maximum edge weight in the graph. The max possible shortest path distance is $V \cdot C$.
• Create an array of buckets B[0 ... V * C], where bucket B[d] is a list containing all vertices $v$ currently having dist[v] = d.
• Maintain a bucket pointer idx starting at 0. Advance idx monotonically.
• When processing node $u$ at distance dist[u] = idx: for each neighbor $v$ with edge weight $w(u, v)$, if dist[u] + w < dist[v]:
  • Remove $v$ from its old bucket B[dist[v]].
  • Update dist[v] = dist[u] + w.
  • Insert $v$ into the new bucket B[dist[v]].

Worked Example

Consider a graph with max edge weight $C = 3$. Source node 0 has dist[0] = 0:

• B[0] = [0], all other buckets empty. Pointer idx = 0.
• Pop node 0 from B[0]. Neighbors: node 1 with weight 2, node 2 with weight 3.
• Update: dist[1] = 2, place 1 in B[2]; dist[2] = 3, place 2 in B[3].
• Advance idx: B[1] is empty, so move to idx = 2. Pop node 1 from B[2].
• Node 1 has neighbor 2 with edge weight 1. Tentative distance $2 + 1 = 3$. Distance stays 3.
• Move to idx = 3: pop node 2 from B[3]. All nodes processed!

Correctness & Monotonicity

Dial's algorithm is functionally identical to Dijkstra's algorithm. Its correctness relies on non-negative edge weights: since $w(u, v) \ge 0$, relaxing an edge from $u$ at distance $d$ yields a target distance $d + w(u, v) \ge d$. Thus, nodes are extracted from buckets in non-decreasing order of distance, preserving Dijkstra's greedy choice property.

Complexity Analysis

Each edge is relaxed once, taking $O(1)$ time to move a node between bucket lists. The bucket pointer idx advances at most $V \cdot C$ times:

$$\text{Time Complexity: } O(V \cdot C + E) \qquad \text{Space Complexity: } O(V \cdot C + E)$$

Using a circular array of size $C + 1$, space complexity drops to $O(V + E + C)$. When $C = O(1)$ or $C \ll \log V$, Dial's algorithm runs in **pure linear time $O(V + E)$**!

Implementation

def dials_algorithm(n, adj, src, max_weight):
    """
    n: number of vertices.
    adj: adj[u] = list of (v, weight)
    src: source vertex
    max_weight: maximum edge weight C
    Returns shortest distances array dist[].
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    # Buckets array B[0 ... n * max_weight]
    max_dist = n * max_weight
    buckets = [[] for _ in range(max_dist + 1)]
    buckets[0].append(src)

    idx = 0
    num_processed = 0

    while num_processed < n and idx <= max_dist:
        while idx <= max_dist and not buckets[idx]:
            idx += 1

        if idx > max_dist:
            break

        u = buckets[idx].pop()
        num_processed += 1

        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                old_dist = dist[v]
                if old_dist != INF:
                    buckets[old_dist].remove(v)
                dist[v] = dist[u] + weight
                buckets[dist[v]].append(v)

    return dist

# Example
n = 5
max_C = 4
adj = [[] for _ in range(n)]
edges = [(0, 1, 2), (0, 2, 4), (1, 2, 1), (1, 3, 2), (2, 3, 1), (3, 4, 3)]
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

print("Dial's Distances from 0:", dials_algorithm(n, adj, src=0, max_weight=max_C))

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

const int INF = 1e9;

vector<int> dialsAlgorithm(int n, const vector<vector<pair<int, int>>>& adj, int src, int maxWeight) {
    vector<int> dist(n, INF);
    dist[src] = 0;

    int maxDist = n * maxWeight;
    vector<list<int>> buckets(maxDist + 1);
    vector<list<int>::iterator> nodeIter(n);

    buckets[0].push_back(src);
    nodeIter[src] = buckets[0].begin();

    int idx = 0;
    int numProcessed = 0;

    while (numProcessed < n && idx <= maxDist) {
        while (idx <= maxDist && buckets[idx].empty()) {
            idx++;
        }

        if (idx > maxDist) break;

        int u = buckets[idx].front();
        buckets[idx].pop_front();
        numProcessed++;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            if (dist[u] + w < dist[v]) {
                if (dist[v] != INF) {
                    buckets[dist[v]].erase(nodeIter[v]);
                }
                dist[v] = dist[u] + w;
                buckets[dist[v]].push_back(v);
                nodeIter[v] = prev(buckets[dist[v]].end());
            }
        }
    }
    return dist;
}

int main() {
    int n = 5, maxC = 4;
    vector<vector<pair<int, int>>> adj(n);
    vector<tuple<int, int, int>> edges = {
        {0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 2}, {2, 3, 1}, {3, 4, 3}
    };
    for (auto& e : edges) {
        int u, v, w;
        tie(u, v, w) = e;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> dists = dialsAlgorithm(n, adj, 0, maxC);
    cout << "Dial's Distances from 0: ";
    for (int d : dists) cout << d << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class DialsAlgorithm {
    static final int INF = 1_000_000_000;

    static class Edge {
        int v, w;
        Edge(int v, int w) { this.v = v; this.w = w; }
    }

    public static int[] solve(int n, List<List<Edge>> adj, int src, int maxWeight) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        int maxDist = n * maxWeight;
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= maxDist; i++) buckets.add(new ArrayList<>());

        buckets.get(0).add(src);

        int idx = 0;
        int numProcessed = 0;

        while (numProcessed < n && idx <= maxDist) {
            while (idx <= maxDist && buckets.get(idx).isEmpty()) {
                idx++;
            }

            if (idx > maxDist) break;

            List<Integer> currBucket = buckets.get(idx);
            int u = currBucket.remove(currBucket.size() - 1);
            numProcessed++;

            for (Edge e : adj.get(u)) {
                int v = e.v;
                int w = e.w;

                if (dist[u] + w < dist[v]) {
                    if (dist[v] != INF) {
                        buckets.get(dist[v]).remove((Integer) v);
                    }
                    dist[v] = dist[u] + w;
                    buckets.get(dist[v]).add(v);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 5, maxC = 4;
        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0,1,2}, {0,2,4}, {1,2,1}, {1,3,2}, {2,3,1}, {3,4,3}};
        for (int[] e : edges) {
            adj.get(e[0]).add(new Edge(e[1], e[2]));
            adj.get(e[1]).add(new Edge(e[0], e[2]));
        }

        int[] dists = solve(n, adj, 0, maxC);
        System.out.println("Dial's Distances: " + Arrays.toString(dists));
    }
}

Real-World Applications

Exercises

1. Trace Dial's algorithm on a 4-node graph with max weight $C=2$ showing bucket array contents at each step.
2. How does Dial's algorithm simplify when all edge weights are $C=1$? (Hint: relate it to standard BFS!).
3. How does 0-1 BFS relate to Dial's algorithm with $C=1$?
4. Challenge: Implement a circular array optimization for Dial's buckets using size $C+1$ and modulo arithmetic.

Limitations