Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
---
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 %}