Chapter 24 Answers

Question 24.1

• What currency would you expect back as change for $78. 96?  1-$50, 1-$20, 1-$5, 3-$1, 1-50¢, 1-25¢, 2-10¢, 1-5¢, 1-1¢
• Does the usual method of making change, giving out the smallest number of bills or coins by counting out the largest possible currency first possess a greedy-choice property? Yes. Making the local decision to give out the largest denomination leads to a global optimization.

RELAX(u, v, w) 1    if v.d > u.d + w(u, v) 2       then v.d ← u.d + w(u, v) 3                v.π ←u

Question 24.2 - w is the weight of the edge. Give the result of:

• RELAX( t, x, w ) unchanged
• RELAX( t, y, w ) y.d ← t.d +w(t, y)=2+4=6

r s t x y z π NIL NIL s s NIL NIL d ∞ 0 2 6 ∞ ∞

24.2 Single-source shortest paths in directed acyclic graphs

	r	s	t	x	y	z
π	NIL	NIL	NIL	NIL	NIL	NIL
d	∞	0	∞	∞	∞	∞

	RELAX(r, s, w)
1	if s.d > r.d + w(r, s)
2	then s.d ← r.d + w(r, s)
3	s.π  ←r

	RELAX(r, t, w)
1	if t.d > r.d + w(r, t)
2	then t.d ← r.d + w(r, t)
3	t.π ←r

Question 24.3 - No change from r→t or r→s. Why? r is the first vertex in the topological sort. However r is not the source, the RELAX algorithm only is applied to sorted vertices following the source.

 

Analysis

Similar to DFS analysis since DFS part of topological sort.

Time = Θ(V + E).

Question 24.4

Explain the Θ(V + E) cost.

3	for each vertex u taken in topologically sorted order	Θ(V)
4	for each vertex v ∈ Adj[ u ]	Θ(V+E)
5	RELAX( u, v, w )	Θ(V+E)

Must always examine every V vertex and, for every vertex, each E edge. There are a total of V+E vertices and edges.

Critical Path Analysis (PERT)

Longest path in blue.   r s t x y z π NIL NIL s t x x d ∞ 0 -2 -9 -8 -10

Earlier shortest path analysis.     r s t x y z π NIL NIL s s x y d ∞ 0 2 6 5 3

Question 24.5

• Why are both y and z on the longest path? The longest path is computed from all connected vertices to the source.
• What is the longest path to s? s-t-x-z
• What is the purpose of Line 3, taking vertices in topologically sorted order? Guarantees that edges will be relaxed in an order that establishes a path from the source vertex to each vertex that follows.
• How would the longest path analysis be useful in construction project assuming weights are completion times? The topological sort determines the order events must be completed; the longest path (assuming time is the weight) determines the worst-case duration.

Dÿkstra's Algorithm

	Dÿkstra(V, E, w, s)
1	Init-Single-Source(V, s)
2	S ← ∅
3	Q ← V
4	while Q ≠ |
5	u ← Extract-Min( Q )
6	S ← S ∪ { u }
7	for each vertex v ∈ Adj[ u ]
8	Relax(u, v, w)

Question 24.6

• Does the algorithm find the shortest part to a destination or to all reachable destinations? All reachable.
• Where's the greed? Line 8 where the smallest weight is always chosen.
• S is constructed but never used. What is the purpose of S? It contains all the vertices, used by the text for loop-invariant proof.
• From the graph above, give a source vertex for producing an S ≠ V. No source will exclude vertex s from the set S.
• There is a cycle (y,x,y). How is looping on cycles prevented? Line 5 extracts a vertex from Q, that vertex will never again serve as the start of a subpath.
• Why are negative weights excluded? To restrict the algorithm from cases where cycling through a negatively weighted edge would iteratively reduce the path weight to negative. Because the algorithm prevents cycling, it is not applicable to negatively weighted graphs.