0:00

What is the shortest path problem? So we're given a graph, G that is we're

given. A vertex and an edge set.

A set of nodes and a set of links. And it is a weighted graph so each link

has a certain number a weight associated with it, interpretable as the cost of

using that link. And it is a directed graph so node I goes

to node j doesn't mean that node j also goes to node i.

And our job is actually very simple. We just want to find a minimum cost path,

so there might be multiple. We just need to find one, between each

pair of source and destination. Okay?

So that's a very simple statement and it turns out this is one of the most

extensively studied graph theoretic optimization problems.

It's got the name, the shortest path, which is a little misnomer, because the

best name really should be minimum. Cross path problem.

1:32

So how can we solve this problem? There's so many different nice ways.

We will look at a specific one based on the dynamic programing principle.

Or the so called Bellman Equation. And if you are taking an optimization

course you probably will spend quite a few lectures on dynamic programing.

Okay? But here we just illustrate it in one

specific algorithm. Again, notice that we're given the graph

G. And for each link there is a cost, the CIJ

for link I to J. And the main idea behind this Bowman's

equation and the resulting Bowman-Ford's algorithm was the following: if you are

node i. And you have a destination n.

You want to figure out the best way to get there, the shortest path or main course

path. Well, you have to get there from one of

your outgoing neighbors. There should be an arrow here.

Say you got three neighbors, so whatever path you take, you have to first start

with one of the three neighbors. Okay, and there's a cause of going to the

neighbors, CIK here. Then, let's denote by p sub it.

2:51

As the minimum cost it takes for node I, to go to destination N, from I to N.

Let's assume this N is a common fixed N for everyone.

Okay. So we just suppress the N notation here,

with implicit understanding that we talk about this nation being node N.

So this is the minimum cost for source I that goes to source N, using T or less

halves. You think but here we usually reserve that

index for time and indeed we can view this as the iteration index over discreet times

loss as well. Both have a temporal meaning over a

duration as well as a spatial physical meaning here.

So we're using that notation, we can write down the following obvious statement.

For example, at time zero, every nose takes infinite cause cuz you cannot get to

the destination using zero or less hops, okay.

Unless node I is node n itself, you are the destination yourself, then in that

trivial case, yeah you are, already there. And we can also write down, therefore at

whatever time or whatever number of halves you may need, you can always get to

yourself, with a zero cost. Okay.

So these are just obvious statements using this definition of the notation PIT.

Now here comes the somewhat magical part. We want to find out PI, let's say using T

plus one or fewer halves. That means we have to go through, well,

4:42

one of the outgoing neighbors indexed by k, okay, with the cost CIK.

Once you get to that neighbor, one of these neighbors, you've already used up

one hop. So you need to get to that destination

with T hops or fewer. And if you could know, still if at this

point, the minimum cost it takes for node K, that's the neighbor you just picked to

go to, to get to destination N using T or fewer hops, then that's great'cause you

can then add these two up. Now, the question is, which outgoing

neighbor K to pick? Well, I'm going to pick whichever one can

give me the smallest sum . So, pick the min of the sum over all the

nodes indexed by k, that's your outgoing neighbors This is the famous Bellman's

equation. And we can, indeed, rigorously prove that

if this equality holds. Now, this boundless equation is useful for

an algorithm only if you can actually efficiently compute a pkt.

Then you can compute PIT plus one. But can you compute PKT efficiently? Well,

Let's use the idea of recursion. So using recursively this Bellman's

equation you can like keep riding this from T plus one to T, to T minus one, T

minus two, all the way down to zero. Then you see that no nodes can get to

destination in zero of fewer hops except that destination is cell.

And then you can recursively work your way back up, back to T plus one.

6:38

Bellman-ford algorithm. Okay.

Essentially, it is an algorithm for efficient computation following this

Bellman's equation. Notice the min is taking over only those

nodes K that are your outgoing neighbors. So, this is one of those beautiful,

elegant and yet extremely useful and so often used equations, like those we

encountered in lectures one, two, and three, back there.

So, without going into the underlying dynamic programming principles, because

then we'll be dragging sort of off the track a little bit.

Let's take a look at an example to illustrate how this can be computed, at

least centrally. Okay, suppose you actually know the whole

graph. How can you compute this essentially?

Then we'll look at, in the next module of the video, the distributed version where

no one has a global bird's eye view of the whole graph.

Then how can you implement this computation?

7:52

But. So here is the centralized example.

This is an extremely small graph. For such a small graph, you can probably

just eyeball the answers. Please don't eyeball the answer.

Let's follow the Bellman's equation cuz the purpose is not to redefine the

shortest path in this graph. Who cares is to illustrate the

Bellman-Ford algorithm. Okay?

So, notice in this graph, we got A, B, C, D, four nodes, five nodes.

There is also a common destination node N. We can do All to one routing basically,

Okay? Find out all the shortest path for these four nodes to a common destination

N. We could also do one to all following a

similar procedure, Okay? So,

You look at these link ways which are numbers written next to the directed

weight links in the graph. You see hey, they are some negative

numbers. What do you mean by negative weights?

The three negative numbers, was really for generality sake.

It may have some physical meaning in some context but for this purpose we just want

to show that is okay to have negative weights on a link for Bellman-Frod to

still work out. As long as you don't have,

No negatively weighted cycles. Cycle is a path connect concatenation of

links that ends up where it started. Okay?

So for example, C to A to B to C, that's a cycle, right?

Is a concatenation of links, of three links, and then you end up where you

started with. And the total cycle path is minus two plus

eight plus four which gives you ten as the cycle went, which is positive number so as

long as we don't have a cycle with total negative wave and s'okay, what's wrong

with a negative weighted cycle? Well because if this whole cycle is

negative weighted then, you can just keep going looping this infinite number of

times and it will push your total cost down to infinite.

Before you take, you know, one more hop to get to the destination, or two more hops.

So, no negative cycles, otherwise the problem is ill-defined.

Negative weighted links, that is okay. Alright.

So, let's run the Bellman's equation now. At time T for this graph, just remember

the graph now, okay. We have the following.

11:05

What are these three numbers? Well it's eight plus infinity, six plus

infinity and four plus infinity because the previous iteration they're all

infinity and this is infinity which means you have no way to get from node A to the

destination in the first iteration i.e. Using one or fewer hops.

Which is obviously true, it's trivial. Of course A is separated from N by two

nodes by one nodes so you at least need two hops to get to N.

But again, don't eyeball solution. We just want to illustrate a Bellman

equation using a simple a numeric example as possible.

Similarly, you can write down PB. At this time iteration is also

implemented. What about PC?

Actually PC is not infinity any more cuz is the mean of three numbers, six plus

zero if you go through node N directly. Minus five plus infinity if you goes to

its outgoing neighbor B. And minus two plus infinity if you go

through its outgoing neighbor A. But clearly you want to pick the first one

that's six. And PD, similarly can find to be seven.

So it's infinity , infinity six and seven and iteration one, okay?

Using one or fewer hops. Now, let, iteration two starts.

You can now see suddenly, that PA at two is not infinity anymore.

It is the mean out of three choices of its outgoing neighbor.

Through B, you get A+ infinity, because it's still infinity in the last iteration.

Pb at iteration one is to infinity, so it's ainfinity.

Plus infinity. That's no good but then you've got sixCs.

Plus Cs. No Cs minimum cost last iteration, using

one of your halves. That is six,

Very good. Now you've got four plus seven if you go

through D. Now clearly the mean of that is eleven,

four plus seven go through neighbor D. You should write on a separate sheet of

paper what exactly node are you using? Okay this is purely computing the shortest

path. But obviously you can also trace back the

actual path itself. In addition to the cost of the shortest

path. Good so PA is now eleven.

Following similar calculation PB now is three and PC now is two.

You can easy derive this yourself or see it in the textbook.

What about PD? We're going to start writing PD cuz PD is

boring. D had only one outgoing neighbor which

turns out to be the destination itself. So it will always stay the same number

which is seven, okay. So now it becomes eleven, three, two,

seven. Keep going.

Iteration three, you see that PB, Iteration three is now the min of what?

Eight plus what? What does it take to node B to get to the

destination three? Okay, very good.

A plus three, Okay? Six2, plus two.

Four7. Plus seven.

14:37

Notice the last iterations updates into eleven, three, two are reflected here.

Now, you've got three and two, okay? So now, this is seven and similarly PB

iteration is -one. Oh, I'm sorry, not seven this is eight.

-One MPC is two . Okay.

Pd again, remains the same. Keep going, t equals four.

Okay? Pa now is , you can compute, 7pb is minus

one pc is two, pd is still the same. And how about we keep going, t equals

five, equals six and so on. Turns out we don't need to do that.

There are two ways to look at it. One is it no longer changes.

Okay? You can try it but you will see that it no

longer changes It converged the Bellman-Ford algorithm at the right

answer. And second You, if you actually had a

bird's eye view and know how many nodes there are, you know there are four nodes.

Okay. Other than yourself out there.

So, you got to be able to stop at iteration four.

You know this APRE, because if you keep on going any further.

I say, well I give you one more half, you can go up to five halves or more or, or,

or fewer. You can go up to a 100 halves of your, not

just four halves of your. Say I don't care, it doesn't help me any

more. Why?

Because the only way for me to leverage beyond four halves.

Is to actually go through the same node twice.'Cause there are only four other

nodes out there. And therefore, I will have to go through a

cycle. But I know cycles are not negatively

weighted, so it will add to my cost. No cycles needed, so I don't need to go

beyond, four hops or more. Either way, you know, you can stop.

And this illustrates the Bellman-Ford algorithm.

But it does not show you how to do it distributively.