The textbook Bellman-Ford algorithm will indeed minimize the span of the variables: $max_i(x_i) - min_i(x_i)$. It involves adding a supernode and 0-weight edges from the supernode to every other nodes in the graph. This is probably what the op is referring to.
To maximize $x_n - x_1$, as usual, convert the difference constraints to edges. However, we will not add the super node and its 0 weight edges. Instead, just run Bellman-Ford using the node for $x_1$ as source:
- If negative cycle is detected, the constraints can't be satisfied.
- The result distance $x_n$ will maximize $x_n - x_1$. If $x_n$ is infinity, that means $x_1$ and $x_n$ can be arbitrarily far apart.
Now let's see why it works.
Why do the $x$s satisfy the constraints?
Proof: By triangle inequality, same as the textbook Bellman-Ford method. I won't repeat it here.
Why will the result distance $x_n$ maximize $x_n - x_1$?
Proof: Consider the shortest path $p = (v_1, v_2,...,v_n)$ from $v_1$ to $v_n$, the path corresponds to the following set of constraints:
Summing the constraints, we obtain:
That is, in any solution that satisfies the constraints, $x_n - x_1$ cannot be greater than $w(p)$, the weight of the shortest path from $v_1$ to $v_n$. As Bellman-Ford sets $x_n-x_1$ to the shortest path value, this implies $x_n-x_1$ is as large as possible.