CS5800-Homework 11 Solved

1             ASSP-FAST
Let  be the minimum weight of any path from vertex i to vertex j that contains at most m edges. When m = 0, there is a shortest path from i to j with no edges if and only if i = j. Thus,

(

                                                                                lij(0) =     0,        if i = j

                                                                                                   ∞,      if i ̸= j

For m ≤ 1, we compute   as the minimum of  (the weight of a shortest path from i to j consisting of at most m edges. obtained by looking at all possible predecessors k of j. Thus, we recursively define

 

The latter equality follows since wjj = 0 for all j.

EXTEND-SP: Taking as our input the matrix W = (wij), we now computed a series of matrices L([1]),L([2]),...,L(n−1), where for m = 1,2,...,n−1, we have .

The final matrix L(n−1) contains the actual shortest-path weights. Observe that   for all vertices i,j ∈ V , and so L(1) = w. The heart of the algorithm is, given matrices L(m−1) and w, returns the matrix L(m). That is, it extends the shortest paths computed so far by one more edges.

ASSP-FAST: In each iteration of the while loop, we compute L(2m) = (L(m))2, starting with m = 1. At the end of each iteration, we double the value of m. The final iteration computes L(n−1) by actually computing L(2m) for some n − 1 ≤ 2m < 2n − 2. By equation .

The next time the m < n − 1 performed, m has been doubled, so now m ≥ n − 1, and the procedure returns the last matrix it computed.

 

Algorithm 1

3:                Let ) be a new n × n matrix

4:               for i = 1 to n do

5:                       for j = 1 to n do

6:                              lij′ = ∞

7:                              for 

8:                                         lij = min(lij,lik + wkj)

9:                             end for

10:                   end for

11:           end for

12:          return L′ 13: end function

14:

15: function ASSP-Fast(w)
16:            n = w.rows

17:            L(1) = w

18:           m = 1

19: while m < n − 1 do 20: letL(2m) be a new n × n matrix

21:                           L(2m) = Extend-SP(L(m),L(m))
22:                   m = 2m

23:           end while

24:            return L(m)

25: end function

 

2             Exercise 24.1-3
 

Algorithm 2

 

1: function Initialize-Single-Source(G,s)
2:               for each vertex v ∈ G.V do

3:                      v.d = ∞

4:                       v.π = NIL

5:             end for

6:              s.d = 0

7: end function

8:

9: function Relax(u,v,w)

10:              if v.d > u.d + w(u,v) then

11:                     v.d = u.d + w(u,v)

12:                    v.π = u

13:           end if

14: end function

15:

16: function Bellman-Ford(G,w,s) Initial-Single-Source(G,s)
17:             for i = 1 to |G.V | − 1 do

18:                     for each v in G.V do

19:                            T = v.d

20:                   end for

21:                     for each edge(u,v) ∈ G.E do

22:                              Relax(u,v,w)

23:                   end for

24:                     for each edge(u,v) ∈ G.E do

25:                             if v.d ̸= T[].d then

26:                                      if v.d > u.d + w(u,v) then

27:                                             return FALSE

28:                                  end if

29:                           end if

30:                   end for

31:           end for

32:             return TRUE

33: end function

 

If the value of v.d at the end of the loop does not change from the value of v.d at the beginning of the loop, the loop is the (m + 1)th passes.

3             Exercise 24.2-2
The DAG-SHORTEST-PATH algorithm starts by topologically sorting the directed acyclic graph (dag) to impose a linear ordering on the vertices. If the dag contains a path form vertex u to vertex v, then u precedes v in the topological sort. Topological sort ensures that edges are arranged in a linear fashion. If the edges are arranged in a linear fashion, and use perform relaxation then the last vertex will have its edges already visited because if there exist edge (u,v) then u appears before v in the ordering. So we can perform the looping for the first |V | − 1 vertices because the vertices after topological sort will be ordered.

4             Exercise 24.3-4
Dijkstra’s algorithm solves the single-source shortest-path problem on a weighted, directed graph G = (V,E) for the case in which all edge weights are noonegative. Therefore, w(u,v) ≤ 0 for each edge (u,v) ∈ E. Dijkstra’s algorithm maintains a set s of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatly selects the vertex u ∈ V − S with the minimum shortest-path estimate, add u to S, and relaxes all edges leaving u.

 

Algorithm 3

 

1: function Check-Output(G,w,s)

2:                    Topological-Sort(G)                                            ▷ find the linear order of the vertices

3:                      Initialize-Single-Source(G,s)
4:          for each edge (u,v) ∈ G.E do 5:             Relax(u,v,w)

6:             end for

7: end function

 

The topological sort is used to find the vertices in the linear order of consideration. The correctness of the Professor Gaedel’s procedure would rely on checking the vertex weight v.d is equal to minimum of (u,v). The program terminates successfully once all the edges are relaxed. The running time of initialization would take O(V ) and relaxation would take O(V +E). Thus, the running time of algorithm would be O(V + E).

5             Transitive Closure
Given a directed graph G = (V,E) with vertex set V = {1,2,...,n}, we might wish to determine whether G contains a path from i to j for all vertex pairs i,j ∈ V . We define the transitive closure of G as the graph G∗ = (V,E∗), where E∗ = {(i,j) : there is a path from vertex i to vertex j in G}.

6             Exercise 25.1-6
FIND-PRE-MATRIX: A predecessor matrix Π = (πij), where πij is NIL if either i = j or there is no path from i to j, and otherwise πij is processor of j on some shortest path form i.

PRINT-ASSP: The following procedure is a modified version of the PRINTPATH procedure from Chapter 22, prints a shortest path from vertex i to vertex j. Give the predecessor matrix Π, the PRINT-ASSP will print the vertices on a given shortest path.

 

Algorithm 4

 

1: function Find-Pre-Matrix(L,w)
2:               n = L.rows

3:                 let Π = (πij) be a new n × n matrix

4:               for i = 1 to n do

5:                       for j = 1 to n do

6:                               for k = 1 to n do

7:                                          if Lij == lik + wkj then

8:                                              πij = k

9:          else 10:               πij = NIL

11:                                  end if

12:                           end for

13:                   end for

14:           end for

15:           return Π

16: end function

17:

18: function Print-ASSP(Π,i,j)
19:              if i == j then

20:                   print i

21:          else

22:                       if πij == NIL then

23:                              print ”no path from ′i′ to ′j′ exists

24:                  else

25:                                 Print-ASSP(Π,i,πij)
26:                           print j

27:                   end if

28:           end if

29: end function

 

7             Exercise 25.2-1
Let   be the weight of a shortest path from vertex i to vertex j for which all intermediate vertices are in the set {1,2,...,k}. When k = 0, a path from vertex i to vertex j with no intermediate vertex numbered higher than 0 has no intermediate vertices at all. Such a path has at most one edge, and hence d(0)ij = wij. Following the above discussion, we define   recursively by

( (k)                        wij,
if k = 0
                                                     d      =

                                                                                                                                   ,      if k ≤ 1

Becasue for any path, all intermediate vertices are in the set {1,2,...,n}, the matrix   gives the final answer:   for all i,j ∈ V .

 0

 1

∞

D(0) = −4

 ∞



∞
∞ ∞              ∞ −1

0     ∞     2         ∞

2      0    ∞         ∞

∞ ∞    0          3 7           ∞ ∞    0

5     10   ∞         ∞
∞

∞

−8

∞

∞

0
 0

 1

∞

D(1) = −4

 ∞



∞
∞ ∞              ∞ −1

0     ∞     2      0

2      0    ∞         ∞

∞ ∞        0        −5

7       ∞ ∞       0

5     10   ∞         ∞
∞

∞

−8

∞

∞

0
 0

 1

 3

D(2) = −4

 

 8

6
∞ ∞              ∞ −1

0 ∞ 2 0 2 0 4 2

∞ ∞        0        −5

7     ∞     9      0

5     10    7      5
∞

∞

−8

∞

∞

0
 0

 1

 3

D(3) = −4

 

 8

6
∞ ∞              ∞ −1

0 ∞ 2 0 2 0 4 2

∞ ∞        0        −5

7     ∞     9      0

5     10    7      5
∞

∞

−8

∞

∞

0
 

 0

−

 2  0

D(4) = −4

 

 5

3
∞ ∞ 0 ∞

2         0

∞ ∞ 7 ∞

5       10
∞ −1
∞

∞

−8

∞

∞

0
2

4

0

9

7
−3

−1

−5

0

2
 
6        ∞

0        ∞

−3       0

2           ∞ 7           ∞

5       10
8

2

−1

0

9

7
−1

−3

−6

−5

0

2
∞

∞

−8

∞

∞

0
 
 

 0

−

 2  0

D(5) = −4

 

 5

3
6

0

2

2

7

5
∞

∞

0

∞

∞

10
8

2

4

0 9

7
−1

−3

−1

−5

0

2
∞

∞

−8

∞

∞

0
 
 

8             Exercise 25.2-4

The old version for computing the values  is:  .

If we use  rather than   in the computation, then we are using subpath from i to k with all intermediate vertices in {1,2,...,k}. However k cannot be an intermediate vertex on a shortest path from i to k since there are no negativeweight cycles on this shortest path. Thus,  and also applies to   . Therefore, we could simply drops all the superscripts.


 
[1] : function Extend-SP(L,w)
[2] :              n = L.rows