Problems 25-2

(a) Insert =, Extract-Min = , Decrease-Key = . If d = , the Insert and Decrease -Key will become and Extract-Min will become .

(b) Let d = , the complexity will become O(|E|).

(c) Run (b) for |V| times.

Problems 25-1

a. Let the new added edge be (u,v). If there are nodes u,v such that i is transitive to u, v is transitive to j. Then i is transitive to j in the G*.

b. Let G be one directed path start from u and stops in v. If we add edge (v,u), then all nodes in the graph are transitive to each other.

c. If i is transitive to v, then add edge (u,v) is no help to i and j. We can check this condition explicitly. Although there are possible insert edges, but the situations which meet i is transitive to u and i is not transitive to v are only possibilities. Hence, we can insert edges in time.

Exercises 25.3-6

If the graph is not strongly connected, the modification will not work.

If the graph is strongly connected, then for every vertex v, h(v) is well-defined and the nonnegative property is preserved.

Exercises 25.3-5

According to (25.9), we know w’(u,v) = w(u, v) + h(u) – h(v), h(u) is the shortest path from s to u. If (u,v) is a edge in the cycle, then the shortest path from v to u is -w(u,v). Suppose that w(u,v) is positive, h(v) will be 0 and h(u) will be -w(u,v), so w(u,v) + h(u) – h(v) = 0. The case of w(u,v) is negative is symmertic.

Exercises 25.3-4

It will change the shortest path. The path with more edges will be added more weight.

Exercises 25.3-3

Because w(u,v) ≥ 0 for all edges, the shortest from s to every vertex v must be edge (s,v)  which weight is 0. Hence the codomain of function h has only one element — 0 and w and w’ must be identical.

Exercises 25.3-2

Because we want to find a suitable function h.

Exercises 25.3-1

Exercises 25.2-9

First, we should compute the strongly connected component graph. Then we use the component graph to run the transitive closure algorithm.

Exercises 25.2-8

We can run DFS at most |V| times to get the transitive closure.