Revisiting Dijkstra’s Algorithm: The Hidden Foundation of Modern Tech

Revisiting Dijkstra’s Algorithm: The Hidden Foundation of Modern Tech

This morning, I revisited Dijkstra’s Algorithm—a classic I had to memorize back in university. It felt like catching up with an old friend and reminded me how much of our modern world relies on this single concept.

From Google Maps route planning to OSPF routing protocols across the internet, its footprint is everywhere.

How It Works

It solves the single-source shortest path problem for graphs with non-negative edge weights:

1. Initialize: Start node distance = 0; others = infinity.
2. Explore: Pick the unvisited node with the smallest distance.
3. Update: For unvisited neighbors, calculate the distance through the current node. If shorter, update it.
4. Repeat: Mark as visited. Repeat until all are visited.

Core Logic in Java

Using a PriorityQueue efficiently extracts the minimum distance:

public static void dijkstra(int source, List<List<Edge>> adj, int V) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.add(new int[]{0, source});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[1], d = cur[0];

        if (d > dist[u]) continue;

        for (Edge e : adj.get(u)) {
            if (dist[u] + e.weight < dist[e.target]) {
                dist[e.target] = dist[u] + e.weight;
                pq.add(new int[]{dist[e.target], e.target});
            }
        }
    }
}

It is amazing how this elegant logic from 1956 still powers today's connected infrastructure. Re-reading the classics always brings fresh perspective!