Scribd
Upload
42 views

Algorithm 2016 Fall HW4 Sol

This document contains solutions to homework questions about algorithms. It discusses using an all-pairs shortest path algorithm to detect negative weight cycles, how to construct the transitive closure of a graph in O(VE) time, and finding that a given system is infeasible due to a negative length cycle.

Uploaded by

woogie boogie
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
42 views

Algorithm 2016 Fall HW4 Sol

This document contains solutions to homework questions about algorithms. It discusses using an all-pairs shortest path algorithm to detect negative weight cycles, how to construct the transitive closure of a graph in O(VE) time, and finding that a given system is infeasible due to a negative length cycle.

Uploaded by

woogie boogie
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

2016 Algorithm HW4

Solutions
指導教授 : 謝孫源 教授
助教: 盧緯 張耕華 楊順翔 許景添
Question 1(10pts)

Solution:
 The presence of a negative-weight cycle can be determined by
looking at the diagonal of the matrix L(n−1) computed by an all-
pairs shortest-path algorithm. If the diagonal contains any
negative number there must be a negative-weight cycle.
Question 2(10pts)

Solution:
 The identity matrix for “multiplication” should look as the one given
in the exercise since 0 is the identity for + and ∞ is the identity for
min.
Question 3(10pts)

Solution:
 We wish to compute the transitive closure of a directed graph
G = (V, E). Construct a new graph G* = (V, E* ) where E* is initially
empty. For each vertex v traverse the graph G adding edges for every
node encountered in E* . This takes O(VE) time.
Question 4(10pts)

Solution:
 PPT CH24 P8.9
Question 5(10pts)

Solution:

S A B C D E
i=1 0 9 11 12 8 7
i=2 0 3 11 7 8 7
i=3 0 3 5 6 8 7
i=4 0 3 5 6 8 7
Question 6(10pts)

Solution:
Question 7(10pts)

Solution:
 After forming the augmented constraint graph and seeking the shortest
path from node 0 to all other nodes, using an algorithm with negative
length cycle detection, one finds there is a negative length cycle (2, 3,
5, 4, 2) with length 1 − 7 + 10 − 6 = −2. Thus the system is infeasible.
Question 8(10pts)

Solution:
 Since there is an arc of length 0 from node 0 to every other node, the
label on every node (representing the length of the shortest path found
so far from node 0 to that node) is set to 0 in the first step. Since it is
only modified if a shorter path is found, of necessity such a path must
have length less than 0, and so cannot be positive; the answer is “no”.
Question 9 (10pts)

Solution:
 Slow-All-Pairs-Shortest-Paths (5%)
 𝐿𝐿1 (1%) 𝐿𝐿2 (1%)

 𝐿𝐿3 (1%) 𝐿𝐿4 (1%)

 𝐿𝐿5 (1%)
Question 9(10pts)

Solution:
 Faster-All-Pairs-Shortest-Paths(5%)
 𝐿𝐿2 (1%) 𝐿𝐿4 (2%)

 𝐿𝐿8 (2%)
Question 10(10pts)

Solution:
 (I) True or False (3%)
 Running time = Θ(𝑛𝑛3 lg 𝑛𝑛)
 Space requirement = Θ(𝑛𝑛2 lg 𝑛𝑛) or Θ(𝑛𝑛2 )
 (II) False (3%)
 Counter example
G1 4 G2 6
-2
B C 1 0
B C 3

A E A E
5 D -1 7 D 1

Shortest path: A->E Shortest path: A->E


A->B->C->E A->D->E

 (III) True (2%)


 (IV) True (2%)

You might also like