Dijkstra's algorithm 🗺️

Background

Who was Dijkstra?

Dr. Edsger W. Dijkstra was a Dutch programmer, physicist, and essayist who played a pivotal role in transforming computer science from an art into a formal academic discipline. His discoveries and algorithms remain widely used today.

History

What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.

How to pronounce it?

Check it out here

Description

Assume that a weighted graph below represents a map, where the nodes are cities, the edges are roads and the weight of each edge is the distance between two cities:

Suppose we are in the city A and want to take a trip to the city G. To get from A to G as fast as possible, we need to know the shortest path between the cities, that is, the path with the minimum total weight. How can this path be found?

One of the possible approaches is to use Dijkstra's algorithm. It allows us to find the shortest paths from a given node to all other nodes of a graph. Let's consider the algorithm in more detail.

First, let's agree that we will use the following notations further:

• source: The node from which we want to find the shortest paths to all other nodes.
• weight(u, v): The weight of the edge that connects the nodes u and v.
• dist(v): The current distance from the source to the node v.

Now, Dijkstra's algorithm can be formulated as follows:

1. Set the current distance to the source to 0, and for all other nodes, assign it to ∞. Mark all nodes as unprocessed.
2. Find an unprocessed node u with the smallest dist(u).
3. For all unprocessed neighbors v of the node u, check whether the distance from u to v is less than the current distance to v. If that is the case, that is dist(u) + weight(u, v) < dist(v), update the current distance to v to the smaller value.
4. When all the neighbors of u are considered, mark u as processed.
5. If there are no unprocessed nodes, the algorithm is finished. Otherwise, go back to the 2nd step.

Pseudocode

After understanding the core principles of Dijkstra's algorithm, let's explore how the choice of data structure for storing current distances can influence its efficiency. The following pseudocode presents an implementation of Dijkstra's algorithm using a priority queue (binary heap), which as we'll soon explain, provides a more efficient solution for sparse graphs (than the array-based storage for current distances)

import java.util.*;

class DijkstraPriorityQueue {
    static class Node {
        String vertex;
        int distance;

        Node(String vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    public static void dijkstra(Map<String, List<Node>> graph, String source) {
        // Initialize distances with infinity for all nodes except the source
        Map<String, Integer> distances = new HashMap<>();
        for (String node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(source, 0);

        // Priority queue to store (distance, node) pairs
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
        priorityQueue.add(new Node(source, 0));

        while (!priorityQueue.isEmpty()) {
            // Extract node with the smallest distance
            Node currentNode = priorityQueue.poll();
            String current = currentNode.vertex;
            int currentDistance = currentNode.distance;

            processNode(current);

            // Update distances to unprocessed neighbors
            for (Node neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                int newDistance = currentDistance + neighbor.distance;
                if (newDistance < distances.get(neighbor.vertex)) {
                    distances.put(neighbor.vertex, newDistance);
                    priorityQueue.add(new Node(neighbor.vertex, newDistance));
                }
            }
        }

        // Output final shortest distances
        System.out.println("Shortest distances from source " + source + ": " + distances);
    }

    public static void processNode(String node) {
        System.out.println("Processing node: " + node);
    }

    public static void main(String[] args) {
        // Sample graph representation as adjacency list
        Map<String, List<Node>> graph = new HashMap<>();
        graph.put("A", Arrays.asList(new Node("B", 4), new Node("C", 1)));
        graph.put("B", Arrays.asList(new Node("A", 4), new Node("C", 2), new Node("D", 5)));
        graph.put("C", Arrays.asList(new Node("A", 1), new Node("B", 2), new Node("D", 8)));
        graph.put("D", Arrays.asList(new Node("B", 5), new Node("C", 8)));

        dijkstra(graph, "A");
    }
}