Exercises 24.3-8

The reason why the Dijkstra’s algorithm can’t handle negative weight edge is that the path to previous selected vertex may be longer than to the vertex which is selected in the future. However, if all negative weight edge is adjacent to s, this situation will not occur. Because after the first iteration, we will not find any negative weight edge.

Exercises 24.3-7

We know that there is at most W+2 key value in the priority queue. Hence we can use the RB-tree to maintain the priority queue, which all operations need time O(lg W).

Exercises 24.3-5

We know the maximum distance is WV. Hence we can use array to implement the priority queue, and the time complexity of EXTRACT-MIN and DECREASE-Key are O(1).

Exercises 24.3-5

There are at most WV vertices in graph G’.

Exercises 24.3-4

Set the weight of (u,v) to lg(r(u,v)), and we define lg 0 = -∞.

Exercises 24.3-3

Correct, because after |V|-1 iteration the shortest paths are fixed.

Exercises 24.3-2

Exercises 24.3-1