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
vertex to the given vertex? So this test client here will print out
all the shortest paths from the given vertex s to every other vertex in the
graph. Go through all the vertices. For every vertex,
You print s to v and the distance from s to v.
And then for every edge in the path, you simply print out the edge,
So it'll print for every vertex, the distance from s to that vertex followed by
the path. So, for example for the sample graph that
we gave with vertex zero as the source it'll print out the path from zero to
every vertex in the graph. So that's a test client that we'll use to
make sure to check and learn the operation of our algorithms.
And this API is going to be effective even for huge graphs.
So that's and introduction to our shortest paths API.