So I'm going to call this additional information a two-dimensional array B,

this is indexed just by the choice of the origin, by the choice of the destination.

And again, the semantics is we want the i, j entry of this array to be the max

label of any internal node on the shortest i, j path.

So two things we have to understand are, first of all, how do we compute all these

B(i,j) values on the forward-pass of the Floyed-Warshall algorithm without

affecting its running time? Secondly, if we successfully compute all

of these B(i,j) on the forward pass, how do we reconstruct shortest paths by going

backward through the filled in table? So this is all analogous to Bellman-Ford

and Bellman-Ford. We two that on the forward pass, you could maintain the

predecessor point it wasn't a big deal, just when you fill in, when you recompute

shortest pass in a given round of subproblems. If you compute some new

shortest path value, i.e. you don't just inherit that solution from

the previous round, you just figure out which vertex was responsible for it and

you remember that as your predecessor. And then given the predecessor pointers

are correctly computed, you just trace back pointers to reconstruct shortest

paths. So here, how do you compute them on the

forward direction? Well, remember in the, in the recurrence

that we used to fill in the three-dimensional array, A,

there's two possibilities, either you just inherit the solution from

the previous iteration, that's kind of the boring case.

And the interesting case is when you actually use the newly available vertex k

in the shortest path from i to j. So whenever you use that second case of

the recurrence to reset the value in the three dimensional array A.

At that point, you reset the corresponding B(i,j) value to the current

value of k. So that is, just add the forward pass of

Floyd-Warshall. You always remember the last vertex

responsible for changing your shortest path distance between i and j.

So now, let's suppose you've coded up this extension of the forward pass of

Floyed-Warshall correctly, so that at the end of your triple for

loop, you have accurate computations of all of these B(i,j) values.

That is, for any origin and desination, you have a little birdy,

the two-dimensional array, B, that will just tell you in constant time what is

the max labeled vertex internal on a shortest i, j path?

Well, maybe you really want to, know your favorite source is 23.

Your favorite destination is 17 and you want to reconstruct a shortest path from

your oracles, your filled in tables. So you look in to the entry 23, 17 into

the B array. You have this little birdy,

this filled in table tells you the max labelled vertex on a shortest path

between 23 and 17. Maybe it tells you it's the vertex 43.

So it promises you that the shortest path comprises 23 on one end, 17 on the other

end, a bunch of stuff in the middle, the largest of which is 43.

Well, you like, okay cool, let me just, now I know where the shortest has to be.

It's the shortest path from 23 to 43 plus a shortest path from 43 to 17, and you

just reconstruct those two shortest paths recursively in exactly the same way.

This has got to terminate because at the end of the day the shortest path is

going to have it most n vertices and you're figuring out one of those vertices

everytime you do a recursive call.