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.

Exercises 25.2-7

If , then we print the path i to m and m to j recursively. In this way, the algorithm is difficult slightly.

Exercises 25.2-6

Check the diagonal. Otherwise we can run more one iteration, if ≠, then there is negative cycle.

Exercises 25.2-5

Yes.

Exercises 25.2-4

We know that , since node k can not be intermediate node on the path from i to k. Similarly, .

Exercises 25.2-3

When updating the value, we also update the π value.

Exercises 25.2-2

We can use the OR and AND operation to replace the multiply operation in the algorithm.

Exercises 25.2-1