Lecture 16: Dijkstra’s Algorithm Correctness
CSC 226: Algorithms and Data Structures II Quinton Yong
Dijkstra’s Algorithm Running Time
Copyright By PowCoder代写 加微信 powcoder
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
Input: A simple undirected graph 𝑮 with non-negative edge-weights, a distinguished vertex 𝒗 in 𝑮 Output:Alabel𝑫𝒖 foreachvertex𝒖in𝑮suchthat𝑫𝒖 istheshortestdistancefrom𝒗to𝒖in𝑮
for each vertex 𝒖 ≠ 𝒗 do
𝑫 𝒖 ← +∞ 𝑸←priorityqueueofallvertices𝒖using𝑫𝒖 asprioritykey
while 𝑸 is not empty do
𝒖 ← 𝑸. 𝒓𝒆𝒎𝒐𝒗𝒆𝑴𝒊𝒏() // add 𝒖 to the cloud of solved vertices
for each vertex 𝒛 ∈ 𝑸 adjacent to 𝒖 do if𝑫𝒖+𝒘 𝒖,𝒛 <𝑫𝒛then
since sum of all degrees is 𝑶(𝒎)
𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
Dijkstra’s Algorithm Time Complexity
Theorem:Givenasimple,undirected,non-negativeedge-weightedgraph𝑮= 𝑽,𝑬 with 𝒏 vertices and 𝒎 edges, Dijkstra’s algorithm computes the shortest distances
between a vertex 𝒗 ∈ 𝑽 and all other vertices of 𝑽 in 𝑶 𝒎 log 𝒏 𝟑
Adding neighbour 𝒖 of the cloud into the cloud
The final value of 𝑫 𝒖
denotes the length of a shortest path from starting vertex 𝒗 to 𝒖
For any vertex 𝒛 not in the cloud:
• 𝑫 𝒛 denotes a shortest path from 𝒗 to 𝒛 using vertices inside the cloud • +∞denotesthat𝒛cannotbereachedyetfrom𝒗viaonlycloudvertices
Correctness of Dijkstra’s Algorithm
Recall: 𝒅(𝒗, 𝒖) denotes the true shortest path distance from 𝒗 to 𝒖
• 𝑫 𝒖 maintains currently known shortest distance from 𝒗 (the starting vertex) to 𝒖
• 𝑫𝒖 ≥𝒅(𝒗,𝒖)atanytime
• When vertex 𝒖 is added to the cloud, 𝑫 𝒖 at that instant represents the shortest path distance from 𝒗 to 𝒖
Prove: Whenever a vertex 𝒖 is pulled into the cloud, the value of 𝑫 𝒖 length of the shortest path from 𝒗 to 𝒖 (i.e. 𝑫 𝒖 = 𝒅 𝒗, 𝒖 )
correctly stores the
Subpaths of Shortest Paths
Lemma: Given a weighted graph 𝑮 = 𝑽, 𝑬 , let 𝑷 = 𝒗𝟎, ... , 𝒗𝒌 be a shortest path from 𝒗𝟎 to 𝒗𝒌. Let 𝑷𝒊,𝒋 be a subpath of 𝑷. Then 𝑷𝒊,𝒋 is a shortest path from 𝒗𝒊 to 𝒗𝒋.
Proof: The weight of 𝑷 is 𝒘 𝑷 = 𝒘 𝑷𝟎,𝒊 + 𝒘 𝑷𝒊,𝒋 + 𝒘 𝑷𝒋,𝒌 . Assume for a contradiction that there exists a shorter path 𝑷′
𝒊,𝒋 𝒊,𝒋 𝟎 𝒌
Then we have that 𝒘 𝑷′ < 𝒘 𝑷 , which is a contradiction since 𝑷 is the shortest path from 𝒗𝟎 to 𝒗𝒌.
to 𝒗 Replace 𝑷 with 𝑷′ in path 𝑷, resulting in a new path 𝑷′ from 𝒗 to 𝒗 .
Namely, 𝑤 𝑷′ < 𝑤 𝑷 . 𝒊,𝒋 𝒊,𝒋
which is not on path 𝑷.
Correctness of Dijkstra’s Algorithm
Theorem: Whenever 𝒖 is added to the cloud, 𝑫 𝒖 stores the length of a shortest path from starting vertex𝒗to𝒖(i.e.𝑫𝒖 =𝒅𝒗,𝒖).
Proof: Assume for a contradiction that the theorem is false. Then, there exists a vertex 𝒕 that is added into the cloud and 𝑫 𝒕 > 𝒅 𝒗, 𝒕 .
Let 𝒖 be the first such vertex (that is “incorrectly” added to the cloud and 𝑫 𝒖 > 𝒅(𝒗, 𝒖)). So, before 𝒖 is added, the vertices in the cloud have correct shortest distances in 𝑫.
Let 𝑷 be the “actual” shortest path from starting vertex 𝒗 to 𝒖.
Let 𝒚 be the last vertex that lies on 𝑷 that was correctly added to the cloud. Let 𝒛 be the vertex closest to 𝒚 that lies on 𝑷 and is not in the cloud.
Correctness of Dijkstra’s Algorithm
1) Assumption: 𝑫 𝒖
> 𝒅(𝒗, 𝒖) lemma we have 𝑫 𝒛 = 𝒅(𝒗, 𝒛)
Putting all of this together:
𝑫[𝒖] ≤ 𝑫[𝒛]
≤𝒅𝒗,𝒛 +𝒅𝒛,𝒖 = 𝒅(𝒗, 𝒖)
2) Since 𝒖 was the minimum distance in 𝑫 removed by the algorithm, we know 𝑫 𝒖
3) Since 𝑷 is the shortest path from 𝒗 to 𝒖, and the path from 𝒗 to 𝒛 is a subpath of 𝑷, by the subpath
from statement 2)
from statement 3) sinceedgeweightsin𝐺arenon-negative since (path from 𝒗 to 𝒛) + (path from 𝒛 to 𝒖) is 𝑷
So, we have that 𝑫[𝒖] = 𝒅(𝒗, 𝒖). This is a contradiction since we assumed that 𝑫[𝒖] > 𝒅 𝒗, 𝒖 .
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com