Lecture 15: Dijkstra’s Algorithm
CSC 226: Algorithms and Data Structures II Quinton Yong
Shortest Paths
Copyright By PowCoder代写 加微信 powcoder
Let 𝑮 be a weighted graph. The length (or weight) of a path 𝑷 in 𝑮 is the sum of the weights of the edges of 𝑷.
That is, if 𝑷 consists of edges 𝒆𝟎, 𝒆𝟏, … , 𝒆𝒌−𝟏, then the length of 𝑷, denoted 𝒘 𝑷 , is defined as 𝒌−𝟏
𝒘𝑷 =𝒘𝒆𝒊 𝒊=𝟎
The distance from a vertex 𝒖 to a vertex 𝒗 in 𝑮, denoted 𝒅 𝒖, 𝒗 , is the length of the shortest path from 𝒖 to 𝒗.
Shortest Paths Applications
Communication Speeds in a Network:
Find the fastest way to route a data packet between two computers
𝟑 Mbps 𝟗 Mbps
𝟏 Mbps 𝟐 Mbps 𝟒 Mbps
𝟑 Mbps 𝟏𝟏 Mbps
Shortest Paths Applications
Google Maps:
Shortest Path Problem Variations
• Shortest path between two given vertices
• Single sink shortest paths (shortest path from all other vertices to some vertex)
• All pairs shortest paths
Dijkstra’s Algorithm
• Single source shortest paths (shortest path from some vertex to all other vertices)
Single Source Shortest Path Variations
• Directedgraphswitharbitraryedgeweights
• Undirectedgraphswithnon-negativeedgeweights • Directedgraphswithnon-negativeedgeweights
• No such thing as shortest paths for undirected graphs with negative edge-weights nor directed graphs with negative cycles
Dijkstra’s Algorithm
Shortest Paths different from MST
Minimum Spanning Tree:
Shortest Path:
Dijkstra’s Algorithm Idea
Find shortest distance from 𝒗 to all other vertices:
• Gradually build a neighbourhood of nodes of solved shortest paths starting from 𝒗
• Check if edges out of solved neighbourhood to give you shorter paths to other nodes • Addnextshortestpathtosolvedneighbourhood
Dijkstra’s Algorithm Idea
Find shortest distance from 𝒗 to all other vertices:
• Gradually build a neighbourhood of nodes of solved shortest paths starting from 𝒗
• Check if edges out of solved neighbourhood to give you shorter paths to other nodes • Addnextshortestpathtosolvedneighbourhood
Dijkstra’s Algorithm Idea
Find shortest distance from 𝒗 to all other vertices:
• Gradually build a neighbourhood of nodes of solved shortest paths starting from 𝒗
• Check if edges out of solved neighbourhood to give you shorter paths to other nodes • Addnextshortestpathtosolvedneighbourhood
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Pseudocode
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝑫𝒛←𝑫𝒖+𝒘 𝒖,𝒛 Update𝒛’skeyin𝑸to𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Dijkstra’s Algorithm Running Time
𝑫𝒊𝒋𝒌𝒔𝒕𝒓𝒂𝑺𝒉𝒐𝒓𝒕𝒆𝒔𝒕𝑷𝒂𝒕𝒉𝒔(𝑮, 𝒗):
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 𝒏 𝟑
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com