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.