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)