Exercises 24.4-12

Solution wanted!

Exercises 24.4-11

Solution wanted!

Exercises 24.4-10

If the constraint is  ≤ , then add edge (, ) with weight . If the constraint is  ≤ , then add edge (, ) with weight

Exercises 24.4-9

Solution wanted!

Exercises 24.4-8

From exercise 24.4-3, we know all  ≤ 0. (How about the maximize property?)

Exercises 24.4-7

Initial all vertex v with d[v] = 0.

Exercises 24.4-6

Let –  ≤ and  ≤ .

Exercises 24.4-5

The edges from s to every vertex with weight 0 is useless, we can initial all vertex with shortest path weight 0 and ignore these edges in remaining Bellman-Ford algorithm.

Exercises 24.4-4

Let be the shortest path from source to vertex i. We can add the constraint  ≤ 0 and  ≤ 0 to force the to be zero. Then add the constraints –  ≤ w(i,j) for all edges between i, j. Finally, we need to maximize all the x variable.

Exercises 24.4-3

No, because there is one path with weight 0 from to every vertexs.