留学生辅导 As always, a->b[c] means an edge from a to b with weight c

As always, a->b[c] means an edge from a to b with weight c

Sample Graph

Copyright By PowCoder代写 加微信 powcoder

1->2[1000000]

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.

… 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

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):

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[2] = inf
d[4] = inf
d[5] = inf

Smallest Dijkstra score is 1->5[7], with score 0+7 = 7

==========

X = {1, 3, 5}
d[2] = inf
d[4] = inf

Smallest Dijkstra score is 3->2[2], with score 6+2 = 8

==========

X = {1, 3, 5, 2}
d[4] = inf

Smallest Dijkstra score is 2->4[9], with score 8+9 = 17

==========

X = {1, 3, 5, 2, 4}

———-

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

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):

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