Exercises 25.1-10

Find .

Exercises 25.1-9

Check the diagonal entries. If there is one entries with negative value, then there exists negative cycle.

Exercises 25.1-8

One matrix L stores the partial result, the other matrix W stores the repeatedly square matrix. We can use the bit-pattern of n to decide whether L multiplies W or not.

Exercises 25.1-7

The same as 25.1-6.

Exercises 25.1-6

If L[i,j] = L[i,k] + w[k,j], then π[i,j] = k.

Exercises 25.1-5

The vector v is initialized with all ∞ except the source is 0. Then multiply v by matrix W n-1 times.

Exercises 25.1-4

Exercises 25.1-3

The matrix corresponds to the identity matrix.

Exercises 25.1-2

It is by definition. If after the algorithm termination the value is not zero, then there exists a negative cycle.

Exercises 25.1-1