CS代考 CSC 226: Algorithms and Data Structures II Quinton Yong

𝒗𝟐 𝒗𝟔 𝒗𝟒
Lecture 6: Floyd-Warshall Algorithm
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca

Transitive Closure
Given a directed graph 𝑮, the transitive closure 𝑮∗ of 𝑮 is the directed graph such that • 𝑮∗hasthesameverticesas𝑮
• If 𝑮 has a directed path from 𝒖 to 𝒗 (𝒖 ≠ 𝒗), 𝑮∗ has a directed edge from 𝒖 to 𝒗
The transitive closure provides information about reachability in the digraph.
Applications include:
• Finding possible flight paths
• Finding possible ways to deliver packets across the internet

Transitive Closure using Floyd-Warshall Algorithm
• Floyd-Warshall’s algorithm constructs transitive closure with a dynamic programming algorithm
• The algorithm is identical to Floyd’s all-pairs-shortest-path algorithm
• We try to take advantage of the fact that some of the paths between vertices overlap
• i.e. We don’t follow the same path over and over again
• In each iteration, we build transitive closure paths between more and more vertices to avoid recalculation of reachability
Algorithm Design: Dynamic Programming
• Thedynamicprogrammingtechniqueisusedmainlyforoptimizationproblems,wherewewish to find the “best” way of doing something.
• The number of “best” ways is often exponential and thus the brute-force way of solving the problem (e.g. enumerating all solutions and selection the “best” one) is exponential
• If the problem has a certain “overlapping structure”, then we can exploit that and arrive at a polynomial time algorithm

Algorithm Design: Dynamic Programming
Simple Subproblems:
• There is a way to break down the problem into simple subproblems of a similar structure
• The subproblems can be easily defined with a few indices (i.e. 𝒊, 𝒋, 𝒌)
Subproblem optimality:
• An optimal solution to the global problem is a composition of optimal subproblem solutions using a simple combining operation
Subproblem overlap:
• Optimal solutions to unrelated subproblems can have subproblems in common. Such overlap is recognized and improves the efficiency significantly
• This is particularly important to dynamic programming algorithms, because it takes advantage of memoization

Floyd-Warshall Transitive Closure Idea
• Number the vertices 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
• For 𝒌 = 1 to 𝒏, when computing if 𝒗𝒊 can reach 𝒗𝒋, consider paths through the intermediate
vertices 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒌 when
• So, in each iteration 𝒌, we gradually add more and more reachability information, which makes
future reachability computation more efficient
Intermediate Vertex

Floyd-Warshall Algorithm
• Let 𝑮 be a digraph with 𝒏 vertices and 𝒎 edges
• Number the vertices 𝒗𝟏, 𝒗𝟐, … 𝒗𝒏 and let 𝑮𝟎 = 𝑮
• In the 𝒌𝒕𝒉 iteration, construct 𝑮𝒌 by adding to 𝑮𝒌−𝟏 edge (𝒗𝒊, 𝒗𝒋) if 𝑮𝒌−𝟏 contains (𝒗𝒊, 𝒗𝒌) and (𝒗𝒌, 𝒗𝒋)
For 𝒌 = 1, … , 𝒏, digraph 𝑮𝒌 has an edge 𝒗𝒊, 𝒗𝒌 if an only if digraph 𝑮 has a directed path from 𝒗𝒊 to 𝒗𝒋, whose intermediate vertices are in the set {𝒗𝟏, … , 𝒗𝒌}. In particular, 𝑮𝒏 = 𝑮∗, the transitive closure of 𝑮.
Intermediate Vertex

Floyd-Warshall Algorithm
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮
Output: Transitive closure 𝑮∗ of 𝑮
Let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be an arbitrary number of vertices in 𝑮 𝑮𝟎 ← 𝑮
for 𝒌 ← 1 to 𝒏 do
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do
if 𝒗𝒊, 𝒗𝒌 and (𝒗𝒌, 𝒗𝒋) are in 𝑮𝒌−𝟏 then
if(𝒗𝒊,𝒗𝒋)isnotin𝑮𝒌 then Add (𝒗𝒊, 𝒗𝒋) to 𝑮𝒌
𝒊 = 5, 𝒋 = 4

Floyd-Warshall Algorithm
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮
Output: Transitive closure 𝑮∗ of 𝑮
Let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be an arbitrary number of vertices in 𝑮 𝑮𝟎 ← 𝑮
for 𝒌 ← 1 to 𝒏 do
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do
if 𝒗𝒊, 𝒗𝒌 and (𝒗𝒌, 𝒗𝒋) are in 𝑮𝒌−𝟏 then
𝒗𝟐 𝒗𝟔 𝒗𝟒
if(𝒗𝒊,𝒗𝒋)isnotin𝑮𝒌 then Add (𝒗𝒊, 𝒗𝒋) to 𝑮𝒌
𝒊 = 4, 𝒋 = 2

Floyd-Warshall Algorithm
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮 𝑮𝟒 Output: Transitive closure 𝑮∗ of 𝑮
Let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be an arbitrary number of vertices in 𝑮
for 𝒌 ← 1 to 𝒏 do 𝑮𝒌 ← 𝑮𝒌−𝟏
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do 𝒗𝟐
if 𝒗𝒊, 𝒗𝒌 and (𝒗𝒌, 𝒗𝒋) are in 𝑮𝒌−𝟏 then if (𝒗𝒊, 𝒗𝒋) is not in 𝑮𝒌 then
Add (𝒗𝒊, 𝒗𝒋) to 𝑮𝒌 𝑮𝟓

Floyd-Warshall Algorithm
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮 𝑮𝟓 Output: Transitive closure 𝑮∗ of 𝑮
Let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be an arbitrary number of vertices in 𝑮
for 𝒌 ← 1 to 𝒏 do 𝑮𝒌 ← 𝑮𝒌−𝟏
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do 𝒗𝟐
if 𝒗𝒊, 𝒗𝒌 and (𝒗𝒌, 𝒗𝒋) are in 𝑮𝒌−𝟏 then if (𝒗𝒊, 𝒗𝒋) is not in 𝑮𝒌 then
Add (𝒗𝒊, 𝒗𝒋) to 𝑮𝒌 𝑮𝟔

Floyd-Warshall Algorithm
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮 𝑮𝟔 Output: Transitive closure 𝑮∗ of 𝑮
Let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be an arbitrary number of vertices in 𝑮
for 𝒌 ← 1 to 𝒏 do 𝑮𝒌 ← 𝑮𝒌−𝟏
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do 𝒗𝟐
if 𝒗𝒊, 𝒗𝒌 and (𝒗𝒌, 𝒗𝒋) are in 𝑮𝒌−𝟏 then
if(𝒗𝒊,𝒗𝒋)isnotin𝑮𝒌 then 𝑮 =𝑮∗
Add (𝒗𝒊,𝒗𝒋) to 𝑮𝒌 𝟕

Floyd-Warshall Algorithm Adj Matrix
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮
Output: Transitive closure 𝑮∗ of 𝑮
Let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be an arbitrary number of vertices in 𝑮 𝑮𝟎 ←𝑮
for 𝒌 ← 1 to 𝒏 do
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do
if 𝒗𝒊, 𝒗𝒌 and (𝒗𝒌, 𝒗𝒋) are in 𝑮𝒌−𝟏 then
𝑭𝒍𝒐𝒚𝒅𝑾𝒂𝒓𝒔𝒉𝒂𝒍𝒍(𝑮):
Input: Directed graph 𝑮
Output: Transitive closure 𝑮∗ of 𝑮
Let 𝟏, 𝟐, … , 𝒏 be an arbitrary number of vertices in 𝑮 foreachedge(𝒊,𝒋)in𝑮do𝑴 𝒊 𝒋 ←1
for 𝒌 ← 1 to 𝒏 do
if (𝒗𝒊, 𝒗𝒋) is not in 𝑮𝒌 then Add (𝒗𝒊, 𝒗𝒋) to 𝑮𝒌
for 𝒊 ← 1 to 𝒏, 𝒊 ≠ 𝒌 do
for 𝒋 ← 1 to 𝒏, 𝒋 ≠ 𝒊, 𝒌 do
if 𝑴 𝒊 𝒌 = 1 and 𝑴 𝒌 𝒋 𝑴𝒊𝒋=1

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts