0:01

And let's begin with the idea of shortest paths. So, again I'll give you

the movie graph. I'll give you Kevin Bacon as a starting point. What's the fewest

number of hops, the fewest number of edges on a path that leads to, say, Jon Hamm? So

some notation, I'm going to use DIST of V, to denote this shortest path distance. So

with respect to a starting node S, the fewest number of hops or the fewest number

of edges on a path that starts at S, and goes to V. And again you can define this

in the same way for undirected graphs or directed graphs. In a directed graph, you

always want to traverse arcs in the forward direction, in the correct

direction. And to do this we just have to add a very small amount of extra code to

the BFS code that I showed you earlier. It's just gonna be a very small constant

overhead, and basically it just keeps track of what layer each node belongs to,

and the layers are exactly tracking shortest path distances away from the

starting point S. So what's the extra code. Well first in the initialization

step, you set your preliminary estimate of the distance, the number of the shortest

path distance from S to vertex V as well if V equals S, you know you can get from S

to S on a path of length zero, the empty path. And if it's any other vertex all

bets are off, you have no idea if there's a path to V at all. So let's just initially

put plus infinity for all vertices other than the starting point. This is something

we will of course revise once we actually discover a path to vertex V. And the only

other extra code you have to add is, when you're considering, so when you

take a vertex off of the front of the queue and then you iterate through its

edges and you're considering one of those edges V, W, so your V would be the vertex

that you just removed from the front of the queue. And as usual if the other end

of the edge W has already been dealt with then, you know, you just throw it out.

That would be redundant work to look at it again. But if this is the first time

you've seen the vertex W. Then, in addition to what we did previously, in

addition to marking it as explored and putting it in the queue at the back, we

also compute its distance, and its distance is just going to be one more than

the distance of the vertex V, responsible for W's addition to the queue, responsible

for first discovering this vertex W. So, returning to our running example of

breadth first search, let's see what happens. So, again, remember the way this

worked is we start out with from the vertex S, and we set the distance, you

know in our initialization equal to zero. We don't know what the distance is of

anything else. So, then how did breadth first search work? So, we, in the initial

step we put S in the queue. We go to the main while loop, and then the queue's not

empty. We extract S from the queue. We look at its neighbors. Those neighbors are

A and B. We handle them in some order. Let's again think of that we first handle

the edge between S and A. So, then what do we do? We say we haven't seen A yet. So we

mark A as explored. We put A in the queue at the front, and now we have this extra

step. It's the first time we're seeing A, so we wanna compute its distance. And we

compute its distance as one more than the vertex responsible for discovering A. And

so in this case S was the vertex whose exploration unveiled the existence of the

vertex A to us. S's distance is zero so we set A's distance to one. And that's tantamount

to being a member of the ith layer. So what happens in the next iteration of the

while loop. So now the queue contains Sorry, the next iteration of the for

loop, excuse me. So after we've handled the edge S comma A, we're still dealing

with S's edges, now we handle the edge S comma B. We put, it is the first time

we've seen B. We put B at the end of the queue, we mark it as explored, and then we

also execute this new step. We set B's distance to one more than the vertex

responsible for discovering it. That would again be the vertex S. S led to B's

discovery. And so we set B's distance to be one more than S's distance, also known

as one. And that corresponds to being the other node in layer one. Now having

handled all of S's adjacent arcs we go back to the while loop. We ask if the queue is

empty. Certainly not. It takes two vertices, first A then B. We extract the

first vertex cuz it's FIFO, that would be the vertex A. Now we look at A's incident

edges. There's S comma A, which we ignore. There's A comma C. This is the first time

we've seen C. So as before we mark C as explored. We add C to the end of the queue

and now again we have this additional line. We set C's distance to be one more

than the vertex responsible for its discovery. In this case it's A. That first

discovered C. So we're gonna set C's distance to be one more than A's distance also known

as two. So then having handled A we move on to the next vertex in the

queue, which in this case is B. Again we can forget about the edge between S and V.

We've already seen S, we can forget about the edge between B and C. We've already

seen C but D is now discovered for the first time via B. It gets more as explored,

it goes to the end of the queue and its distance is set equal to one more than B's

distances which is two. So, then we deal with C. Again it has four arcs, four

edges, three of them are irrelevant. The one to E is not irrelevant, cause this is

the first time we've seen E. So, E's distance is computed as one more than C,

cause C was the one who first found E, and so E gets a distance of three, and then

the rest of the algorithm proceeds as before. And you will notice that the

labelings, the shortest path labels, are exactly the layers as promised. I hope you

find it very easy to believe at this point that, that claim is true in general. That

the distance computed by breadth-first search for an arbitrary vertex V, that's

reachable from S is, that's gonna be equal to i if and only if V is in the ith

layer as we've been defining it previously. And what does it really mean

to be in the ith layer? It means that the shortest path distance between V

and S has i hops, i edges. So I don't wanna spend time giving a super rigorous

proof of this claim but let me just give you the gist, the basic idea,

and I encourage you to produce some formal proof at home if that is something that

interests you. So one way to do it is you can do it by induction on the layer i. And so what you

want to prove is that all of the nodes that belong to a given layer i do Indeed, breadth

first search does indeed compute the distance of i for them. So what does it

mean to be a node in layer i? Well, first of all, you can't have been seen in either

of the, any of the previous layers; you weren't a member of layer zero through i

minus one. And furthermore, you're a, a neighbor of somebody who's in layer i

minus one. Right? You're seen for the first time once all of the layer i minus

one nodes are processed. So the inductive hypothesis tells you that distances were

correctly computed for everybody from the lower l, from the lower layers. So in

particular, whoever this node V was from layer i minus one was responsible for

discovering u, in layer i. It has a distance computed as i minus one. Yours is assigned

to be one more than its, namely i. So that pushes through the inductive step

everything in layer i indeed gets the correct label of a shortest path

distance i away from S. So before we wrap up with this application, I do wanna

emphasize, it is only breadth first search that gives us this guarantee of shortest

paths. So, we have a wide family of graph search strategies, all of which find

everything findable. Breadth-first search is one of those, but this is a special

additional property that breadth-first search has: you get shortest path distances from

it. So in particular depth-first search does not in general compute shortest path distances.

This is really a special property of breadth-first search. By contrast in this next

application, which is going to be computing the connected components of

an undirected graph, this is not really fundamental to breadth first search. For example,

you could use depth first search instead and that would work just as well.