Graph and Johnson's Algorithm Problem

Consider the following directed graph $G=(V,E),$ where:

$V=\{1,2,3,4,5\}$

$E=\{(1,2),(2,5),(3,2),(3,4),(4,1),(4,5),(5,1),(5,3)\}$

Suppose that we are given the following weight function $w$:$ER$ for the edges:

$w(1,2)=-5$

$w(2,5)=8$

$w(3,2)=1$

$w(3,4)=-4$

$w(4,1)=7$

$w(4,5)=6$

$w(5,1)=0$

$w(5,3)=2$

For all pairs shortest path problem, if we would like to apply Dijkstra's algorithm, we have

to reweight the edges, as suggested by Johnson's algorithm.

Johnson's algorithm is based on first finding some suitable weights for the vertices of the

graph. Let us use $x_1,x_2,x_3,x_4,x_5$ as the weight of the nodes $1,2,3,4,5$ respectively. After

we find a suitable weight for each node, we will define a new weight function tilde$(w)$:$ER$

for the edges, such that all edges will have non$-$negative weights when we use

tilde$(w)(i,j)=w(i,j)-x_i+x_j,AA(i,j)inE$

For each edge $(i,j)$ in $E,$ write down the constraint on the difference of $x_i$ and $x_j$ based

on the way tilde$(w)$ is defined in Equation $(1)$ above.

$($b$)$ Draw the graph G that would solve this system of difference constraints if applied the Bellman$-$ Ford algorithm.