This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.
2.5 Dijkstra Shortest Path
Loading...
Del curso dictado por University of California, Santa Cruz
C++ For C Programmers, Part A
472 calificaciones
De la lección
Module 2
Review of Dijkstra's shortest path algorithm. C++ Functions and Generics. C++ classes and OO.
Point as an example.
Conoce a los instructores
Ira PohlProfessor
Computer Science
Oh, now we're going to describe one of the most
important algorithms in computer science, the Dijkstra Shortest Path Algorithm.
Edsger Dijkstra is a Dutch computer scientist, and he's
one of the most important figures in modern computer science.
He was involved in computer language design, ideas in compiling,
ideas in the semantics, correctness of programming.
And he invented a number of very, very clever and important algorithms.
Dijkstra started his career in the Netherlands at the Mathematical Centrum.
And later became a professor at the University of Texas in the United States.
And he's also one of the very first people to
win the Turing Award, which hopefully most of you know about.
But if you don't the people who've won the Turing Award are what
the analogy is MacArthur Prizes or Nobel Prizes.
We don't have such things in computer science, per se,
and the Turing Award is considered our Nobel Prize.
So in the Dijkstra Shortest Path Algorithm that we're going to
describe, we're going to use undirected graphs with weightings(with cost).
So costs are going to all be non-negative.
And conceptually, what you should keep in mind is a road map, and
the canonical problem is finding the shortest route from one place to another.
So, if you're looking for a road trip and you're going between Chicago and Los
Angeles, and you want a shortest path, you have a very big map.
Lots of roads.
You typically might go to AAA and get some specific assistance.
Or nowadays, you can just use
your on-board trip computer.
And they indeed in, in some important sense (it has embeded )the Dijkstra algorithm.
We're going to learn how to program this critical
algorithm and indeed, it's going to be our next programming assignment.
So, the idea is we have a source and a destination.
Chicago to Los Angeles.
And between the source and destination, we
want to find a shortest path. The
critical steps in the Dijkstra algorithm are to maintain what
I call two sets. One is a set of closed nodes.
The closed nodes
are nodes that
have, have known
shortest distances.
Now if we're starting from Chicago, what do we know?
Right off the cuff, we know the shortest distance from Chicago to Chicago.
That's zero.
That's like trivial case. So, the algorithm would start with the
source node being put in the closed set, and that source node would have value 0.
And then, in the open
set, we would look for immediate
successors of s. And place their distance in the open set.
So the open set is what's reachable. And
at any time in the open set,
we have what's reachable.
And we have a calculation based on the edge cost from things in
the closed set. And what we do, our major iterative step
is we pick the open note in that list, who's cost is least.
Pick the open node who has least cause.
Whoops, least cost, not list cost, least cost.
Confusing list and least. Okay.
If in this iterative step, we pick a node that is the termination node.
If we've, are moving along from Chicago, and we've reached Los Angeles.
And Los Angeles gets thrown in the closed set, we can stop.
The algorithm guarantees that when the destination node
is placed in the closed set, calculation is provably
a shortest distance. If the
destination node is not the node picked as the next least node from the
open set, we compute all the direct successors from
that node. So if that node,
so we, n has least cost.
We look at the edges out of n.
And they have a cost. It might be cost of n to j, where
(n,j) are the determiners of the edge.
And n will have a value, which is its value of
the, the cost from s, from the source. So n has some cost,
some current
cost, back to s.
And that cost, whatever that is, s to n
plus cost ( n , j) is what
it takes to reach j. Now either j is already in the open set.
we have like, three cases. J is in the closed set.
If j was already in the closed set, we don't need to bother with it, because
we already know by the nature of Dijkstra's
algorithms that we have a shortest path to j.
If j is not in the open set, or the closed set, then we put it in the open set.
We now have a new path, a way to get to j. So we're somewhere, past Chicago.
Maybe we're approaching Kansas City and we haven't yet reached Kansas City
in any kind of path that we've calculated. And we see we can get to Kansas City.
That would be placed in the open set with whatever
it's value is, traced back to Chicago.
And the last case is, we already had an alternative route.
We had a pre-computed route.
So j, or Kansas City, in this case, was already in the open set.
But this new route improves on the old route
because we're trying to search for least costly paths.
In that case we update the paths.
So we have three conditions, open set, a possibility for updating, or
it's already in the closed set. And then if the node d is picked, we stop.
There's no further need to look for successors.
Or if there's no more successors, we can't get to d.
So if we try to go from Chicago to Honolulu, we would find all sorts of
paths to places like Seattle and El Paso, and God
knows what else, Los Angeles, but we would have no road
route to Honolulu. So we would exhaust, if we had tried
to put into our travel
computer, find me a road from Chicago to Honolulu, it would stop.
And otherwise some shortest path tree is maintained in the calculation.
And that lets us, when it's done, having stopped at d, not only have
the value of the shortest route but be able to trace back the shortest route.
So I'm going to simulate Dijkstra by hand.
And I'm going to simulate it on this next map.
And I'm going to draw things in red and I'm going to start with S.
And I'm going to want to get us to T.
In this case, I'm doing it in a directed graph.
So this was just the case that I had manufactured and I'll show it to you in
the directed case, but it, it shouldn't be any different in the undirected case.
So initially, the open set s has value 0, and
then s can reach a.
So this is the closed set, and its value is 4.
S can reach b,
and its value is 3. S can reach
d, and its value is 7. And that's it.
The out degree edges of s are 3.
So now we look at the open set. We pick s equals b,
so b comes into the closed set with value 3.
So in some sense, Dijkstra's algorithm has picked out this.
And now b becomes the node we expand from, and so we search b.
Now b can go back to s, but that's not a value, since s is in a closed set.
And b can go to d.
So we have to check if b went to d, it would be 3 plus 4.
But we
already of d at 7, so there's no reason to update it.
And that's the only two ways we can go. So there isn't anything new in
the open set. So we would come back, and we would get as
our least value, a, whose value is 4. And
so now, our Dijkstra's shortest path tree would be
at this point in the second iteration also s going to a with 4.
Now a has some new things we can go to. So from a we can go to
c. The value was 4 plus 1, so now it's 5.
And that's the only thing a can go to. But 5 is indeed
the best value, so we put in c in the closed set.
The c's value equal 5.
And c can reach e with
value 6. And c can
reach d, and that would
be value 8. 8 doesn't
improve on 7, so we don't update that. But we can
go c to e, and that's value 6. So now we cross out this.
We get e.
We get it equal 6. We go back and we find we can go to e.
Oops, no e already went to (6 -sic).
Excuse me, we go back and e is now in the open set.
e has to be expanded. So we get, we can look at e to d.
Now e can't go to d directly, that's the wrong direction.
But e can go to g and g is value 8.
And e can go to t, so it can go to g for value 8.
It can go to t,
and that's value 10.
Now just because we can reach t, which is
our destination, the terminus, doesn't mean we go there.
because this is still in the open set.
The only time we're guaranteed a best or least costly path
is when something's been stored in the, in the closed set.
And there's still values less than 10. So they have to be explored.
The next value that needs to be explored is s going to d at 7.
So s going to d at 7 makes d equal 7 in the closed set.
And then we have d can go to f.
So 7 plus 5 is 12. d from here can go to
t. So that's 7 plus 3, which is 10.
But that hasn't improved the value, so we don't update anything.
And d can go to e, but e is in the closed set, so we don't do anything with that
either. So here we go back, we look.
We've got an e
going to g (value) 8.
And from g, we can go back to e. e is already in the closed set.
We can from g to t.
But 8 plus 3 is 11. We don't improve on 10.
So we leave it alone.
We're done with the updates. We come back, select the node.
And now we find e to t, which is value 10. And e to t,
so t equals 10. We can terminate.
And if we keep our
back lengths in this map, we can even find the shortest path.
Now notice it wasn't unique.
We could have found the shortest paths, which would have been s to d and d to t.
That would have also been 10.
So this doesn't guarantee any kind of uniqueness, but
it does guarantee that we get a least costly path.
You should practice with other graphs.
And the assignment I'm giving out now is that you will try to do a
Dijkstra Shortest Path Algorithm, which will mean
that you need to decide on a representation.
my recommendation is the list representation's a little more flexible.
But it's perfectly okay if you do the matrix
representation, or even do both, depending on how ambitious you are.
And that'll be an assignment that I'll be expecting for the next turn in time.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
