程序代写代做代考 algorithm Solutions to Homework 5
Solutions to Homework 5
Debasish Das
EECS Department, Northwestern University
ddas@northwestern.edu
1 Problem 4.17
We want to run Dijkstra algorithm whose edge weights are integers in the range 0,1,…,W where W is a
relatively small number.
a)Using a bucket implementation (also known as Dial’s implementation) Dijkstra algorithm can be made to
run in O(W |V |+ |E|). Idea is to find an upper bound on shortest distance labels. Since the maximum edge
weight is W and a vertex can be updated at most |V |−1 times, we get a bound of O(W |V |) on shortest path
distances. Using the property of Dijkstra algorithm that the distance labels that are designated permanent
are non-decreasing we can present the following algorithm
procedure Efficient-Dijkstra1(G,l,W,s)
Input: Graph G=(V,E), edge weights le,
Max edge weight W, vertex s ∈ V
Output: Shortest path distance labels
for all vertices v ∈ V :
dist(v) = ∞
prev(v) = nil
bucket(v) = nil
Create an array B of size W |V |:
B[i] keep vertex of distance label i
B[0] = s,dist(s)=0,bucket(s)=0
index = 0
while index 6= W |V |
Increment index:
B[index] 6= ∅
u = B[index]
for all edges (u,v) ∈ E:
temp = dist(v)
if dist(v) > dist(u) + l(u,v):
dist(v) = dist(u)+l(u,v)
prev(v) = u
B[dist(v)] = v
if temp 6= ∞:
Remove v from B[temp]
Doubly linked list should be used for array B, which allows us to do the following operations in O(1) time:
(1) Checking whether a bucket is empty or nonempty
(2) Deleting an element from a bucket
(3) Adding an element to the bucket
(b)The algorithm is same as the algorithm shown on Page 110. We claim the following lemma
1
Lemma 1 If edge weights are integers in the range of 0,1,…,W, where W is a relatively small number then
at each iteration of dijkstra algorithm, there can be at most |W | elements in the heap
Proof: We use induction to prove our claim. We refer to the minimum key of the heap as min-k and the
maximum key of the heap as max-k.
Initialization: On the first iteration of Dijkstra’s algorithm we can add at most W elements in the heap as
number of edges can be at most W . Therefore max-k−min-k = W
Hypothesis: For i-th iteration of Dijkstra’s algorithm we have the following max-ki −min-ki ≥ W .
Induction: During the i+1-th iteration, we choose the minimum key from the heap which is min-ki. Suppose
the respective vertex is v. In worst case we will update all the vertices connected to v and update the keys
in the heap. Since edge weights are bounded by |W |, new min-k and max-k of the heap at i+1-th iteration
is given by
max-ki+1 = max(min-ki + W,max-ki)
min-ki+1 ≥ min-ki
From the above equations we can establish that
max-ki+1 −min-ki+1 ≤ W or
max-ki+1 −min-ki+1 ≤ max-ki −min-ki ≤ W
which validates our claim.
Now since at every iteration of Dijkstra’s algorithm there can be at most |W | elements in the heap, O((|V |+
|E|) log V ) bound changes to O((|V |+ |E|) log W ). Note that this is the property of this problem which leads
to an efficient bound on the complexity.
2 Problem 4.22
Given a directed graph G=(V,E) whose nodes are ports, and which has edges between each pair of ports.
For any cycle C in this graph, the profit-to-cost ratio is
r(C) =
∑
(i,j)∈C pj∑
(i,j)∈C cij
(1)
The maximum ratio achievable over all cycles is called r∗. Given each edge (i,j) we assign a weight of
wij = r · cij − pj .
(a)
Lemma 2 Show that if there is a cycle of negative weight, then r < r∗ Proof: Suppose the graph G contains a cycle of negative weight. For that cycle ∑ (i,j)∈C(r · cij − pj) < 0 which implies that r < ∑ (i,j)∈C pj∑ (i,j)∈C cij (2) Therefore the r we choose is a lower bound of r∗. (b) Lemma 3 Show that if all cycles in the graph have strictly positive weight then r > r∗
Proof: If G contains no negative cycle then for every directed cycle C,
∑
(i,j)∈C(r · cij − pj) ≥ 0 which
implies that
r ≥
∑
(i,j)∈C pj∑
(i,j)∈C cij
(3)
Therefore in this case the r we choose is a upper bound of r∗
2
Corollary 0.1 If G contains a zero weight cycle, then r = r∗
(c)The algorithm we present for this part is a binary search algorithm. Since we know the upper bound and
lower bounds on r∗ we choose a r from the interval where r is feasible. Upper bound of r is given by R where
as lower bound of r is 0. The lower bound is crude and better bound can be obtained. Therefore r is feasible
in interval (0, R).
procedure max-pcr-cycle(G,C,P,�)
Input: G = (V,E), Transportation cost C = {cij : (i, j) ∈ E}
Profit P = {pj : j ∈ V },accuracy �
Output: r∗ and corresponding cycle
lb = 0, ub = R
r = lb+ub
2
do
temp-r = r
for each edge (i,j) ∈ E
wij = temp− r · cij − pj
flag1 = NegativeCycleDetect(G,W):
W={wij : (i, j) ∈ E}
if flag1 = true:
Update the lb:
lb = temp-r
else
flag2 = ZeroCycleDetect(G,W,Cycle)
if flag2 = true:
return temp-r and C
else Update the ub:
ub = temp-r
r = lb+ub
2
while(|temp-r− r| > �)
NegativeCycleDetect(G,W) is straightforward. See Section 4.6.2 for its detail. The idea is to do one more
iteration in Bellman-Ford algorithm and keep track whether any shortest path distance labels change in the
final iteration or not. If they change, then we have found a negative cycle. If NegativeCycleDetect terminates
with true, it implies that shortest distance labels have been correctly obtained. ZeroCycleDetect then checks
whether the resultant graph has any zero cycle length cycle or not. If not then we upate upper bound. If
there is a zero length cycle then we return the maximum profit-to-cost ratio and corresponding cycle.
procedure ZeroCycleDetect(G,W,Cycle)
Input: G = (V,E) with shortest path distance on vertex,
W={wij : (i, j) ∈ E}
Output: true if zero weight cycle exists:
Cycle stores one such cycle
false if no zero weight cycle exists
Construct a graph G0 = (V 0, E0):
G0 = V 0
for each (i,j) ∈ E
if dist(i) + l(i,j) = dist(j):
insert (i,j) to E0
if cycle identified in G0:
return true and Cycle
else
return false
3
Correctness of ZeroCycleDetect comes from the following lemma
Lemma 4 If G has a zero length cycle then G0 also has a cycle
Proof: Let W be a zero length cycle in G. Then∑
(i,j)∈W
wij = 0 =
∑
(i,j)∈W
dist(i) + wij − dist(j) (4)
Note that over a cycle, dist(i) and dist(j) pairs will cancel each other. But dist(i) + wij ≥ dist(j) (since
they are shortest path labels). Therefore dist(i) + wij − dist(j) ≥ 0. Therefore each of the terms dist(i) +
wij − dist(j) should be 0 to satisfy Equation 4. Since we kept only those edges in G0 whose distance label
satisfies the above condition, G0 must have cycle W.
Runtime analysis of the algorithm: Each iteration of the binary search reduces the feasible search space
for r∗ by half. Let the number of iterations be n. We have R
2n
= �. Therefore n = log R
�
. Negative cycle
detection algorithm has a complexity of O(|V ||E|) where as zero cycle detection takes O(|V |+ |E|). Overall
complexity of the algorithm is given by O(|V ||E| log R
�
)
3 Problem 5.5
(a)
Lemma 5 If each edge weight is increased by 1, the minimum spanning tree doesn’t change
Proof: Suppose initially the minimum spanning tree was T . After each edge weight is increased by 1, the
minimum spanning tree changes to T̂ . Therefore there will be at least an edge (u, v) ∈ T but (u, v) /∈ T̂ .
Suppose we add edge (u, v) to the tree T̂ . T ∗ = T̂ +(u, v). Since (u, v) was not in T̂ therefore (u, v) must be
the longest edge in the cycle C formed in T ∗. But since (u, v) is the longest edge it cannot be in the MST
T̂ (We prove this lemma in Problem 5.22). (u, v) is the longest edge and therefore when we decrease each
edge weight by 1, (u, v) will still be the longest edge in cycle C formed in T . But longest edge (u, v) can not
be contained in MST T . Therefore (u, v) /∈ T which is a contradiction. It implies that trees T and T̂ are
same.
(b)We show an example in Figure 1 where the shortest path can change due to increase in weight by 1.
Before increasing the edge weights, shortest path from vertex 1 to 4 was through 2 and 3 but after increasing
Figure 1: Counterexample for Shortest Path Tree
the edge weights shortest path to 4 is from vertex 1.
4 Problem 5.8
If the graph is directed it is possible for a tree of shortest paths from s and a minimum spanning tree in G
not to share any edges. A counterexample is shown in Figure 2 (taken from Xi Chen’s solution). MST will
4
have the edges {(3,1),(3,2),(2,4)}. Shortest path tree rooted at vertex 1 has the edges {(1,4),(1,2),(4,3)}.
However if the graph is undirected, by the cut property minimum cut edge is in MST. According to Dijkstra
Figure 2: Counterexample for MST and Shortest Path Tree
algorithm, minimum cut edge must be in shortest path tree.
5 Problem 5.22
This problem presents an algorithm for finding minimum spanning trees. The algorithm is based on the
following property
Lemma 6 Pick any cycle C in the graph and let e be the heaviest edge in that cycle. Then there is a
minimum spanning tree that does not contain e.
(a)Proof: Suppose there is a minimum spanning tree which contains e. If we add one more edge to the
spanning tree we will create a cycle. Suppose we add edge ê to the spanning tree which generated cycle C.
We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal
which implies that e must not be in minimum spanning tree and we get a contradiction
(b)Correctness of the algorithm follows from the lemma. Since we are looking at all the edges in decreasing
weight, we are choosing the heaviest edge first. That edge must not be in the MST if it is part of a cycle C.
Presented algorithm checks for a cycle and remove the edge from the graph if it is part of a cycle.
(c)Linear time algorithm to check whether there is a cycle containing a specific edge e: Let e = (u, v). Start
a DFS from u and exclude edge e while considering outgoing edges from u. Check if e is a back-edge in
resultant DFS tree
(d)Complexity Analysis: Total number of edges in a MST is given by |V | − 1. Therefore on the worst case
the algorithm will remove E − |V |+ 1 edges from G to obtain the MST. At each iteration of the algorithm,
cycle detection takes O(V + E). Therefore total running time is given by O((|E| − |V |+ 1) · (V + E)).
6 Problem 5.30
We present the algorithm first followed by correctness proof
procedure ternary-huffman(f)
Input: An array f[1…n] of frequencies
Output: An encoding tree:
n leaves if n is odd
n+1 leaves if n is even
if n is even:
add a new element f[n+1] = 0
5
let H be a priority queue of integers ordered by f
for i = 1 to size(f): insert(H,f[i])
for l = size(f) to 2n-3:
i = deletemin(H), j = deletemin(H), k = deletemin(H)
create a node numbered l with children i,j,k:
f[l] = f[i]+f[j]+f[k]
insert(H,l)
Ternary Huffman Algorithm in essence is similar to binary huffman but there are some distinct differences.
We add a node of zero frequency if n is even. This is necessary as we want to form a complete ternary tree.
Objective function of ternary huffman algorithm is given by∑
a∈σ
h(a) · f(a) h(a),f(a) are height and frequency of a (5)
The following three lemmas are essential for proof of correctness
Lemma 7 There is always an optimal tree such that three letters of minimum frequency must be combined
together
Lemma 8 After the combination with the sum of frequency as the frequency for the new tree, the problem
becomes same problem of smaller size
Lemma 9 If at any point of time three letters of minimum frequency cannot be combined then the resultant
tree is not optimal
Proof of lemma 7-8 are already presented in class. I am not repeating it again. If you are not clear about it,
drop by during my office hours and I can explain it to you.
Proof: Consider at some point of time we cannot find 3 letters of minimum frequency to combine. Without
any loss of generality assume we are left with nodes i and j with frequency f(i) and f(j). If we combine
them the cost of the tree formed will be
h(i)f(i) + h(j)f(j) (6)
Consider any children ci of i. h(ci) = 1 + h(i). Therefore cost of the tree considering children of i can be
written as
(1 + h(i))(f(ci) + k) + h(j)f(j) where k = f(i)− f(ci) (7)
Now we can reduce the cost of the tree if we bring ci to the height of j
(1 + h(i))(f(ci) + k) + h(j)f(j) > (1 + h(i))k + h(j)f(j) + h(j)f(ci) (8)
as h(i) is equal to h(j).
Optimality condition is violated if at any point of time we cannot combine three letters of minimum frequency.
To satisfy this constraint we add a additional letter of 0 frequency when n is even as it is evident from
Equation 8 that
(1 + h(i))(f(ci) + k) + h(j)f(j) = (1 + h(i))k + h(j)f(j) + h(j)f(ci) when f(ci) = 0 (9)
6
