程序代写代做代考 algorithm CSC373H Lecture 3

CSC373H Lecture 3
Dan Zingaro
September 26, 2016

Single-Source Shortest Path
􏹩 Input:connected,directed,weightedgraphG=(V,E),with n vertices and m edges; and start vertex s
􏹩 Each edge e has nonnegative weight w(e)
􏹩 Output: shortest path between s and each other vertex

Dijkstra’s Algorithm
􏹩 Dijkstra’s algorithm uses a min-priority queue to store the current distance to each remaining vertex
􏹩 It is a greedy algorithm because, on each iteration, it selects the vertex v in the priority queue with minimum distance and never looks at v again

Dijkstra’s Algorithm…
P = {} # edges in shortest paths tree
q = min priority queue
for all v in V:
pi[v] = NIL # predecessors
d[v] = infinity
enqueue all V in q
d[s] = 0
update priority of s in q
while q not empty: # main loop
v = dequeue minimum priority element from q
P = P UNION {(pi[v],v)}
for all edges (v,u):
if u in q and d[v] + w(v,u) < d[u]: pi[u] = v d[u] = d[v] + w(v,u) update priority of u in q P = P - {(NIL,s)} # clean up return P Dijkstra’s Algorithm: Example Let’s run Dijkstra’s algorithm on this graph, using start vertex s = 1. 1->2[weight 4]
1->3[weight 2]
1->4[weight 6]
3->2[weight 1]
3->4[weight 10]

Dijkstra’s Algorithm: Proof
Main idea of the proof.
􏹩 Let δ(x,y) be the weight of the shortest path from x to y
􏹩 Let u be the first vertex added to P such that d(u) ̸= δ(s,u)
􏹩 Notice that u cannot be s, because Dijkstra correctly sets d(s) to 0
􏹩 We will prove by contradiction that actually d(u) = δ(s,u) when u is added to P

Dijkstra’s Algorithm: Proof…
􏹩 Let p be the shortest path from s to u
􏹩 Before adding u to P, path p connects s, which is in P, to u,
which is not in P
􏹩 LetxbethefinalvertexonpthatisinP,andletybethe vertex after x on p

Dijkstra’s Algorithm: Proof…
First, let’s show that d(y) = δ(s,y) when u is added to P.
􏹩 x ∈ P, and d(x) = δ(s,x) (because x was added to P before
u)
􏹩 When x was added to P, Dijkstra would have found edge
(x,y)
d (y ) ≤ d (x ) + w (x , y ) (operation of Dijkstra) = δ(s, x) + w(x, y)
= δ(s,y) (subpaths of shortest paths are shortest paths)
d values cannot be less than the optimal δ values, so d(y) = δ(s,y).

Dijkstra’s Algorithm: Proof…
OK. Now let’s show that d(u) = δ(s,u) when u is added to P.
d(y) = δ(s,y) ≤ δ(s, u)
(just proved this) (all weights are nonnegative)
(d(u) was minimum weight outside of P) Therefore, d(u) = δ(s, u). Contradiction!
≤ d(u) ≤ d(y)

Runtime of Dijkstra
􏹩 We can use a min-heap to implement the priority queue of vertices
􏹩 Initialization is O(n) to enqueue the n vertices
􏹩 The outer for-loop does n dequeues, each of cost lg n
􏹩 The inner for-loop examines each of the m edges once, and each edge costs O(lgn) if its distance is updated in the queue
􏹩 So,wehaveO(n)+O(nlgn)+O(mlgn)=O(mlgn)