CS代考 COMP3711: Design and Analysis of Algorithms Tutorial 10: MST and Shortest P

S. Hitarth
26/04/2022
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 1 / 20
COMP3711: Design and Analysis of Algorithms Tutorial 10: MST and Shortest Paths

MST: Definition
Spanning Tree: It is a subgraph of
G = (V,E) that has all the vertices of G in it, and is a tree
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 2 / 20

MST: Definition
Spanning Tree: It is a subgraph of
G = (V,E) that has all the vertices of G in it, and is a tree
Minimum Spanning Tree: Let
G = (V,E,c) with c : E → Q be a edge-weighted graph. A MST is a spanning tree T = (V,E′ with minimum cost
􏰪e∈E′ c(e) among all the possible spanning trees of G
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 2 / 20

MST: Definition (Contd.)
Quick Exercise: Can there be two minimum spanning tree of a graph G?
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 3 / 20

MST: Definition (Contd.)
Quick Exercise: Can there be two minimum spanning tree of a graph G?
Consider the following trivial example:
S. Hitarth (HKUST)
Tutorial 10 : MST and Shortest Paths
26/04/2022

MST: Algorithms
Prim’s Algorithm:
1 Start from any vertex v ∈ G and a graph
T =({v},{}):
2 Among all the edges e = (x,y), where x∈T andu̸∈T,selecttheedgewith smallest weight and add it to the tree T . If no such edge exists, return T
3 Repeat Step 2 until all vertices are in T
Kruskal’s Algorithm:
1 Start with an empty graph T = ({}, {})
2 Greedily add an edge (v , u) with smallest weight to T if the resulting graph remains acyclic. If no such edge exists, return T
3 Repeat step 2 until all vertices are in T
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 4 / 20

Bellman-Ford Algorithm and Shortest Path in DAG
Relaxation: Given an edge e = (u,v) ∈ E of a weighted graph
G = (V,E), and a distance v.d ∈ R and a parent v.p ∈ V associated with each vertex, relaxation of edge e is an update of the distance map:
if v.d > u.d + weight(u, v) then v.d = u.d + weight(u, v)
Bellman-Ford Algorithm: Given a directed graph G = (V , E ), and a source vertex s ∈ V
1 Initialize dist[v] = ∞ for all v ∈ V − s, and dist[s] = 0
2 Perform |V | − 1 rounds of relaxing each edge of E
Shortest Path In DAG: Given a directed-acyclic graph G = (V , E ), and a source vertex s ∈ V
1 Topologically sort the vertices of G
2 Initialize dist[v] = ∞ for all v ∈ V − s, and dist[s] = 0
3 For each vertex in the topological sort: Relax all the edges outgoing
from the current vertex
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 5 / 20

Problem 1: Is e in the MST?
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 6 / 20
Given a connected graph G = (V , E ) with n vertices and m edges, all having distinct edge costs, and an edge e = {u, v } ∈ E , devise an algorithm with running time O(m + n) to decide whether e is contained in a minimum spanning tree of G.

Problem 1: Is e in the MST?
Key Idea: Think about Kruskal’s Algorithm!
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 6 / 20
Given a connected graph G = (V , E ) with n vertices and m edges, all having distinct edge costs, and an edge e = {u, v } ∈ E , devise an algorithm with running time O(m + n) to decide whether e is contained in a minimum spanning tree of G.

Problem 1: Is e in the MST? (Contd.) Consider the following graph G with given edge e = (u,v):
v3 v1 5 u 8
S. Hitarth (HKUST)
Tutorial 10 : MST and Shortest Paths
26/04/2022

Problem 1: Is e in the MST? (Contd.) Consider the following graph G with given edge e = (u,v):
Let’s color the edges with cost smaller than that of the given edge green, and those larger with red
Quick Exercise: When we apply the Kruskal’s algorithm for MST, which edges will be considered before the edge {u,v} with cost c?
The edges that have cost less than c! Suppose we run the Kruskal’s algorithm for all the green edges, the connected components that we will end up with finally do not depend on the order in which we execute the unions for the components.
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 7 / 20

Problem 1: Is e in the MST? (Contd.)
Every time we process an edge {u,v} in Kruskal’s algorithm, we do union(u,v). To find out if we will actually include the edge in MST we had to execute the find(u) and find(v).
At this stage of Kruskal’s algorithm, the edge e = {u,v} will be added to the MST if and only if u and v belong to different components. Instead of doing union-find on processing each edge, we find all the connected components in the subgraph induced by the green edges
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 8 / 20

Problem 1: Is e in the MST? (Contd.)
In line 1, we spend O(n) time for initializing the array
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 9 / 20
CheckEdgeInMST: Algorithm
1: 2: 3: 4:
Input: GraphG=(V,E)andanedgee=(u,v)∈E CompID = 0, ComponentID[x] = −1 for each x ∈ V for vertex x in V if ComponentID[x] = −1 do
Start BFS from x restricting to edges with cost less than cost(e) ID[x] = CompID for each vertex visited in the previous BFS
CompID+ = 1
return ComponentID[u]! = ComponentID[v]

Problem 1: Is e in the MST? (Contd.)
In line 1, we spend O(n) time for initializing the array
We execute the loop body at most once per vertex, and pass through
each edge once (Why?). Therefore, the total time the loop at line 2 takes is in O(n + m) time.
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 9 / 20
CheckEdgeInMST: Algorithm
1: 2: 3: 4:
Input: GraphG=(V,E)andanedgee=(u,v)∈E CompID = 0, ComponentID[x] = −1 for each x ∈ V for vertex x in V if ComponentID[x] = −1 do
Start BFS from x restricting to edges with cost less than cost(e) ID[x] = CompID for each vertex visited in the previous BFS
CompID+ = 1
return ComponentID[u]! = ComponentID[v]

Problem 1: Is e in the MST? (Contd.)
In line 1, we spend O(n) time for initializing the array
We execute the loop body at most once per vertex, and pass through
each edge once (Why?). Therefore, the total time the loop at line 2 takes is in O(n + m) time.
In total, the algorithm takes O(n + m) time.
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 9 / 20
CheckEdgeInMST: Algorithm
1: 2: 3: 4:
Input: GraphG=(V,E)andanedgee=(u,v)∈E CompID = 0, ComponentID[x] = −1 for each x ∈ V for vertex x in V if ComponentID[x] = −1 do
Start BFS from x restricting to edges with cost less than cost(e) ID[x] = CompID for each vertex visited in the previous BFS
CompID+ = 1
return ComponentID[u]! = ComponentID[v]

Problem 2: NegativeCycle
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 10 / 20
Let G = (V , E ) be a weighted, directed graph that has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle.

Problem 2: NegativeCycle
Quick Exercise: Which algorithm can we use to detect the presence of the negative cycle?
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 10 / 20
Let G = (V , E ) be a weighted, directed graph that has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle.

Problem 2: NegativeCycle
Quick Exercise: Which algorithm can we use to detect the presence of the negative cycle?
Bellman-Ford!
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 10 / 20
Let G = (V , E ) be a weighted, directed graph that has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle.

Problem 2: NegativeCycle
Quick Exercise: Which algorithm can we use to detect the presence of the negative cycle?
Bellman-Ford!
Suppose we execute the relaxation for all the |E | edges |V | − 1 time with the source vertex s ∈ V .
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 10 / 20
Let G = (V , E ) be a weighted, directed graph that has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle.

Problem 2: NegativeCycle
Quick Exercise: Which algorithm can we use to detect the presence of the negative cycle?
Bellman-Ford!
Suppose we execute the relaxation for all the |E | edges |V | − 1 time with the source vertex s ∈ V .
If the graph didn’t contain a negative cycle reachable from s, then v.d would become the shortest distance from s to v. We can also retrieve this path by finding the listing the v.p iteratively starting from v until we reach s.
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 10 / 20
Let G = (V , E ) be a weighted, directed graph that has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle.

Problem 2: NegativeCycle Contd.
Suppose there exists an edge e = (u,v) ∈ E that can result in a successful relaxation, i.e., the distance function and the parent are updated for the vertex v.
What does it mean for us?
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 11 / 20

Problem 2: NegativeCycle Contd.
Suppose there exists an edge e = (u,v) ∈ E that can result in a successful relaxation, i.e., the distance function and the parent are updated for the vertex v.
What does it mean for us?
There exists some negative cycle!
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 11 / 20

Problem 2: NegativeCycle (Detecting)
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 12 / 20
NegativeCycleExists
Given a directed graph G and a source vertex v, suppose we run the Bellman-Ford algorithm for |V | − 1 iteration to get the distance function dn−1 : V → R. There is no edge that can be relaxed in the |V |th iteration if and only if there is no negative cycle in the graph reachable from s.

Problem 2: NegativeCycle (Detecting)
To prove this, we need to prove the following two statements: No Relaxation Possible =⇒ No Negative Cycle
No Negative Cycle =⇒ No Relaxation Possible
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022
NegativeCycleExists
Given a directed graph G and a source vertex v, suppose we run the Bellman-Ford algorithm for |V | − 1 iteration to get the distance function dn−1 : V → R. There is no edge that can be relaxed in the |V |th iteration if and only if there is no negative cycle in the graph reachable from s.

Problem 2: NegativeCycle (Detecting)
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 13 / 20
⇒ Suppose, for the sake of contradiction, that there exists a negative cycle C = v0,v1,…vk reachable from s with vk = v0. None of the edges can be relaxed, as assumed. Therefore, the following inequalities hold:
dn−1(v1) ≤ dn−1(v0) + weight(v0, v1) …
dn−1(v0) ≤ dn−1(vk−1) + weight(vk−1, v0)

Problem 2: NegativeCycle (Detecting)
Where did we use the fact that the cycle is reachable from s?
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 13 / 20
⇒ Suppose, for the sake of contradiction, that there exists a negative cycle C = v0,v1,…vk reachable from s with vk = v0. None of the edges can be relaxed, as assumed. Therefore, the following inequalities hold:
dn−1(v1) ≤ dn−1(v0) + weight(v0, v1) …
dn−1(v0) ≤ dn−1(vk−1) + weight(vk−1, v0)
Sum up all these inequalities, all the dn−1() terms will cancel out to give 􏰪0≤i≤k−1 weight(vi,vi+1) ≥ 0. Therefore, the cycle is non-negative.

Problem 2: NegativeCycle (Detecting)
Where did we use the fact that the cycle is reachable from s?
The cancellation of dn−1(v)s only works if they are finite numbers,
which would only be guaranteed if v is reachable from s.
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 13 / 20
⇒ Suppose, for the sake of contradiction, that there exists a negative cycle C = v0,v1,…vk reachable from s with vk = v0. None of the edges can be relaxed, as assumed. Therefore, the following inequalities hold:
dn−1(v1) ≤ dn−1(v0) + weight(v0, v1) …
dn−1(v0) ≤ dn−1(vk−1) + weight(vk−1, v0)
Sum up all these inequalities, all the dn−1() terms will cancel out to give 􏰪0≤i≤k−1 weight(vi,vi+1) ≥ 0. Therefore, the cycle is non-negative.

Problem 2: NegativeCycle (Detecting)
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 14 / 20
Proof (Contd.)
⇐ Let there be no negative cycle in the graph G reachable from s. Suppose, for the sake of contradiction, we can relax at least one edge
e = (u,v) ∈ E in the |V|th iteration.
This will contradict the fact that Bellman-Ford algorithm correctly computes the shortest distance for all vertices reachable from s in |V | − 1 iterations, any possible relaxation in |V |th iteration will improve the shortest path, which is not possible.
Therefore, our assumption was wrong, and we cannot relax any edge in the last iteration.

Problem 2: NegativeCycle (Finding)
Note that since our graph had negative cycle, we cannot assume that every dn−1(v) holds the length of the shortest path from s to v. What does it hold then?
After |V|−1 iterations of , the value dn−1(v) is smaller than or equal to every simple path from s to v, including the shortest simple path. Moreover, any further relaxations will only decrease this value further.
S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 15 / 20
πv := v,v.p,…,v.pk be the sequence obtained by iteratively finding the parents until we either reach s, or we see a vertex already in the sequence. Thus, v.pk = s or v.pk = v.pj for some 0 ≤ j < k. It is clear that reverse πv′ = v.pk,...,v would be a path in G. At any stage of the Bellman-Ford algorithm, we claim that if v.pk ̸= s, then this path contains a negative cycle. Problem 2: NegativeCycle (Finding) Contd. S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 16 / 20 Let v.pk = v.pj for some 0 ≤ j < k. Obviously, none of these vertex would be s. Consider the moment we set parent of v.pk−1 to be v.pj. Right before that moment, the value of d(v.pk−1) = d(v.pj) + 􏰪j≤i≤k−2 weight(v.pi,v.pi+1). We will only relax the edge (v.pk−1,v.pj) if following holds: d(v.pj) > d(v.pk−1)+weight(v.pk−1,v.pj)
By substitution, we get
weight(v.pi,v.pi+1) + weight(v.pk−1,v.pj) < 0 j≤i≤k−2 This proves the lemma. Problem 2: NegativeCycle (Finding) Contd. Consider the paths πv′ and πu′ . If either of them contain a cycle C, then it would be negative. so we return C S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 17 / 20 Problem 2: NegativeCycle (Finding) Contd. Consider the paths πv′ and πu′ . If either of them contain a cycle C, then it would be negative. so we return C Suppose neither of the two contain a cycle, then both the paths would would have to end at s. Then, taking the edge (u,v) will give a simple path from s to v that has smaller length than the current path, which is not possible as Bellman-Ford will make each d(v) smaller than the shortest simple path after we run it for |V | − 1 iteration. S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 17 / 20 Problem 2: NegativeCycle (Finding) Contd. Finally, we give the following algorithm to find the negative cycle: Algorithm 1 DetectNegativeCycle 1: Run the Bellman-Ford for |V | − 1 iteration. 2: if̸∃e=(u,v)∈Ethatcanberelaxedthen 3: return No Negative Cycle 5: Let e = (u,v) be the edge that can be relaxed 6: Find the path πv′ and πu′ by iterating through the parents. One of these path will contain a cycle C 7: return C S. Hitarth (HKUST) Tutorial 10 : MST and Shortest Paths 26/04/2022 18 / 20 1 Problem: Zhou is given a directed graph G = (V , E ) and a source vertex v, and he need to find the shortest distance of each vertex from the source s. An ang 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts