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.

Loading...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part A

353 ratings

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.

From the lesson

Module 2

Review of Dijkstra's shortest path algorithm. C++ Functions and Generics. C++ classes and OO.
Point as an example.

- 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.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.