Now, node v is certainly hoping not to have to inherit its
solution of plus infinity from the previous round, when i equals 0.
And indeed when i equals 1, the subproblem solution for
the vertex v is going to be 2.
That's because we can choose the last hop to be the edge s, comma v.
That has length 2, and
S's subproblem value last iteration when i equals 0, is 0.
By the same reasoning x's new subproblem value is going to be four,
because we can chose the last hop to be s, comma x, and add the cost of that
edge four to s's subproblem value, last iteration when i equals 0.
Now, the nodes w and t would love to throw out their plus infinity solutions and
get something finite.
And you might be thinking that because v and x now have finite distances,
those would propagate to the nodes w and t.
That will indeed happen, but we're going to have to wait until the next iteration,
we're going to have to wait until i equals 2.
The reason is if you look at the code, if you look at the recurrence,
when we compute the subproblem value at a given iteration i, we only make use
of the subproblem solutions from the previous iteration, i minus 1.
We do not use any of the updates that have already happened in the current
iteration i.
So because when i equals 0, a of 0 v, and a of 0 x were both plus infinity,
we're going to be stuck with a1w and a1t, both being plus infinity as well.
So, now let's move onto the next generation of the outer 4 loop,
when i equals 2.
The subproblem solution s is not going to change,
you're not going to do better than 0, so it's going to stay that way.
Similarly at the vertex v, you're not going to do better than 2, so
that's going to stay the same at this iteration.
Something interesting happens at the vertex x, however.
Now, in the recurrence you certainly have the option of inheriting
the previous solution.
So one option would be to set a of 2, comma x, to be equal to 4,
but there's actually a better choice.
So the recurrence is going to come out to be even smaller,
specifically if we choose that last hop to be the unit cost arc from vx.
We add that unit cost to v subproblem value, last iteration when i equals 1,
that was 2, 2 plus 1 equals 3.
So that's going to be the new subproblem value at x,
in this iteration where i equals 2.
So as advertised, the updates to the vertices v and
x in the iteration where i equals 1, now that i equals 2,
get propagated onto the vertices WNT.
So, WNT shed their plus infinity values, and
instead they pick up the values 4 and 8 respectively.
