And it has the cost it takes each of its
neighbors to get to the destination in at most one hop.
So, the question is, can we generalize this and can we use this information
to try to figure out how long it'll this
router to get to the destination in two hops.
'Kay?
because we already computed for one hop and we said okay well some of
the nodes I know that I can get to the destination in one hop.
We said DNE can get there in one hop.
So can we use that information, then, to backtrack and say, okay
for the other nodes can we use the fact that DNE can
get there in one hop and they're cost to be able to
figure out what the cost is going to be for the rest of them?
Rather than have it construct an entire view of
the network for the router which would be basically impossible.
So the real, real key here though is that adding each
of these is going to give the node the two-hop cost right.
So we have the cost that it takes each node to get to its neighbors, and then we
have the cost that it takes each of the neighbors to get to the destination.
Right, like in this example right here. And stored as S right, it takes S cost
of W to get to A, we're going to say in general.
say W is 3 and Y is 5, you don't want to deal with symbols here.
so then we know, S is going to know it's path cost to get to A.
And it's going to, S make that somehow.
It's just knows it's a number. It knows that it's 3.
And S knows how, what the cost is to get to B, it knows that it's 5.
And then, if A has already figured out how,
what the cost is to get to N in, let's say, three hops, just as an example.
So, we're doing the three hop case right here for X or for A to N, and we know that
in three hops the cost to get from A to N is 16, say.
well then, if A can get to N and it costs 16 three hops, then
W should be, or then S should be able to get to N And the cost
of 3 plus 16 in 4 hops.
So really we're just adding this link on
to As path already, because we're going to go
to A and then A already knows how to get to N and his minimum call.
So we'll just use A's minimum cause to get to N in order to go from S and
again we're blurring this here because there could be
so many routers in between, but it wouldn't matter.
That's the whole beauty of this, this is, it doesn't matter what's in between.
S doesn't need to know what's past A.
He just needs to know the cost to get to A,
and he needs to know what A is saying the cost to
get to N is, or what, not, A doesn't have to
be saying it necessarily, just needs to know what the cost is.
So, that's the power of the Bellman-Ford algorithm.
So that we can do this dynamically, it's like a dynamic programming problem.
So, from source F to N, as we said through A it's going to cost
W plus X and through, B it's going to cost then Y plus Z, right?
And this could maybe be,
maybe with the three hop case again, so three hops.
And again, three hops is going to be what we're saying.
It's, it's in at most three hops, so the, the cost could be
lowest for two hops, in which case we're not going to add another hop in.
but it's just giving us more information, so, in three hops B can get to N in
cost Z, so then Y plus Z is going to give this cost, Y plus Z, whatever that is.
And then this is W plus X.