Proof of Correctness

Loading...

来自 University of California San Diego 的课程

Algorithms on Graphs

793 个评分

University of California San Diego

Algorithms on Graphs

793 个评分

课程 3（共 6 门，Specialization 数据结构与算法）

If you have ever used a navigation service to find optimal route and estimate time to destination, you've used algorithms on graphs. Graphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders in Facebook, you're going to work with graphs and algorithms on graphs. In this course, you will first learn what a graph is and what are some of the most important properties. Then you'll learn several ways to traverse graphs and how you can do useful things while traversing the graph in some order. We will then talk about shortest paths algorithms — from the basic ones to those which open door for 1000000 times faster algorithms used in Google Maps and other navigational services. You will use these algorithms if you choose to work on our Fast Shortest Routes industrial capstone project. We will finish with minimum spanning trees which are used to plan road, telephone and computer networks and also find applications in clustering and approximate algorithms.

从本节课中

Paths in Graphs 1

In this module you will study algorithms for finding Shortest Paths in Graphs. These algorithms have lots of applications. When you launch a navigation app on your smartphone like Google Maps or Yandex.Navi, it uses these algorithms to find you the fastest route from work to home, from home to school, etc. When you search for airplane tickets, these algorithms are used to find a route with the minimum number of plane changes. Unexpectedly, these algorithms can also be used to determine the optimal way to do currency exchange, sometimes allowing to earh huge profit! We will cover all these applications, and you will learn Breadth-First Search, Dijkstra's Algorithm and Bellman-Ford Algorithm. These algorithms are efficient and lay the foundation for even more efficient algorithms which you will learn and implement in the Shortest Paths Capstone Project to find best routes on real maps of cities and countries, find distances between people in Social Networks. In the end you will be able to find Shortest Paths efficiently in any Graph. This week we will study Breadth-First Search algorithm.

Most Direct Route9:18

Breadth-First Search7:49

Breadth-First Search (continued)6:15

Implementation and Analysis9:33

Proof of Correctness7:11

Proof of Correctness (continued)5:31

Shortest-Path Tree6:14

Reconstructing the Shortest Path3:27

与讲师见面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hi.

In this video,

we will prove the correctness of the breadth-first search algorithm for

finding distances from an original node to all the nodes in the graph.

We will also prove some properties of this algorithm, which can be useful when you

want to extend this algorithm to other kinds of problems.

First, recall that node u is called reachable from node S,

if there is a path from S to u.

And the lemma states that the reachable nodes are discovered during breadth-first

search.

And they get a finite estimate of distance from S.

And unreachable nodes are not discovered during breadth-first search.

And they stay with infinite distance estimate, infinite distance value.

First, let's prove it for reachable nodes.

So, suppose for the sake of contradiction that some reachable nodes were

not discovered during the breadth-first search.

Then select out of those nodes the one closest to S in

terms of the length of the path.

So, let's assume that u is the closest to S unreachable node,

which was not discovered during the breadth-first search.

Then take the shortest path, some shortest path from S to u.

It goes from S to some nodes of v1 from there to v2 and so

on and up to vk and from vk it goes to u.

Then u will be discovered, actually, while processing vk.

Why is that?

Well, because first, we will discover and process S.

Then we will discover and process v1.

Then we will discover and process v2 and so on.

And we will go up to vk.

And when we process vk, u will be discovered.

So this is a contradiction with the assumption we made for

the sake of contradiction that

some reachable node is not discovered during breadth-first search.

So we proved that reachable nodes are discovered.

And of course, they will find its estimation of distance.

Because this is how the algorithm works.

As soon as the node is discovered, it gets estimation of distance, bigger by one,

than the estimation for the node b process.

Now let's prove this statement about unreachable nodes.

Let's suppose, again, for

the sake of contradiction that some unreachable nodes were discovered.

And let u be the first such unreachable node to be discovered.

Now let's see when it was discovered.

It was discovered while processing some other node v.

And as u is the first unreachable node that was discovered and

v was discovered before u, because u is discovered when v is already processed,

it means that v is a reachable node.

And it means that there is a path from s to v, but

then it means that there is a path from s to u through v.

So u is actually reachable, and this is a contradiction, and so we proved that

unreachable nodes are not discovered during the breadth-first search.

So it works correctly at least in the sense that it finds some distances to

reachable nodes and doesn't find any finite distances to unreachable notes.

Now we will prove the order lemma, which states something about

the order in which nodes are discovered and dequeued from the queue.

It says that by the time some node u at distance d from

the original node is dequeued, it started processing.

All the nodes at distance at most d have already been discovered.

So they have already been enqueued in the queue.

And maybe some of them have already been processed.

Some of them are still in the queue, but

at least, they have already been discovered.

So let's prove this again by contradiction.

Suppose that this lemma is not true and considered the first time

this order was broken, so that some node u at distance d has already

started processing, and that's why it is filled with black.

And some other node v at distance d',

which is at most d has not yet been discovered.

Let's suppose that.

So we know that d' is at most d, and we know that node u

was discovered while processing some other node u'.

And we know that the distance to this node u' is at least d-1,

because if the distance to u' was less than d-1,

then the distance to u would be less than d because there's an edge from u' to u.

Also, we know that the node v has an edge from

some node v' with distance d'-1 from s,

because there is some shortest path from s to v.

And there is the previous node before v on this path, and this is v'.

And distance to v' is exactly d'-1, because this is a shortest path.

So, it can be less than d'-1 because otherwise,

distance to v will be less than d'.

And it cannot be bigger than d'-1 because then

the shortest path to v would be longer than d'.

So, distance from s to d' is exactly d'-1.

And we know that the prime is at most d, and from that,

we know that d'-1 is at most d-1.

And it means that v' was discovered before u' was dequeued because we know that

the first time that order lemma was wrong was with nodes u and v.

And now u' and v' were before that.

So that point of time order lemma still works.

So we know that v' was discovered before u' was dequeued.

So it means that v' was gray before u' became black.

[COUGH] And this means that also, v' became gray before u became gray,

because u became gray while processing u'.

So v' was enqueued and

filled with gray before u was enqueued, discovered, and filled with gray.

What that means is that because our queue works as first in first out, and

v' was discovered before u, it means that v' was also started processing before u.

So v' was dequeued and filled with black before u was dequeued,

and immediately after v' was dequeued,

v would be discovered, because there is an edge from v' to v.

So either v was discovered even before that, or

it was discovered during processing v'.

And we see that v is already discovered, and u is not yet dequeued.

So it is a contradiction with the fact that when u is already black,

v was still white and not discovered.

So we proved our order lemma by contradiction.

探索我们的目录

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

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

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

通过 App Store 下载

通过 Google Play 获取