S. Hitarth
03/05/2022
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 1 / 18
COMP3711: Design and Analysis of Algorithms Tutorial 11: Dijkstra and Max-Flows
Copyright By PowCoder代写 加微信 powcoder
Problem 1. ShortestCycle
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 2 / 18
Given a directed graph G = (V , E ) with positive edge lengths, given an O(|V|3) algorithm that returns the length of the shortest cycle in the graph (if it doesn’t exists, say so).
Problem 1. ShortestCycle
Consider the following simpler problem: find the length of the shortest cycle in G containing the vertex s
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 2 / 18
Given a directed graph G = (V , E ) with positive edge lengths, given an O(|V|3) algorithm that returns the length of the shortest cycle in the graph (if it doesn’t exists, say so).
Problem 1. ShortestCycle
Consider the following simpler problem: find the length of the shortest cycle in G containing the vertex s
Any cycle containing s must have the form s → v1 → …u → s
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 2 / 18
Given a directed graph G = (V , E ) with positive edge lengths, given an O(|V|3) algorithm that returns the length of the shortest cycle in the graph (if it doesn’t exists, say so).
Problem 2. ShortestCycle Contd.
If we can find the shortest path from s to all such u that have incoming edge to s, then we can find the shortest cycle computing minu∈V (shortest path(s, u) + length(u, s)). Here, we assume length(u, s) = ∞ if the edge doesn’t exist.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 3 / 18
Problem 2. ShortestCycle Contd.
If we can find the shortest path from s to all such u that have incoming edge to s, then we can find the shortest cycle computing minu∈V (shortest path(s, u) + length(u, s)). Here, we assume length(u, s) = ∞ if the edge doesn’t exist.
We can find the shortest path from s to all other vertices in G in O(|V|2) time using the naive Dijkstra implementation. We can do the computation min in O(|V|) time. Therefore, this takes
O(|V | log |V |) ⊆ O(|V |2) time.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 3 / 18
Problem 2. ShortestCycle Contd.
If we can find the shortest path from s to all such u that have incoming edge to s, then we can find the shortest cycle computing minu∈V (shortest path(s, u) + length(u, s)). Here, we assume length(u, s) = ∞ if the edge doesn’t exist.
We can find the shortest path from s to all other vertices in G in O(|V|2) time using the naive Dijkstra implementation. We can do the computation min in O(|V|) time. Therefore, this takes
O(|V | log |V |) ⊆ O(|V |2) time.
For the original problem, we just have to perform the Step 3 for each vertex!
In total, this will take O(|V|3) time!
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 3 / 18
Problem 3a. Shortest Path with 3q hops
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 4 / 18
Given a directed, weighted, connected graph G = (V,E), a source A and a destination Z, find a shortest path from A to Z where the number of hops on the path is divisible by 3. (hops : Number of edges in the path)
Problem 3a. Shortest Path with 3q hops
Consider the following example. Here our goal is to find the shortest path from A to Z where the number of hops is divisible by 3.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 4 / 18
Given a directed, weighted, connected graph G = (V,E), a source A and a destination Z, find a shortest path from A to Z where the number of hops on the path is divisible by 3. (hops : Number of edges in the path)
Problem 3a. Shortest Path with 3q hops Contd. Can we use Dijkstra on this graph with A as source and find the
shortest path to Z?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 5 / 18
Problem 3a. Shortest Path with 3q hops Contd. Can we use Dijkstra on this graph with A as source and find the
shortest path to Z?
No, because it will return the path A → B → Z. Here, the number of hops is not divisible by 3.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 5 / 18
Problem 3a. Shortest Path with 3q hops Contd. Can we use Dijkstra on this graph with A as source and find the
shortest path to Z?
No, because it will return the path A → B → Z. Here, the number of hops is not divisible by 3.
So, how we can solve the problem? Clearly we need to construct some other graph and apply Dijkstra on that graph to solve the problem.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 5 / 18
Problem 3a. Shortest Path with 3q hops Contd.
Note that there are two things to consider here Current Location
Length of the path traversed divisible by 3 or not.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 6 / 18
Problem 3a. Shortest Path with 3q hops Contd.
Note that there are two things to consider here Current Location
Length of the path traversed divisible by 3 or not.
We create 3 nodes for each node in the original graph.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 6 / 18
Problem 3a. Shortest Path with 3q hops Contd.
Note that there are two things to consider here Current Location
Length of the path traversed divisible by 3 or not.
We create 3 nodes for each node in the original graph.
For example for the node A we create three nodes (A, 0), (A, 1) and (A, 2) where 0, 1 and 2 represents whether the length of the path traversed leaves remainder 0, 1 or 2 when divided by 3.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 6 / 18
Problem 3a. Shortest Path with 3q hops Contd.
Note that there are two things to consider here Current Location
Length of the path traversed divisible by 3 or not.
We create 3 nodes for each node in the original graph.
For example for the node A we create three nodes (A, 0), (A, 1) and (A, 2) where 0, 1 and 2 represents whether the length of the path traversed leaves remainder 0, 1 or 2 when divided by 3.
We create an edge in between a vertex (A,i) to (B,j) iff there is an edge from A to B in the original graph and j = (i + 1)mod3.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 6 / 18
Problem 3a. Shortest Path with 3q hops Contd.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 7 / 18
Problem 3a. Shortest Path with 3q hops Contd. Now, just find the shortest path from (A,0) to (Z,0) using Dijkstra.
Why does it work? and How much time will it take?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 8 / 18
Problem 3a. Shortest Path with 3q hops Contd. Now, just find the shortest path from (A,0) to (Z,0) using Dijkstra.
Why does it work? and How much time will it take?
It works because Dijkstra algorithm would give the shortest path from A to Z in the original graph. Now since we are taking the shortest path from (A, 0) to (Z , 0) hence, the number of hops is divisible by 3. It will take 3mlog(3n) = mlogn time where m and n are the number of edges and vertices respectively in the original graph.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 8 / 18
Problem 3a. Shortest Path with 3q hops Contd. Now, just find the shortest path from (A,0) to (Z,0) using Dijkstra.
Why does it work? and How much time will it take?
It works because Dijkstra algorithm would give the shortest path from A to Z in the original graph. Now since we are taking the shortest path from (A, 0) to (Z , 0) hence, the number of hops is divisible by 3. It will take 3mlog(3n) = mlogn time where m and n are the number of edges and vertices respectively in the original graph.
How much time does the construction of the transformed graph take?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 8 / 18
Problem 3a. Shortest Path with 3q hops Contd. Now, just find the shortest path from (A,0) to (Z,0) using Dijkstra.
Why does it work? and How much time will it take?
It works because Dijkstra algorithm would give the shortest path from A to Z in the original graph. Now since we are taking the shortest path from (A, 0) to (Z , 0) hence, the number of hops is divisible by 3. It will take 3mlog(3n) = mlogn time where m and n are the number of edges and vertices respectively in the original graph.
How much time does the construction of the transformed graph take? O(m + n). Why O(m + n)?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 8 / 18
Problem 3a. Shortest Path with 3q hops Contd. Now, just find the shortest path from (A,0) to (Z,0) using Dijkstra.
Why does it work? and How much time will it take?
It works because Dijkstra algorithm would give the shortest path from A to Z in the original graph. Now since we are taking the shortest path from (A, 0) to (Z , 0) hence, the number of hops is divisible by 3. It will take 3mlog(3n) = mlogn time where m and n are the number of edges and vertices respectively in the original graph.
How much time does the construction of the transformed graph take? O(m + n). Why O(m + n)?
We can apply BFS starting from A in the original graph and for each edge (a,b) traversed in the original graph we add three edges (a,i) to (b,j) where j = (i +1) mod 3 and a,b ∈ {A,B,C,D,Z} and
i ∈ {0, 1, 2}.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 8 / 18
Problem 3b. Generalised Version
How to find the shortest path where the number of hops is divisible by k where k can be any parameter need not be a constant?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 9 / 18
Problem 3b. Generalised Version
How to find the shortest path where the number of hops is divisible by k where k can be any parameter need not be a constant?
We simply take k copies of each node instead of 3 copies and use Dijkstra’s Algorithm to find the shortest path from (A,0) to (Z,0). How much time will it take?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 9 / 18
Problem 3b. Generalised Version
How to find the shortest path where the number of hops is divisible by k where k can be any parameter need not be a constant?
We simply take k copies of each node instead of 3 copies and use Dijkstra’s Algorithm to find the shortest path from (A,0) to (Z,0). How much time will it take?
O(kmlogkn).
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 9 / 18
Problem 3c. DAG Version
Now, suppose the original graph is a DAG. Then how to find the shortest path where the number of hops is divisible by k?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 10 / 18
Problem 3c. DAG Version
Now, suppose the original graph is a DAG. Then how to find the shortest path where the number of hops is divisible by k?
Use DAG-SSSP that is topologically sort all the vertices in the transformed graph and then relax the edges in that order. How much time will it take?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 10 / 18
Problem 3c. DAG Version
Now, suppose the original graph is a DAG. Then how to find the shortest path where the number of hops is divisible by k?
Use DAG-SSSP that is topologically sort all the vertices in the transformed graph and then relax the edges in that order. How much time will it take?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 10 / 18
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 11 / 18
Problem Statement
A Kangaroo has its house on the left bank of a river. N rocks are placed on the river. The width of the river is D.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 11 / 18
Problem Statement
A Kangaroo has its house on the left bank of a river. N rocks are placed on the river. The width of the river is D.
There are two sizes of rocks. The bigger ones can withstand any weight but the smaller ones start to drown as soon as any mass is placed on it.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 11 / 18
Problem Statement
A Kangaroo has its house on the left bank of a river. N rocks are placed on the river. The width of the river is D.
There are two sizes of rocks. The bigger ones can withstand any weight but the smaller ones start to drown as soon as any mass is placed on it.
The Kangaroo has to go to the right bank to take its child and return back home.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 11 / 18
Problem Statement
A Kangaroo has its house on the left bank of a river. N rocks are placed on the river. The width of the river is D.
There are two sizes of rocks. The bigger ones can withstand any weight but the smaller ones start to drown as soon as any mass is placed on it.
The Kangaroo has to go to the right bank to take its child and return back home.
It can land on a small rock only once but it can land on a big rock any number of times.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 11 / 18
Problem Statement
A Kangaroo has its house on the left bank of a river. N rocks are placed on the river. The width of the river is D.
There are two sizes of rocks. The bigger ones can withstand any weight but the smaller ones start to drown as soon as any mass is placed on it.
The Kangaroo has to go to the right bank to take its child and return back home.
It can land on a small rock only once but it can land on a big rock any number of times.
Can you find a path such that the maximum distance the Kangaroo has to jump is minimized?
Problem 4. Leaping Kangaroo
First, let’s ignore the fact that we need to find the path with the smallest maximum edge length.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 12 / 18
Problem 4. Leaping Kangaroo
First, let’s ignore the fact that we need to find the path with the smallest maximum edge length.
We need to find a path from our source(left bank) to our sink(right bank), and then back again, that does not cross any of the “small” vertices more than once.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 12 / 18
Problem 4. Leaping Kangaroo
First, let’s ignore the fact that we need to find the path with the smallest maximum edge length.
We need to find a path from our source(left bank) to our sink(right bank), and then back again, that does not cross any of the “small” vertices more than once.
Keeping track of the state of the vertices after going to the sink (right bank) and then coming back seems difficult!
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 12 / 18
Problem 4. Leaping Kangaroo
First, let’s ignore the fact that we need to find the path with the smallest maximum edge length.
We need to find a path from our source(left bank) to our sink(right bank), and then back again, that does not cross any of the “small” vertices more than once.
Keeping track of the state of the vertices after going to the sink (right bank) and then coming back seems difficult!
But we can transform it into the equivalent problem of finding two paths from the source to the sink.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 12 / 18
Problem 4. Leaping Kangaroo
To find two vertex disjoint paths from the source to the sink, we need to find a flow of at least 2 in a flow graph with vertex capacities 1.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 13 / 18
Problem 4. Leaping Kangaroo
To find two vertex disjoint paths from the source to the sink, we need to find a flow of at least 2 in a flow graph with vertex capacities 1.
What is vertex capacity?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 13 / 18
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 14 / 18
Vertex Capacities
A graph has vertex capacities if the capacity restrictions are on the vertices instead of on the edges.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 14 / 18
Vertex Capacities
A graph has vertex capacities if the capacity restrictions are on the vertices instead of on the edges.
How to interpret it as a flow network with edge weights?
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 14 / 18
Vertex Capacities
A graph has vertex capacities if the capacity restrictions are on the vertices instead of on the edges.
How to interpret it as a flow network with edge weights?
This is solved by splitting each vertex into two vertices, an “in” vertex and an “out” vertex.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 14 / 18
Vertex Capacities
A graph has vertex capacities if the capacity restrictions are on the vertices instead of on the edges.
How to interpret it as a flow network with edge weights?
This is solved by splitting each vertex into two vertices, an “in” vertex and an “out” vertex.
For some vertex u with capacity cu, we add an edge from inu to outu with capacity cu.
Problem 4. Leaping Kangaroo
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 14 / 18
Vertex Capacities
A graph has vertex capacities if the capacity restrictions are on the vertices instead of on the edges.
How to interpret it as a flow network with edge weights?
This is solved by splitting each vertex into two vertices, an “in” vertex and an “out” vertex.
For some vertex u with capacity cu, we add an edge from inu to outu with capacity cu.
The edge capacities for the edges in the original graph are infinite.
Problem 4. Leaping Kangaroo
To find two vertex disjoint paths from the source to the sink, we need to find a flow of at least 2 in a flow graph with vertex capacities 1.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 15 / 18
Problem 4. Leaping Kangaroo
To find two vertex disjoint paths from the source to the sink, we need to find a flow of at least 2 in a flow graph with vertex capacities 1.
But this formulation will only allow us to visit any of the “big” vertices once.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 15 / 18
Problem 4. Leaping Kangaroo
The only thing that enforces that restriction in our graph is the vertex capacity of 1 in our original construction.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 16 / 18
Problem 4. Leaping Kangaroo
The only thing that enforces that restriction in our graph is the vertex capacity of 1 in our original construction.
So if we set the vertex capacity for every “big” vertex to be infinite, then we have a solution.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 16 / 18
Problem 4. Leaping Kangaroo
The only thing that enforces that restriction in our graph is the vertex capacity of 1 in our original construction.
So if we set the vertex capacity for every “big” vertex to be infinite, then we have a solution.
Practically, an edge with capacity infinity is an edge with a large enough finite capacity that it’ll never be reached.
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 16 / 18
Problem 4. Leaping Kangaroo
Now that we know how to find a valid path at all, how do we then find the one with the smallest maximum edge weight?
S. Hitarth (HKUST) Tutorial 11 : MST and Shortest Paths 03/05/2022 17 / 18
Problem 4. Leaping Kangaroo
Now that we know how to find a valid path at all, how do we then find the one with the smallest maximum edge weight?
It can be seen that if we can find a solution with the maximum edge weight being at most k, then we can
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com