Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees and Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Dijkstra's Algorithm

Loading...

Algorithms, Part II

Princeton University

5 (771 ratings) | 93K Students Enrolled

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

Skills You'll Learn

Graphs, Data Structure, Algorithms, Data Compression

Reviews

5 (771 ratings)

5 stars
746 ratings
4 stars
20 ratings
3 stars
2 ratings
2 stars
2 ratings
1 star
1 ratings

MK

Mar 25, 2018

Excellent course that provides a good introduction to more advanced algorithms that build on those presented in part 1 of the course. Thank you Professor Sedgewick and Kevin Wayne.

QZ

Aug 19, 2018

This class is amazing. If you follow this course schedule strictly, and finish the homework and interview questions, you are gonna to learn a lot of algorithm thinking methods.

From the lesson

Shortest Paths

In this lecture we study shortest-paths problems. We begin by analyzing some basic properties of shortest paths and a generic algorithm for the problem. We introduce and analyze Dijkstra's algorithm for shortest-paths problems with nonnegative weights. Next, we consider an even faster algorithm for DAGs, which works even if the weights are negative. We conclude with the Bellman−Ford−Moore algorithm for edge-weighted digraphs with no negative cycles. We also consider applications ranging from content-aware fill to arbitrage.

Shortest Paths APIs10:51

Shortest Path Properties14:46

Dijkstra's Algorithm18:58

Edge-Weighted DAGs19:23

Negative Weights21:01

Taught By

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer

Now we'll look for, at Dijkstra's algorithm for finding shortest paths in

graphs with non-negative edge weights. Dijsktra is a famous figure in computer

science. And you can amuse yourself by reading some

of the things that he wrote. He was a very prolific writer, and, kept

notebooks. And then here really some of his, famous

quotes. Now, you need to may know something about,

old languages to appreciate some of these. For example, COBOL was one of the first

business oriented languages, programming languages and it tried to, make it so that

programs kind of read like English language sentences.

But purists in computer science, such as Dijkstra really didn't like that language

as you can tell, The use of COBOL cripples the mind.

It's teaching should therefore be regarded as a criminal offense.

Actually, when I first came to Princeton and was setting up the department here,

One of, there was a big donor, who actually, wanted to have me fired and the

department closed down because we wouldn't teach COBOL.

I didn't know about Dijkstra's quote at that time,

I wish I had. And there's some other opinions that

Dijkstra had. You can amuse yourself on the web, reading

some of his writing, But he was, here's another one that's

actually pretty relevant today. Object-oriented programming is an

exceptionally bad idea that could only have originated in California.

Dijkstra worked in Texas, the University of Texas for a while, and of course, came

from the Netherlands. Okay.

But, Dijkstra, did, invent, a very, very important algorithm, that's very widely

used for solving the shortest paths problem.

It's the one that's in your maps app and in your, car, and many, many other

applications. So let's take a look at how that algorithm

works. It's a very simple algorithm.

We, consider, what we're going to do is consider the vertices

In increasing order of their distance from the source.

So and a way we're going to do that is take the next vertex, add it to the tree

and relax all the edges that point from that vertex.

So let's talk about it in terms of a demo and then we'll look at the code.

So our mandate is to consider vertices in increasing order of distance from the

source. So, our source is zero in this case so

what vertices are closest to the source? Well, we can look at the edges that point

from that vertex. Well, start out with vertex is zero, is

the distance zero from the source, so we pick it.

Then we add that vertex to the shortest paths tree, and relax all its edges.

And relaxing all the edges pointing from zero in this case is just going to uptake

the, this two and edgeTo entries for five, eight, nine.

So in this case, this says that the shortest path from zero to one is to go

along zero, one and that's distance five and from zero to four, it's to go along

zero, four and that's distance nine, And zero to seven, let's go take it zero,

seven that's distance eight. And the edge weights are positive.

We're not going to find a shorter path to anyone, of what,

Sorry. The edge weights are positive and those

are the shortest paths that we know so far to the vertices.

Now, the first key point of the algorithm is take the closest one.

If you take the closest one, in this case, it's one, Then we know we're not going to

find a shorter, shorter path to one. The only other way to go out of zero is to

take one of these other edges, and they're longer.

So, and all the edge weights are positive. So we're not going to find a shorter way

from zero to one, than to take the edge, 0-1.

So that means that edge 0-1 is on the shortest path tree,

That's what the algorithm says. Take the next closest vertex to the

source. in this case, it's one. And then,

We're going to add that edge, that vertex to the tree.

And relax all the edges that point from that.

So now both zero and one are on the tree, so now let's look at the edges pointing to

that and we have to relax each one of those.

So in this case if you go from one to four, Then we look at four, we know a path

of length nine. And one to four doesn't give us a shorter

path, so we leave that edge alone. One to three gives us a shorter path to

three which is going to be twenty, cuz you went from zero to one, and then one to

three is of length twenty. And one to two, also, we didn't know a way

to two, But now we know now we know one, or better one is seventeen.

So that completes the relaxation of all the edges pointing from one.

So now we have zero and one on the tree, And.

We would, consider next, The next closest vertex to the source.

So what we have in this two is the shortest paths to all the vertex, vertices

that we've seen so far and this one says that the we've been to the zero and one so

the next closest one is seven, which is distance eight.

So we are going to choose vertex seven. And again, that's the shortest path we've

seen so far, we are not going to find a shorter one cuz to get to every other

vertex is longer. and so, we know it's on the shortest paths tree, and now we're

going to relax all the edges pointing from seven.

In this case, both of them, the one from seven to two, gives us a shorter way to

two than what we knew before, and the one from seven to five gives us a shorter way

to five than we knew before. Well, we hadn't been to five before.

So that relaxes seven, so now seven is on the shortest paths tree.

So now 4's the next closest path vertex to the source.

From the edge zero, four which is of length nine.

So that's the one that we're going to pick next for the tree.

We're not going to find a shorter path there,

And we relax, relax along all its edges. In this case, we find a shorter path to

five than we knew before and a shorter path to six, well, we visit six for the

first time. Okay, so that's four, so now we just have

to worry about two, three, five, and six, and five is the one over there, and so we

select vertex five, Relax along its edges. In this case those edges both give us

better paths than we knew before. So now we're left with three vertices, and

two is the winner. This is the two from the sources fourteen,

To three, it's twenty and to six, it's 26. Relax it's edges, and it gives us again,

new shorter paths to both three and six. And then the last, this next to last step

is to pick three and that does not give us a new way to six, and then finally we pick

six. And then we now know,

The shortest path to all the vertices from vertex zero.

If we just take the edgeTo edges, That's from one, to one you take zero, to

five you take two, And so forth you get the shortest paths tree and that gives the

shortest way to get from the source to every vertex.

That's a simulation of Dijkstra's algorithm.

Here's a demo of Dijsktra's algorithm running in a large digraph.

So the source is the protects the center with the open circle and you can see it

considers the vertices in the graph in order of their distance from the source.

Now you can see this is maybe like a lake in the middle of the graph,

And so it's not going to move on from those vertices.

It's going to take a little while to get around the lake.

And again, if, this visualization is produced by our code,

Then it, and it gives a very, natural feeling for the way that the algorithm

works, This, in principle. And I think, in fact,

in many cases, is what your, car does when you turn the map system on,

It computes the shortest path to everywhere,

And then it's all ready when you ask for a certain place, how to get there.

So here's just, starting from another point in the graph.

You have, if you happen to live at a corner of the Earth, then it's going to be

slightly longer to get to the other corner.

And, a nice feeling for how the algorithm gets its job done.

Again, when it gets into those blank areas, it takes a little while to get over

to the other side. And of course if we had islands, if we had

little roads in the middle there that were not connected,

Then we know where to get to them from the source and we wouldn't see them.

And that's fine for the way our algorithm works.

We just leave that out of the demo and the proof to avoid adding an extra comment

about that for every algorithm. That's a visualization of Dijkstra's

algorithm on a large graph. So, so how do we prove it's correct?

Well, essentially we've prove that it's an instance of the generic algorithm.

So, first thing is that every edge is relaxed exactly once.

Every time we, everytime we put a vertex onto the tree, we relax all the edges that

come from that vertex and we never reconsider the vertex.

And what does relaxation do? Relaxation ensures that after the

relaxation, either way there was before, afterwards, you have the distance to w is

less than or equal the distance to v plus e to the, e plus the way to the edge.

Either it's equal cuz we just made it that way, or it's less than it was before and

the edge was not relevant. And this inequality is going to hold for

every an, entry for every edge corresponding to every edge, for just two

entries corresponding to every edge because number one, the, these two values

are always increasing. We never I'm sorry, we're always

decreasing. The only thing we ever change, only reason

we ever change distTo w is to make it smaller.

If we, if we found an edge that would make it bigger we ignor that edge,

So it's always decreasing. So when we change distTo w, we're not

going to make that inequality holds. We're just going to make it better.

And this distTo v is not going to change at all.

Once we relax an edge from a vertex, we're done with that vertex.

We're not going to process that at all. So, then when we're done we have the

optimality conditions hold that exactly is the optimality condition.

And, not only that, we have a path from the source to every vertex.

So that's the correctness proof for Dijkstra's algorithm based on the

optimality conditions. Here's the code.

It's similar to code that we've seen before.

We're going to use the indexed priority queue that allows us to implement the

decreased key operation. And we have our edgeTo and distTo arrays

that are part of the shortest paths computation and the goal of the shortest

paths computation. So we initialized the constructor,

initializes those rays and including the Index

Minimum PQ. and we start out with all the distances infinity except for the distance

of the source is zero. We put the source on the priority Q and

then what we're going to do is take the, Edge that closest to the source off the

priority. That's on the priority queue off and then

relax all the edges that are adjacent to that, so I'm using our standard iterator

to get all the edges that emanate from that vertex and relax them. And then the

relax code is just like the code that was showed when describing relaxation, except

that it also updates the priority queue. If the, vertex, that, that edge goes to is

on the priority queue, it gives a new shorter way to get to that,

So we have to, decrease the key on the priority queue,

Cuz if it's not on the priority queue, we insert it,

And that's it. That's a complete implementation, of

Dijsktra's algorithm using modern data structures.

Now, this algorithm might seem very familiar than, if you've been paying

attention. It's essentially the same algorithm as

Prim's algorithm. The difference is that, in both cases,

we're building what's called a spanning tree of the graph.

But in Prim's algorithm, we take a vertex that, that's not on the tree using the

rule of let's take the vertex that's closest to the tree, anywhere on the tree,

Closest to some vertex on the tree. For Dijsktra's algorithm, we take next,

the vertex that's closest to the source through a path, they go through a tree and

then into a non-tree vertex. That's the difference and the differences

in the code have to do with the fact that Prim's algorithm is for an undirected

graph, Dijsktra's algorithm is for a directed graph,

But essentially, they're the same algorithm.

And actually, several of the algorithms that we've talked about are in this same

family. They compute a spanning tree.

I have, you, you have a tree that takes care of where that records where you've

been in the graph, From every vertex, back to where you

started. Then you used different rules for choosing

which vertex to add next. For breadth-first search, you use a Q, for

depth-first search, you use something like a stack and then you have to decide what

to do, if you encounter a vertex that you've been to before.

But many graph algorithms use this same basic idea.

So in particular, when we are talking about what the running time of Dijsktra's

algorithm, it depends on what priority Q the implementation we use,

And it's the same considerations as for Prim's algorithm.

We have V insert operations, every vertex goes on to the priority queue. V

delete-min, every vertex comes off the priority queue. and for every edge, in the

worst case, we could compute decrease-key operation.

So, the original implementations of Dijsktra's algorithm used an unordered

array, Which would mean that it would take time

proportional to V to find the minimum, To find the vertex closest to the source.

So the total running time would be proportional to V squared.

That's not adequate for the huge sparse graph that we see in practice today like

the map in your car. So, the binary heap data structure, makes

the,, makes it feasible to run this algorithm.

And that's where all the operations take time proportional to log V.

We have to use the indexing trick that we talked about last time to support

decrease-key. But still, we get a total running time of

E log V, Which makes it feasible.

And just as with Prim's algorithm, by using a implementation of the priority

queue that can do a faster decrease-key, you can get a faster algorithm.

And in, in practice something like a 4-way hit is going to give quite a fast

algorithm. And so, more expensive to insert and t-,

to insert but much faster to delete min in decrease key.

And again, there's a theoretical data structure that's not useful in practice.

It gets the running time down to E + V log V.

Of course, if your graph, graph is dense, And again, the examples I used, they're

not. The array implementation is optimal, we

can't do any better. We have to go through all the edges and

might as well find the minimum, at the same time.

But in, in, in practice, people use binary heaps, for sparse graphs.

I maybe going to four way, If, the performance is really critical.

The bottom line is, we have, extremely efficient implementations for the huge

graphs that arise in practice nowadays.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

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

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates