Today we're going to talk about shortest path algorithm.

This was another problem on graph that's very easy to, to state.

We use, again, a slightly different graph model.

Last time, we had edge-weighted graphs for computing minimum spanning trees.

Now, we're going to have edge-weighted directed graphs.

So now the edges are directed, but they're weighted.

And the problem that we're going to be looking at is to find the shortest path

from one vertex to another. So in this example, we've got a directed

graph with a variety of edges, the directed edges.

And our goal is to find given two vertices, say zero to six, what's the

shortest path that takes us from zero to six.

Where the length of the path is the sum of it's weights.

And in this case, the shortest distance from zero to two, two to seven, seven to

three, and three to six. Now, the algorithms that we're going to

look at for this are classic algorithms and this is an example where years ago we

would teach these algorithms, Algorithms and say, well, they will be

important someday, When people have devices, with maps on

them and will want to get around. Nowadays, of course, everyone's familiar

with these kinds of devices. When you have a map and you want to get

from one place to another or you have, a device, in your car that gives you

directions to get from one place to another.

These devices are implementing the classic algorithms that we're going to talk about

today. Not only that and even more important,

shortest path is a really interesting and important problem solving model. There's

all kinds of important practical problems that can be recast as shortest paths

problems. And because we have efficient solutions to

the shortest path, efficient algorithms for finding shortest paths, we have

efficient solutions to all these kinds of problems,

All around us. From texture mapping, to network routing

protocols, to pipelining, to trucks, to traffic planning, we find shortest path

applications and we'll look at a couple surprising examples later on today.

So one thing to think about is, let's specify really what the problem's all

about a this all different variance, similar to many other problems we've

studied. So one thing is, what vertices are we

talking about? So, of course, the most familiar is

so-called source-sink. What's the shortest path from one vertex

to another? But actually, more useful often is

so-called single source shortest path, which is all the paths from one vertex to

every other. And this is the one for example that the

navigation system in your car might use. The source is where you are and it'll

compute the shortest paths to every place else.

And then when you ask for some place it'll just pick the one that you want in a

manner very similar to the API that we're going to talk about.

Another thing that you might do if you didn't have that many vertices is compute

all pairs of shortest paths. So, precompute the path between all pairs

of vertices. And then immediately be able to direct

answer a client query. This is the type of thing that was used on

the old map, for example. Another thing is the edge-weights.

Usually, we think of it in terms of positive edge-weights cuz the maps are

geometric and so the length of an edge is proportional to it's distance in the

plane. But, actually for many problems there may

be much more arbitrary and actually one of the big issues that we'll see is whether

the eggs, edge-weights are positive or negative.

And those types of restrictions are going to give rise to different types of

algorithms. Another issue that arises and is

particular important in the presence of negative weights that we'll see at the

end, Is weather or not the graph, graph has

directive cycles. In particular whether the total length of

a cycle is negative or not and we'll get to that at the end.

So, and also, just to reduce some clutter in our code in the slides, we'll

throughout the lecture, make the simplifying assumption that there are

paths from the source to every vertex. We won't worry about driving to islands

and other such issue. To get started, we have to develop our

APIs. And this'll be straightforward after cuz

this is the fourth variation of a graph API that we've done.

We started with, regular undirected graphs,

Then we did digraphs, Then we did weighted, graphs,

And, now, we're doing weighted digraphs. So to begin, we're going to need a API for

processing edges. And this is actually simpler for digraphs

than it was for undirected graphs, Cuz we have this concept of one of the

vertices is, where the edge goes from and the other vertex is where, is where it

goes to. So we have our constructor that builds an

edge from, The vertex that's given it's first

argument to the vertex that's given it's second argument and there's a double list

of weight. And then, the client can ask for the from

vertex or the to vertex or the weight or string representation.

And always in our code we'll use the idiom at the bottom of the slide for processing

an edge. We'll pick out v which is e.from and w

which is e.2 and then our code will process v and w.

The implementation of a weighted directed edge is very similar to the one for

undirected graphs, but simpler, Because, the, constructor, simply sets the

instance variables from its argument, And from and to are simply getter methods

as is weight. So that's implementation of directed edge

for directed weighted graphs. So now what about the graph itself?

So, edge-weighted digraph. So, as usual, we have a constructor, that

gives, that takes the number of vertices in the graph,

So we can build data structures that are vertex, vertex index arrays.

Or we can reterminate the input stream. And then the key methods are add edge,

which takes in directed edge and adds it to the graph.

And then the Iterable per adjacency list, which returns an Iterable of all the edges

that point from a given vertex. So since we're processing edges, we can

have self loops and parallel edges and most of our code will simply use adj

method to iterate through the edges adjacent to vertices.

Representation, is very similar to the other representations, that we've seen,

except simpler, Because it's only one representation of

each edge. So, there's a, the, instance variable for

the adjacency list is a vertex index array.

Each entry is a bag of directed edges, actually, references to directed edges.

So, the, all the code for, building and processing this is very straightforward

version of code that we've seen before. Here's the implementation, for,

edge-weighted digraphs. It's the, the same as our edge-weighted

graph, except, we just replace graph with digraph, everywhere.

And, when we add an edge, we only add it to the from vertices adjacency list.

So v is e.from, adj v equals add, add the edge to that.

And then to get all the vertices adjacent to a given vertex we just re-used the

vertex array just to get its adjacency list and return that bag which is

Iterable, So that the client can iterate through all

those vertices. A very straightforward version of what we

did for edge-weighted graphs. Okay,

So now, our client for that program is, our single source shortest paths, API.

And so, it works in a manner very similar to others that we've done and we'll call

it SP. The constructor takes a graph and a source

vertex and it'll go ahead and build the data structures.

It'll find the shortest path from the short, from s vertext to every other

vertex in the graph and build the data structures, so that it can efficiently

answer client queries of, first, what's the length of the shortest path from s to

a given vertex? And second, what's the path,

Give, an, an iterable that gives the path from the source vertex, from the source

Shortest Paths APIs

Algorithms, Part II

Meet the Instructors