Core: Shortest Path with BFS

Loading...

来自 University of California San Diego 的课程

Java 高级数据结构

920 个评分

University of California San Diego

Java 高级数据结构

920 个评分

课程 3（共 5 门，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.

从本节课中

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

与讲师见面

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 this video we're going to be reexamining breadth first search, and

looking at simplifications, essentially, for

finding the shortest path through a graph.

So at the end of this video you should be able to describe breadth first search's

value for unweighted graphs.

To do this, we're going to work through an example.

What I have here are a number of vertices and edges.

We're gonna look for a path between vertex zero and vertex four.

So how are we gonna do this?

Well if we apply breadth first search, as you already learned from the previous

week, what you're gonna find is, I have set up a queue.

I'm gonna insert V0 into that queue.

And I'm gonna mark that one essentially as distance zero.

Distance zero from itself, right,

then, what I'm gonna do is I'm gonna remove the zero from the queue.

I'm gonna look at all the neighbors of V0 and add them into the queue.

So V1 is one away from V to zero so its going to have a distance of one,

and we'll mark it as visited and then insert V1 into the queue.

Next in line we look at pop and

we'll remove V1 from the queue, and then I'm gonna look at its neighbors.

So what I'm gonna do is I'm gonna look at V2, I'm gonna say that it

has a distance of two because it's one greater than the distance of V1.

And the distance of V1 was one, so the distance for

V2 is two when market is visited and I'm going to add it to the queue.

Next I'm going to look at V4, I'm going to mark this distance as two and

I'm gonna realize, wait I'm looking for V4.

All right this is the thing I was looking for from the very start.

So now that I found it, can I stop now?

Are we done?

Go ahead and answer this as an in video quiz and we'll come back in just a second.

So in your in video quiz I hope you realize we are actually done now.

We can stop.

But I want to explain why we can stop because understanding why we can stop at

this point is going to be essential for

developing the next algorithms going forward.

So let's think about it this way.

So this point in time, after we've pushed V2 onto the queue and we're looking

at V4 and we've recognized V4's distance as two, what's going to happen next?

So let's mark that point in time,

essentially at where we recognized V4's distance is two, and let's just keep it.

So the next thing we would have done was push V4 onto the queue, or

inserted V4 into the queue.

Then we would have looked at V2, we would have removed V2.

We would have looked at the neighbors of V2.

Marked V3 as a distance of 3 and then inserted V3 into the queue.

At this point then we'd keep emptying the queue but you recognize we've already

visited all of our nodes so this would actually be pretty clean.

But I really want you to pay attention to, is that point in time again, where we

found a V4, and we recognized its distance was two.

If we label distances for each of these zones in the queue, I think we're gonna

understand really clearly, why we could have just stopped right there.

So I put these distances here, you're gonna recognize that V0 has a distance

of 0, and then they essentially ascend in distance.

So that point in time when you saw V4 and

you knew its distance was two, the only things that are gonna be

added to the queue after that are gonna be as distant or further distant.

So we know we've essentially found the shortest path and

that's why we're able to stop right then.

Now, the big question is, does this work for all graphs?

We're gonna find that out in the next video.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取