Consider the following digraph G = (V, E) with a weight function w : E R on the edges:

the nodes are V = {1,2,3,4}, the edges are E = {(1, 2), (2, 3), (3, 4), (4, 1), (4, 2)}, and the weights of the edges are:

w(1, 2) = 3 w(2, 3) = 8 w(3, 4) = 4 w(4, 1) = 2 w(4, 2) = 5

For all pairs shortest path problem, if we would like to apply Dijkstras algorithm, we have to reweight the edges, as suggested by Johnsons algorithm. As you know, Johnsons algorithm is based on first finding some suitable weights for the vertices of the graph. Let us use x1, x2, x3, x4 as the weight of the nodes 1, 2, 3, 4 respectively. After we find a suitable weight for each node, we will define a new weight function for the edges, such that all edges will have nonnegative weights.

There are two possible ways to define this new weight function: w1(i,j)=w(i,j)xi +xj (i,j)E,or

w2(i,j)=w(i,j)+xi xj (i,j)E. Fill in the blanks (. . .) below, to give the constraints on the differences on the vertex weights for both

of these cases:

edges when w1 is used when w2 is used

for(1,2)E x... x... ... x... x... ...

for(2,3)E x... x... ... x... x... ...

for(3,4)E x... x... ... x... x... ...

for(4,1)E x... x... ... x... x... ...

for(4,2)E x... x... ... x... x... ...