Generally the shortest path to get to X, the best thing to do is to accumulate of

all of the negative weight at the top of the graph, go via vertex C.

And it's true you have to pay the cost two to get from C to X.

You still wind up with an end length of minus one, which out performs the direct

zero length path from X to S. Now, the brilliant insight in Johnson's

Algorithm is that this shortest path computation is extremely useful.

In fact, these computed shortest path distances are exactly the magical vertex

weight, weights that we're seeking. They're going to transform all of the

edge links from general to non-negative. So let's define the weight P sub V of a

vertex V from the original graph, that is one of the six vertices in this example

that we started with, as the shortest path distance we just computed from the

extra vertex S to that vertex V. What I want to do next is see the effect

of reweighting using these vertex weights.

So to do that, let me redraw the example. So let's recall the formula for the

re-weighting technique given vertex weights like these.

You define the new length C prime E of an edge E say from U to V as its original

length CE plus the length of its tail P sub U minus the weight of it's head, P

sub V. So let's just do this computation for

each of the seven edges. Let's start at the top.

Edge A comma B. So we start with its original length:

minus two. We add the weight of the tail, so we're

adding zero. And then we subtract the weight of the

head, so we're subtracting minus two. That is, we're adding two.

So we get minus two plus two or zero for the new length C prime B for the edge A

comma B. Similarly for the edge B, C, we take the

original length -one, we add to it -two, and then we subtract -three but as we add

three, then again it all cancels out, we get zero for the new cost of arc B, C.

For the arc C comma A we take the original length four, we add minus three,

we subtract zero. So the arc C comma A has a strictly

positive shifted length that's now one. If we look at the arc C, X we take the

original link two. We add -three and we subtract -one.

So that again all cancels out and C, X has a new cost of zero.

Same thing happens with the arc C, Y. We start with minus three, we add another

minus three, we subtract minus six, that gives us zero.

For the arc Z comma Y, we start with one, we add zero, we subtract minus one so we

get a new cost of two on the arc Z comma X.

Finally for the arc Z comma Y, we start with minus four, we add zero, we subtract

minus six, that is, we add six, so that gives us a new length of two.