And so to illustrate the Bellman-Ford algorithm let's walk

through an example and see some of the steps.

The example we're going to be considering is a graph of six routers and

we have one common destination, F, which is where we want to get to.

We want to try and find the minimum cost from each of the other routers to F.

And, so, the routers, again, we're going to

notate A through F, and, we want to

figure out the minimum cost path ,um, to F from each of A through E.

And,

so, we want to choose the shortest path at each iteration, right?

So, an iteration is really the number of hops, right?

So, we start with zero hops.

We say, what's the shortest path?

Then we move onto one hop, and we say, what's the shortest path?

Then we move up to two hops. We say, what's the shortest path?

And it may not sound, intuitive to you, but

it will be come obvious how it can build

upon itself in a minute, when we get to after we do zero on one hop, we'll see.

So let's start with zero hops, it's really a trivial case.

A through E cannot get to F, right so,

in zero hops you can't because, they're not F itself

and the only way you can get to a node in zero hops is if you are that node.

Right, so A, B, C, D and E can't get to F in zero hops, so we, we

denote that cost as infinity, so there's an infinite

cost really, which means that you just can't get there.

F can get to F though, obviously, and the cost from F to get to F is zero.

So, the path costs right now, are infinity,

from A through E and zero for F, right?

And again, we're finding a path cost to get to F.

We could choose another router as the destination.

We could choose E, D, C, whatever which one we want and typically we

would do all of them at the same time and build a routing table.

But really we're just focusing on one element of the routing table,

here, so we're trying to build a routing table, for entry F.

Like how do we get to F, from each of the other guys.

So, now, let's move onto one hop.

again, by inspection, we see A through C still can't get to

F in one hop, right, because they're more than one hop away.

any one of them would have to either go through D or E to get to F, right.

But, so, we, those costs are still infinity, but now let's look at D and E.

OK, D and E can get to F in one hop because it's

just, one step away, and, so the path here would be, link DF.

For D to get to F and

the path here would be E F, for E to get to F.

And the costs accordingly.

for D the cost is going to be eight, and we'll just say cost

D to be rid of the cost to get from D to F.

We're not going to input F in there

because everything's assumed to be going to F.

so that cost is eight, and it's just from D to F, and the cost

to get from E to F is 10 and the link the path is EF.

Just just one link here.