0:03

Now we're going to look at shortest paths and edge weighted dags.

Â This is a very common situation and we'll see a couple of important applications.

Â Suppose that you've got an edge weighted digraph.

Â That's our input to shortest paths. But you konw there's no directed cycles.

Â And actually that's true and in many applications we see some.

Â The question is this fact that it has no directed cycles make it easier to find the

Â surest path than in a general digraph, And the answer is yes, it certainly does.

Â So lets take a look at what happens. And the algorithm is very simple.

Â What we're going to do is, just consider the vertices in topological order.

Â Since there's no cycles, we know there's a topological ordering where we can lay out

Â the graph and all the edges point to vertices that we haven't seen yet.

Â And so we're just relaxed all edges, pointing from each vertex, taking them in

Â topological order. Again, this'll be easy to see in an

Â example. Alright, so here's a edge-weighted

Â directed acyclic graph. And the first thing that we do is sort it

Â in topological, Sort the vertices in topological order.

Â And we talked about an algorithm for doing that a couple of lectures ago.

Â So just using that first search. So we consider vertex zero, and relax all

Â the edges coming from vertex zero. And that gives us shortest paths to one

Â four and seven. So next we consider vertex one.

Â We don't do anything except take the next vertex in topological order.

Â We could of also taken four in this case. And so we're going to add that.

Â And then just relax along all the edges coming from that vertex.

Â In this case that gives us new shortest paths to two and to three.

Â Next is four relax and that gives us new shortest paths to five and six.

Â Next in topological left quarter is seven. Relax and that gives us a new shortest

Â path to two, but not to five. The path that we had to five was better.

Â So next in the order is five. Relax along its edges.

Â And it gives us better ways to get to both two and to six.

Â Then 2's next. Relax along its edges.

Â And it gives us, new better ways to get both three and six.

Â Then we do three, and relax. And that doesn't help.

Â And then we do six. And, when we're done all we did was

Â consider the edges in topological order and relax.

Â Then we have a shortest path tree. From the source to every vertex in the

Â directed acyclic weighed digraph. So that's a demo of a simple algorithm for

Â that case. Alright, why does that algorithm

Â considering the vertices and topological work for edge-weighted dags.

Â Now, one thing that's pretty important about this is that the edge weights could

Â even be negative doesn't matter to this algorithm.

Â So let's look again. Every edge is relaxed exactly once.

Â When, we add a vertex to the tree we, relax each of the edges that go from that

Â vertex. And, again, just as, with Dykestra, after

Â we're done with the relaxation, we have this condition holds that, distance to w

Â is less than or equal to the distance to v plus the edge weight.

Â Either it was before-hand and we ignored the weight, or we made it equal.

Â And so. when we relax an edge we have that condition.

Â And again, inequality holds until the algorithm terminates.

Â Well, first, again, we only. Decrease values in the distribute array.

Â We don't change it to increase. So the only thing that can happen to this

Â 2W is that it gets smaller. And that's not going to violate the

Â inequality. And then the other thing is, this 2V's not

Â going to change because of the topological order.

Â When we process v, it's in topological order.

Â That means we're not going to find an edge that points 2V.

Â So this two v's not going to change. And edge weight doesn't change, so the

Â inequality holds. And this is true even if the edge weights

Â are negative. So shortest path optimality conditions

Â hold. And so this simple algorithm finds

Â shortest paths in edge-weighted directed acyclic graphs.

Â Whether or not the edge weights are positive or negative.

Â Pretty easy algorithm to implement. So this, acyclic, shortest path.

Â So, the goal is to compute edge two and disc two.

Â And then we use those to respond to client queries of the length of the shortest path

Â and the path itself. This is the constructor.

Â We build the arrays. We initialize this distances to infinity.

Â Distance the source to zero. Then we use our topological sort algorithm

Â on di-graphs to compute an iterable that gives us the vertices in topological

Â order. And that's the order method in this

Â topological class. So that's using the API that we set up for

Â topological sorting, Which has to be adapted to weighted

Â di-graphs. But that's just adding some nomenclature.

Â So we take the vertices in topological order.

Â We take for every vertex in topological order, taken in topological order.

Â We take every edge that emanates from that vertex and relax it.

Â It couldn't be simpler. And then we're done we have the other

Â shortest pass. And that works even for negative edge

Â weights. Pretty simple.

Â Now, as an example of a, familiar application of, shortest paths in dags and

Â weighted dags we'll look at, the idea of scene carving.

Â And this is a relatively recent algorithm that, was developed that has, important

Â application that you'll see, in this, YouTube film clip.

Â Scene carving for content-aware image resizing.

Â 9:44

So that's a amazingly powerful image processing process.

Â And you'll find it all over image processing applications, from Photoshop to

Â GIMP to Image Magic. And actually nowadays almost any image

Â that you see on your cell phone or your Tablet.

Â And what really, does that have to do with shortest paths?

Â Well, it's actually a direct application of shortest paths on a directed acyclic

Â graph. So what we do is, build a huge directed

Â acyclic graph. And this is a really huge graph.

Â Because images now, at high resolution, can have millions or billions of pixels.

Â And so. Every pixel corresponds to a vertex in

Â this graph. And the edges are gonna be just directed

Â edges from every pixel to its three downward neighbors.

Â And then there's, what weight do we assign to the pixels?

Â Well, there's an energy function that has to do with the image processing, that is,

Â a function of the eight neighboring pixels.

Â Every, every pixel, has a relationship with all its neighboring pixels.

Â And, the energy function, has it, is, is a image processing, concept that, is.

Â Perfect for, assigning weights, in, in this instance.

Â And so, that gives, the weights. And then, a seam is just the shortest

Â path, that goes from the top to the bottom.

Â So you can, imagine an imaginary source that goes all to the top ones, and, just,

Â run the shortest pass algorithm that we just gave, and, it'll find a seam.

Â So that's the lowest energy, one pixel cut, through the image, and then, the

Â resizing algorithm, just deletes, one, one pixel on each row, along that seam, and

Â that's the algorithm. Which.

Â The shortest pass algorithm, I'im I'm sorry, allows and enables the

Â re-sizing for a really huge graph. And, and it's really important to realize

Â that you have to have an efficient implementation of the shortest pass

Â algorithm. Because there's so many pixels.

Â And certainly the topological sort algorithm that we gave is extremely

Â efficient linear time algorithm. And you can see the effects of that

Â efficient algorithm all around you. Here's another completely different

Â application of shortest paths in directed acyclic graphs.

Â And the idea is that actually since negative weights are allowed, we can find

Â longest paths in edge-weighted DAGs, just by negating all the weights.

Â So what I want is I have edge. Again I have an edge weighted dag.

Â And what I want is, this is with, I guess five as the source.

Â I, I don't want the shortest path from five to two.

Â I want the longest path from five to two. We'll see an application why that's

Â important in a minute. And in order to get that, all I do is just

Â negate all the weights, and the run shortest paths.

Â And if you add up negative weights to get the smallest negative number, then to

Â negate the answer that's the longest path, and it works because the algorithm, top

Â logical sort algorithm, doesn't care whether the weights are positive or

Â negative. In general graphs it does matter as we'll

Â see in a minute, but for a cyclic graph it doesn't matter, we can find longest path

Â in a cyclic graph just by negating all the weights, therefore we can solve the

Â longest paths problem. So that's a key point.

Â And now, now you can look at applications that had problems.

Â And there's a really important application for longest paths in edge weighted

Â directed A-cyclic graphs. And that's called the Job Scheduling

Â Problem. And this is just another example to show

Â the importance of the shortest paths problem as a problem solving model.

Â This particular problem doesn't seem related to shortest paths at all.

Â But we'll show how to formulate it as a shortest paths problem.

Â And that's great, because we have an efficient solution to the shortest paths

Â problems. Or actually, it's a longest paths problem

Â in this case. So this is just an example that arises

Â say, in man, in manufacturing. Or other applica, applications we have a

Â complex set of interacting processes. So this we call, job scheduling.

Â Parallel job scheduling. So we've got a bunch of let's say a

Â factory manager has a bunch of jobs to manage, And they have.

Â Durations and precedents constraints. So durations just means the job takes a

Â certain amount of time. And precedents constraints means that you

Â can't start job one until after job zero is done, or seven, or nine.

Â One, seven and nine have to start sometime after jo-, job zero.

Â And similarly three and eight have to start after six, and so forth.

Â So maybe this is manufacturing a car. And, you know you can't, paint the car

Â until after you put the doors on. Or whatever else you can imagine.

Â Easily, setting up, precedence constraints, that are natural, for trying

Â to complete this whole, set of jobs. And so what we want to do is, find a start

Â time for each job. That minimizes the completion time.

Â While still respecting all the precedence constraints.

Â So when do we start each job? That's the parallel job scheduling

Â problem. We, we assume that we got enough workers

Â that we can have a bunch of jobs going on at the same time, same time.

Â So, This graph model shows that we can change the job scheduling problem into a

Â graph processing problem. So, what we're going to do is, create an

Â edge weighted directed acyclic graph the following way.

Â We're going to have a source and sync vortex that the source is, begin

Â everything and the sync is, end everything.

Â And then, well at the zero weightage from the.

Â For every job will have a start and a finish vertex for that job, and then we'll

Â have an edge, whose weight is the duration.

Â And from the finished vertex of every job, we'll have edges to the start vertex of

Â the jobs that it has to complete before. That's, those are the precedence

Â constraints. We have a zero weight edge from, the,

Â overall source to every job start, and a zero weight edge from the overall, from

Â every job finish to, the, sink vertex. And so, in summary, there's three edges

Â for every job. There's from the begin to the end, the

Â start to the finish, weighted by the duration.

Â From the source to the beginning, zero weight, and from the end to the sync, zero

Â weight, in the edges for the precedence constraints, also have zero weight.

Â So that's a graph model, we took our scheduling problem and now we have a

Â graph. And what relates this to what we've been

Â talking about is the longest path from the source to each job.

Â It turns out to give a schedule. So the job scheduling problem corresponds

Â to a solution to the longest path problem in directed acyclic graph by the way this

Â graph doesn't have any cycles because that would mean we have to do a job before

Â another job insist that one be done after zero and that two be done after one.

Â We can't also insist that zero be done after two because that would be a present

Â cycle that couldn't be satisfied at all. And so the, the n-, now you have to think

Â of this quite a while to understand why the longest path from the source.

Â We'll schedule each job, but, that's a fact in that it means, then, we have, a

Â fast, linear time algorithm for solving this problem.

Â Negate all the weights, run shortest paths with topological sort, and negate the

Â answer, and you have the start times for every job.

Â In fact, in the book and the book site, you'll find code that not solves, this,

Â schedule, parallel job scheduling problem using the critical path method, Again,

Â showing how important it is to have, a fast and efficient solution to the

Â shortest paths problem.

Â