Core: Dijkstra's Algorithm

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

891 ratings

University of California San Diego

Advanced Data Structures in Java

891 ratings

Course 3 of 5 in the Specialization Object Oriented Java Programming: Data Structures and Beyond

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

From the lesson

Finding shortest paths in weighted graphs

In the past two weeks, you've developed a strong understanding of how to design classes to represent a graph and how to use a graph to represent a map. In this week, you'll add a key feature of map data to our graph representation -- distances -- by adding weights to your edges to produce a "weighted graph". Although this might seem like a small change, the algorithms that work for unweighted graphs may prove ineffective for weighted graphs. To address this problem, you'll explore more advanced shortest path algorithms. First, you'll see how to find the shortest path on a weighted graph, then you'll see how to find it more quickly. In the project, you'll apply these ideas to create the core of any good mapping application: finding the shortest route from one location to another.

Core: Shortest Path with BFS3:28

Core: Geographic Maps4:12

Core: Dijkstra's Algorithm8:56

Concept Challenge: Performance of Dijkstra's Algorithm8:02

Core: A* Search Algorithm5:14

When I struggled: Tackling large programming projects1:26

When I Struggled: Remembering classical algorithms0:31

Meet the Instructors

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

[MUSIC]

In the last video we saw how breadth first search has some limitations when you

start with weighted graphs.

So what we're gonna do now is start looking Dijkstra's algorithm.

How Dijkstra's algorithm is gonna solve the source path problem for

again, weighted graph.

So by the end of this video you should be able to apply Dijkstra's algorithm.

You should be able to write the code to implement Dijkstra's algorithm.

You should be able to explain how a Priority Queue works, and

how a Priority Queue is used within Dijkstra's algorithm.

So looking back, when you first saw breadth-first search code.

You recognized that this was using a queue as the main core data structure as part of

the algorithm.

We also know the algorithm looks something like this.

What we're going to now is use a different data structure called a priority queue.

Now a priority queue,

the analogy here that works quite well is a hospital waiting room.

So there's a queue of people waiting to be seen.

And maybe these people all have a cold or a flu.

But the ambulance shows up and

someone's having a heart attack, they get higher priority.

They're gonna be seen by the emergency crew a lot

faster than the people with just a cold.

And this is the way the priority queue works.

So it's just like a queue,

except each person in the queue has a priority attached to them.

So whenever you enqueue an item,

you're gonna enqueue the element as well as its priority.

And when you dequeue, you're gonna get back the person or

the item in the queue that has the highest priority reserved right now.

Now, priority queues are actually implemented using Heaps.

And you can prioritize either based on low values with Min-Heaps or

high values using Max- Heaps.

But we're only gonna get into the details of how to design a heap in this module.

So now we can start looking at how we're going to change our code

from Breadth-forsearch search to now work for Dijkstra Algorithm.

First off, we're gonna use a priority queue.

So all the places that you saw in Breadth-forsearch that you used a queue.

Are now gonna be replaced with operations using the priority queue.

We're also gonna have to keep track of essentially the best distance we've

seen so far for each node.

And I'm gonna initialize that at the very start to be infinity for

each of the nodes.

Again, I'm gonna be working the priority queue.

So we're always gonna be in queuing S, which is a start node.

Along with the priority of it,

which is zero because it's the start node, into the priority queue.

And then as long as the priority queue is empty, we're gonna keep working.

And there's some changes here in that you can actually have a single

node be in the queue multiple times at different priorities.

So what you have to do right at the very start is just to check.

Have I visited this node yet?

And if you haven't visited the node, you do all the work.

If you've already visited the node, this is just a duplicate.

You don't do any work.

So do that test first.

If it hasn't been visited before, now you mark it as visited.

We'll still check to see if this is one that we're looking for.

Just like we did with breadth-for search.

We're still going to go through each occurence neighbors,

that aren't in the visited set.

Except now we aren't adding to the visited set anymore.

Because we do that only if we pop an element from the queue.

So that piece has been removed from the breathe of our search.

Next we're gonna check if the path the current in is shorter

than what we've seen before.

So remember we're keeping essentially the best found path to each nodes distance,

associated with each node.

Again, right now all of them are marked on this map, on this graph as infinity.

So if it's better, then we're going to update the distance,

potentially update the parent map.

And then enqueue, and

again, instead of just doing enqueuing a node, we're gonna enqueue the node

plus the distance to that node from the start node into the primary queue.

Okay, so a lot of changes there.

I think this'll make a lot more sense once we start working through the example.

So what we gonna try to do is we're gonna start with essentially no V0.

That's our start node.

We're gonna initialize it's distance to the node, V0 to V0, and we're gonna

insert into the prior enqueue, again, is that pair of V0 and the distance of zero.

Vertex, distance for each time in the priority queue.

Next we're gonna remove V0 from the priority queue and

we're gonna make that the current node that we're looking at.

And when I'm doing this in these slides I'm gonna always mark the current node

as essentially the red one.

First thing we're gonna do is because V0 hasn't been visited before,

we're gonna mark it now as visited.

And I want to mark it as visited by making it blue.

Next I'm gonna look at all the neighbors of V0 and find that V0 has an edge to V1.

And its distance is gonna be two.

And the reason I know its distance is two is because the distance to V0 is zero.

The edge weight from V0 to V1 is two.

You add those and you get a distance of two.

In doing so I'm gonna mark the distance of V1 to V2.

And I'm gonna insert into the priority queue V1 with a distance of two.

Next we're gonna remove V1,2 from the priority queue.

We're gonna make current be V1.

Just like before, V1 hasn't been visited before.

So I'm gonna mark it as visited.

And then I'm gonna start looking at its neighbors.

So first thing I'm gonna do is, I'm gonna recognize that V2 can be reached

at a distance of three, not a distance of infinity.

And the reason I got three is that the distance to V1 is two and

the edge from V1 to V2 has a weight of one.

So two plus one is three.

I'm then gonna look over to V4 and

recognize I can reach V4 with a distance of eight.

And again, the reason I know I can reach it with a distance of eight is because I

have V1's distance is two, and the edge from V1 to V4 is six.

If you sum those, you get eight.

And then when I add both the {V2, 3}, we already did that, as well as {V4, 8}.

And again, recognize that the larger distances here are gonna have

a lower priority.

So V2, 3 is essentially at the front of the list because it's priority is three.

Next, we're going to go to the next node.

So we're gonna remove V2 from the list.

We're gonna mark that as our current.

And just like before, because V2 hasn't been visited before,

I am going to mark it now as visited.

And now I am going to look at the edges from V2.

And I'm gonna see that I have a way from going V2 to V3 as a distance of five.

So, I'm gonna update that infinity, change it over to be five.

And we're gonna insert V3, 5 into the priority queue.

Because five is less than eight, it's gonna be pushed to the very front

of the queue, even though V4 has been in there longer.

So again, we're basing this on priority,

not how long the element's been in the queue.

At this point, we're essentially done with V2, so we're going to go to the next step,

which would be to remove V3 from the queue.

Make V3 the current node because V3 hasn't been visited,

we're gonna mark it as visited.

And then, we'll look at the neighbors of V3.

And we'll see that five plus one, the distance from V3 to V4,

through the path from V0 to V1 to V2 to V3.

Is shorter than the previous distance of eight, that V4 was marked with.

So what I'm gonna do then is change that eight to be a six.

And I'm gonna enqueue that into the priority queue.

So now we have {V4, 6} being inqueued into the queue,

it takes a higher priority, because 6 is less than 8

I wanna point out at this point we have two entries for V4 in the queue.

Well that's totally okay.

If you remember right at the start of this video.

I said we add this extra clause, which was to say if you DQ an element you check,

has it been visited before?

If it already has, you don't do anything.

So it's okay for us to have multiple entries for V4, essentially, in our queue.

That's totally okay.

Next thing I'm gonna do is I'm gonna remove V four comma six from the queue.

Make V four our current node.

I'm going to mark V four as visited because it hasn't been visited before.

And we're done.

We found our source path from V four,

from V zero to V four to have a distance of six.

And just like when we talked about looking at BFS.

We don't need to look at anything else in this cue.

Because everything that's in the cue after this is gonna have a higher distance.

So we have a larger distance, we don't need to look at those anymore.

One thing I haven't covered through this video, and

I know there's a lot of details that we just worked through.

I didn't work through the details on how to obtain that parent HashMap.

And I want you to think through that on your own.

Because you're essentially gonna be doing this code for the assignment this week.

Good luck.

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.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play