Explore
For Enterprise
Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Notas
Certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

Proof of Correctness (continued)

Loading...

Algorithms on Graphs

Universidade da Califórnia, San Diego

4.7 (1,145 classificações) | 48K alunos inscritos

Curso 3 de 6 no Estruturas de dados e algoritmos Programa de cursos integrados

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. Do you have technical problems? Write to us: coursera@hse.ru

Visualizar o programa do curso

Habilidades que você aprenderá

Graph Theory, Graphs, Graph Algorithms

Avaliações

4.7 (1,145 classificações)

5 stars
893 ratings
4 stars
199 ratings
3 stars
36 ratings
2 stars
14 ratings
1 star
3 ratings

SK

Apr 24, 2018

This course is very much helpful for the graph beginners. As a suggestion, i would like to say that add some extra contents on the data structures which is to be used in the algorithm.

NG

Jun 28, 2019

Loved the explanations and proofs. They are so explicitly told. And the discussion forum for you well assorted problems in assignment is really helpful.

Na lição

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

Ministrado por

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Daniel M Kane
Assistant Professor
Neil Rhodes
Adjunct Faculty

Transcrição

Now the main result is that one node u is discovered during breadth-first search.

The dist value, the estimate of distance to this node from origin,

is assigned exactly the correct distance from node S to node u.

Let's prove this.

To prove it, we'll use mathematical induction, and as a base case,

we see that one node S is discovered.

This is the first node to be discovered.

The dist value is assigned to 0, and

this is actually the correct distance from S to itself.

So we'll use induction on the distance to the node.

So, the inductive step is that suppose we proved our statement about

correct distances for all nodes, which are distance at most k from the origin.

And now we'll prove it for nodes at distance exactly k + 1.

If we do that, we'll prove the lemma itself.

So now, taken out v at distance k + 1 from the origin,

we know that for all nodes which are closer,

the correct distances are found during breadth-first search.

Now let's prove it for this particular node v.

So we know that v was discovered, because it is reachable.

And we proved that all reachable nodes were discovered during

breadth-first research.

So it was discovered while processing some other node u.

Now let's estimate the distance to u.

From one point of view, we know that the distance from S to v is at most distance

from S to u plus 1, plus this edge from u to v through which v was discovered.

And we know the distance from S to v is exactly k + 1,

and that means the distance from S to u is at least k.

From the other hand, we know that v is discovered only after u is dequeued.

And using the order lemma, we can state that the distance to u is strictly less

than distance to v, because otherwise v would be discovered before u is dequeued.

And so distance from S to u is strictly less than k + 1.

And we already know this at least k.

And we also know this distance is integer number.

And so the only option is that distance from S to u is exactly k.

And then see what happens when we assign this value for v.

We assign it to this value of u + 1, which is k + 1.

Which is the same as the distance from original to v.

So we proved our lemma by induction that when the node is discovered at that point,

it is assigned correct distance estimate and it is saved in this value.

And the last property we want to prove, just to understand better how

breadth-first search works and to apply it to some nonstandard situation,

is that the queue which we use in the breath-first search looks like this.

It first has some nodes of distance d for some d, and

maybe in the end it has some nodes of distance d + 1.

But it doesn't contain any other distances.

If the first node in the queue has distance d,

then there are no nodes in the queue with distance less than d,

there are no nodes with distance more than d + 1.

And maybe there are some nodes at distance exactly d + 1, but

they all go after all the nodes at distance d in the queue.

Let's prove that.

So first, we know that by order lemma,

all nodes at distance d were enqueued before first such node is dequeued.

And nodes at distance d + 1 are only found

when a node at distance d is dequeued in process.

So, this means that nodes at distance d were enqueued before nodes at

distance d + 1 were dequeued.

Also, we know the same thing for nodes at distance d- 1,

so they were all enqueued before nodes at distance d.

So by the time node at distance d is dequeued,

all the nodes at distance d- 1 are already dequeued from the queue.

So there are no more nodes in the queue at distance d- 1 or less.

And regarding the nodes at distance more than d + 1, they will be

discovered only when we start dequeuing nodes at distance d + 1 and more.

But those nodes are all going after nodes at distance d.

So at the point when the first node in the queue has distance d,

no nodes at distance more than d + 1 can be in the queue,

because no nodes at distance d + 1 were dequeued and so

we couldn't put anything at distance more than d + 1 in the queue.

So we proved this property.

Also, and now we have to prove that our algorithm finds correct distances

to all the reachable nodes in the graph,

that it finds infinite distances to the unreachable nodes in the graph,

and we also know the structure of the queue at any given moment in time.

And in the next lecture, we will also learn how to actually,

not only find distance, but

also reconstruct the shortest path from the origin to the node we need.

Because we don't want to just know that the distance in terms of number of

flight segments from Moscow to San Diego is two, we also want to find

are those two flight segments to actually get from Moscow to San Diego.

So, see that in the next video.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados