---
title: Dijkstra's optimizations
nav_order: 7
---

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

```java
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.

```java
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 %}