dijkstras-optimizations.md

title: Dijkstra's optimizations
nav_order: 7

Dijkstra's algorithm computes a weighted shortest paths tree in a graph from a start vertex.

dijkstra(Graph graph, Vertex start) {
    Map<Vertex, Double> distTo = new HashMap<>();
    Map<Vertex, Vertex> edgeTo = new HashMap<>();
    PriorityQueue<Vertex> perimeter = new PriorityQueue<>();

    perimeter.add(start);

    while (!perimeter.isEmpty()) {
        Vertex from = perimeter.removeMin();
        for (Edge edge : graph.neighbors(from)) {
            Vertex to = edge.to();
            double oldDist = distTo.getOrDefault(to, Double.INFINITY);
            double newDist = distTo.get(from) + edge.weight();
            if (newDist < oldDist) {
                distTo.put(to, newDist);
                edgeTo.put(to, from);
                if (perimeter.contains(to)) {
                    perimeter.changePriority(to, newDist);
                } else {
                    perimeter.add(to, newDist);
                }
            }
        }
    }
}

{% capture question %} Suppose we design a priority queue implementation where all methods run in worst-case constant time. Which of the following is the most descriptive worst-case runtime for Dijkstra's algorithm using this priority queue in terms of the number of vertices |V| and the number of edges |E|?

• Θ(|V|)
• Θ(|E|)
• Θ(|V|log |V|)
• Θ(|E|log |E|)
• Θ(|V| + |E|)
• Θ(|V|log |V| + |E|log |V|)
• Θ(|V|log |E| + |E|log |E|) {% endcapture %} {% capture explanation %} The runtime analysis is essentially the same as breadth-first search. Recall that the queue operations in BFS are also constant time. Dijkstra's enhances BFS by considering elements in order of least distance from the start using a priority queue.

Later, we'll prove why it is impossible to design such a priority queue that achieves these runtime bounds in general for any arbitrary data type. {% endcapture %} {% include question.html question=question number=1 %}

{% capture question %} Suppose we wanted to speed-up Dijkstra's algorithm for real-world routing by computing just a single-pair shortest path from a given start vertex to a given end vertex, rather than the shortest paths tree from the start to every other reachable vertex.

Consider the following implementation of this idea. The main addition is the commented if statement inside of the neighbors loop. Unfortunately, this implementation doesn't work. Explain why the behavior isn't correct and suggest a fix.

dijkstra(Graph graph, Vertex start, V end) {
    Map<Vertex, Double> distTo = new HashMap<>();
    Map<Vertex, Vertex> edgeTo = new HashMap<>();
    PriorityQueue<Vertex> perimeter = new PriorityQueue<>();

    perimeter.add(start);

    while (!perimeter.isEmpty()) {
        Vertex from = perimeter.removeMin();
        for (Edge edge : graph.neighbors(from)) {
            Vertex to = edge.to();
            if (end.equals(to)) {
                // edgeTo stores the shortest path from start to end
                // Wait, but is this really always true?
                return;
            }
            double oldDist = distTo.getOrDefault(to, Double.INFINITY);
            double newDist = distTo.get(from) + edge.weight();
            if (newDist < oldDist) {
                distTo.put(to, newDist);
                edgeTo.put(to, from);
                if (perimeter.contains(to)) {
                    perimeter.changePriority(to, newDist);
                } else {
                    perimeter.add(to, newDist);
                }
            }
        }
    }
}

{% endcapture %} {% include question.html question=question number=2 %}