As always, a->b[c] means an edge from a to b with weight c
Sample Graph
1->2[1000000]
1->3[20]
3->2[10]
Let’s say start vertex s is 1.
What’s the shortest path distance from 1 to 2? 20+10 = 30. We care about total weight, not number of edges.
Can we convert to unweighted graph and use BFS?
No… not a good idea! Here’s why.
1->2A
2A->2B
2B->2C
2C->2D
… just do this a million times
1->3[20] # replace by 20 edges
3->2[10] # replace this by 10 edges
Problem: blows up the number of vertices and edges; BFS will be slow. We need something better.
———-
Walkthrough example of the first implementation of Dijkstra’s Algorithm
for all v in V:
d[v] = infinity # Shortest path to each vertex
X = {s} # Vertices whose shortest paths have been found
d[s] = 0
while X != V:
let (u*, v*) be an edge where u* in X and v* not in X
that minimizes d[u*] + w(u*, v*)
add v* to X
d[v*] = d[u*] + w(u*, v*)
Graph (start vertex s is 1):
1->2[12]
1->3[6]
1->4[45]
1->5[7]
3->2[2]
2->1[26]
2->4[9]
4->3[8]
5->2[21]
X = {1}
d[1] = 0
d[2] = inf
d[3] = inf
d[4] = inf
d[5] = inf
Smallest Dijkstra score is 1->3[6], with score 0+6 = 6
==========
X = {1, 3}
d[1] = 0
d[2] = inf
d[3] = 6
d[4] = inf
d[5] = inf
Smallest Dijkstra score is 1->5[7], with score 0+7 = 7
==========
X = {1, 3, 5}
d[1] = 0
d[2] = inf
d[3] = 6
d[4] = inf
d[5] = 7
Smallest Dijkstra score is 3->2[2], with score 6+2 = 8
==========
X = {1, 3, 5, 2}
d[1] = 0
d[2] = 8
d[3] = 6
d[4] = inf
d[5] = 7
Smallest Dijkstra score is 2->4[9], with score 8+9 = 17
==========
X = {1, 3, 5, 2, 4}
d[1] = 0
d[2] = 8
d[3] = 6
d[4] = 17
d[5] = 7
———-
We did a proof of correctness of Dijkstra’s algorithm. See slides for the cleaned-up version.
———-
Suppose we implement the algorithm using the above pseudocode.
What runtime will we get?
Let m = number of edges, n = number of vertices
We have to bound the work done by the while loop:
How many iterations of the while loop are there? n (one per vertex)
How much work do we do on each iteration of the while loop? m (scan through all edges)
Total: O(mn)
———-
Walkthrough example of the second implementation of Dijkstra’s Algorithm
for all v in V:
d[v] = infinity # Shortest path to each vertex
X = {} # Vertices whose shortest paths have been found
d[s] = 0
while X != V:
choose vertex v* not in X such that d[v*] is minimum
add v* to X
for each vertex u not in X
d[u] = min(d[u], d[v*] + w(v*, u))
Graph (start vertex s is 1):
1->2[12]
1->3[6]
1->4[45]
1->5[7]
3->2[2]
2->1[26]
2->4[9]
4->3[8]
5->2[21]
*d[1] = 0
d[2] = 8
*d[3] = 6
d[4] = 45
d[5] = 7
X = {1, 3}
First iteration, choose vertex 1.
Second iteration, choose vertex 3
Third iteration, choose vertex 5
…
(I stopped here; the above d values are those after the third iteration.)
———-
What runtime will we get for the second Dijkstra implementation?
Before: we had O(mn).
Let’s look at the runtime of this second implementation now.
Focus on the work done by the while loop.
1. How many iterations are there? n
2. How much work do we do on each iteration?
Find minimum d value: n work
The inner for loop: n work
Total work per iteration of the while loop: O(n)
n iterations of while loop, n work on each iteration…
O(n^2) algorithm now
Why is this better than O(mn) from before?
Think of a graph with n^2 edges, i.e. m = n^2
Before: O(mn) = O(n*n^2) = O(n^3)
Now: only O(n^2)
But we are not done making this thing as fast as possible!
The biggest clue that we can still improve this further is:
“choose vertex v* not in X such that d[v*] is minimum”
It’s min heap time!
Main idea:
-The min heap is going to hold all vertices outside of X; that is, all vertices whose d[] values we haven’t found yet
-The key for each of these vertices is its d value
-At the beginning of the algorithm, every vertex is in the heap
choose vertex v* not in X such that d[v*] is minimum: this goes from O(n) to O(log n); just do extract_min
Now how about this — how do we do this part:
d[u] = min(d[u], d[v*] + w(v*, u))
u is already in heap; we might be improving its d value here.
We can’t let the heap keep using the old d value for u.
So, we have to fix this vertex in the heap. How?
Approach 1: bubble up to new correct place
Approach 2: remove vertex, and then insert it again with its new d value
Approach 3: see Algorithmic Thinking, Appendix B
———-
What runtime will we get for the third Dijkstra implementation?
q = min priority queue
for all v in V:
d[v] = infinity # Shortest path to each vertex
enqueue all V in q
X = {} # Vertices whose shortest paths have been found
d[s] = 0
update priority of s in q
while X != V:
v* = dequeue minimum priority element from q
add v* to X
for each edge (v*, u) in q:
if d[u] > d[v*] + w(v*, u):
d[u] = d[v*] + w(v*, u)
update priority of u in q
What kind of runtime can we expect?
The priority queue/heap will have at most n items in it (one per vertex).
So each heap operation takes O(log n) time
To do all of the inserts and dequeues takes a total of O(n log n) time
The only other operations to consider are updating the priorities in the heap
Dijkstra’s algorithm looks at each edge at most once, and each edge can trigger at most one update.
So you can have at most m update operations on the heap.
This will cost you only O(m log n)
Total: O(m log n)
Overall best implementation of Dijkstra!
If you implement Dijkstra’s algorithm in this course, this is what we want you to use.