Projeto e Análise de Algoritmos - Aula 13 - Problema do caminho mais curto

Summary

This video script discusses the shortest path problem in graphs, specifically focusing on the Dijkstra's algorithm for finding the shortest path from a single origin to all other vertices. It explains the concept of relaxation, the importance of non-negative weights for correct results, and how the algorithm constructs a shortest path tree from the origin. The script also touches on the Bellman-Ford algorithm, which handles negative weights and detects negative cycles, and provides an example to illustrate the algorithm's process.

Takeaways

• 📚 The lecture introduces the problem of finding the shortest path in a graph with a single origin.
• 🛣️ The problem is modeled using a graph where vertices represent cities and edges represent paths between cities, each with a weight.
• 🔢 The weight of an edge could represent the distance or cost to travel, calculated as the sum of the prices of all edges in a path.
• 📈 The shortest path is determined by calculating the weights of all possible paths and finding the minimum.
• 🔄 An important characteristic of shortest paths is the optimal substructure, where any subpath of the shortest path is also the shortest path between its endpoints.
• ⚠️ Negative weight cycles can cause issues in shortest path calculations, as they can lead to infinitely decreasing path weights.
• 🛠️ Two well-known algorithms for solving the single-source shortest path problem are Dijkstra's algorithm and the Bellman-Ford algorithm.
• 🚀 Dijkstra's algorithm assumes all edge weights are non-negative and is efficient for graphs without negative weight cycles.
• 🔄 The Bellman-Ford algorithm can handle graphs with negative weight edges but is more generic and may have a higher processing time.
• 🌳 The result of the shortest path problem is a shortest-path tree rooted at the source vertex, showing the shortest path to all reachable vertices.
• 🔄 The relaxation step in algorithms is crucial for updating the estimated shortest path weights and determining the parent vertices in the shortest-path tree.

Q & A

What is the main topic of the video script?

The main topic of the video script is the shortest path problem in graphs, focusing on algorithms for finding the shortest path from a single source to all other vertices.

What is the problem modeled in the script?

The problem modeled in the script is finding the shortest path from Rio de Janeiro to São Paulo, represented as a graph where cities are vertices and the distances between them are edges with weights.

What is the weight of an edge in the context of the script?

In the context of the script, the weight of an edge represents the distance or cost of the path between two cities.

What is the formula used to calculate the total weight of a path?

The total weight of a path is calculated as the sum of the weights of all the edges that make up the path.

What is the property of shortest paths that is referred to as the 'greedy property'?

The 'greedy property' refers to the characteristic that if you have the shortest path from the source to a vertex, any subpath of that path is also the shortest path between the start and end vertices of the subpath.

What happens when there are negative weights in the graph?

When there are negative weights in the graph, it can lead to a situation where the shortest path cannot be determined if there is a cycle with negative total weight, as passing through the cycle an infinite number of times would result in a path with a weight approaching negative infinity.

What are the two well-known algorithms mentioned in the script for solving the single-source shortest path problem?

The two well-known algorithms mentioned in the script are Dijkstra's algorithm and Bellman-Ford algorithm.

How does Dijkstra's algorithm handle negative weights?

Dijkstra's algorithm does not handle negative weights well because it assumes all edge weights are non-negative. It does not account for the possibility of negative cycles that could lead to infinite paths.

What is the data structure used by the Bellman-Ford algorithm to keep track of the shortest paths?

The Bellman-Ford algorithm uses two sets: one for vertices whose shortest path distance is definitive (known) and one for vertices whose distance is still an estimate (provisional).

What is the result of running the shortest path algorithms in the script?

The result of running the shortest path algorithms is a shortest path tree rooted at the source vertex, which shows the shortest path to all other reachable vertices.

How does the Bellman-Ford algorithm perform the relaxation step?

The Bellman-Ford algorithm performs the relaxation step by checking if the current estimate of the shortest path to a vertex can be improved by going through another vertex. If an improvement is found, it updates the estimate and the parent of the vertex in question.

Outlines

00:00

🛣️ Introduction to Shortest Path Problem

This paragraph introduces the concept of the shortest path problem in graph theory, specifically focusing on the single-source shortest path from Rio de Janeiro to São Paulo. It explains how to model the problem using a graph where vertices represent cities and edges represent the paths between them, each with a weight representing distance. The paragraph also discusses the importance of non-negative weights for the optimal substructure property and introduces the notion of a relaxation technique used in algorithms to find the shortest path.

05:01

🔄 Negative Cycles and Algorithms for Shortest Paths

The second paragraph delves into the complications that arise when negative weight cycles exist in a graph, which can lead to an undefined shortest path. It contrasts two well-known algorithms for shortest path problems: Dijkstra's algorithm, which assumes all edge weights are non-negative, and Bellman-Ford algorithm, which can handle negative weights but detects negative cycles. The paragraph explains that the Bellman-Ford algorithm constructs a shortest path tree rooted at the source, showing the shortest paths to all reachable vertices.

10:02

🔄 Relaxation Step in Shortest Path Algorithms

This paragraph explains the relaxation step used in shortest path algorithms, which involves checking if a shorter path to a vertex can be found by passing through another vertex. It illustrates how to update the estimated shortest path if a better path is discovered. The explanation includes an example with a graph of five vertices, showing how to initialize the algorithm and perform relaxation to improve the path estimates, ultimately finding the shortest paths from the source vertex to all other vertices.

15:03

📈 The Bellman-Ford Algorithm's Relaxation Process

The fourth paragraph provides a detailed walkthrough of the Bellman-Ford algorithm's relaxation process. It describes the initialization of estimates and the iterative process of updating these estimates by considering each vertex and its adjacent edges. The paragraph uses a step-by-step example to demonstrate how the algorithm refines the shortest path estimates for each vertex until it converges on the definitive shortest paths from the source to all other reachable vertices.

20:04

🌳 Completion of the Shortest Path Tree

The final paragraph concludes the explanation of the Bellman-Ford algorithm by detailing the completion of the shortest path tree. It shows how the algorithm determines the definitive shortest path to each vertex and updates the tree accordingly. The paragraph ends with a summary of the algorithm's process and an example of the final shortest path tree, highlighting the minimum distances and the edges that constitute the shortest paths from the source vertex.

Keywords

💡Graph

A graph is a mathematical structure consisting of a set of vertices (or nodes) and a set of edges that connect pairs of vertices. In the context of the video, a graph is used to model a network of cities where vertices represent cities and edges represent the paths between them. The script uses graphs to explain how to find the shortest path between cities, such as from Rio de Janeiro to São Paulo.

💡Shortest Path

The shortest path in graph theory is the path with the minimum sum of edge weights between two vertices. The video discusses algorithms to find this path, emphasizing its importance in routing and navigation, such as finding the shortest route from one city to another.

💡Relaxation

Relaxation in the context of the video refers to a technique used in pathfinding algorithms where the algorithm iteratively improves the estimate of the shortest path to a vertex. The script describes this process as updating the path cost when a cheaper path is found, which is central to the functioning of the Dijkstra's algorithm.

💡Dijkstra's Algorithm

Dijkstra's Algorithm is a pathfinding algorithm that calculates the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. The video explains how this algorithm works, starting with an initial estimate of infinity for all paths and then iteratively improving these estimates through the relaxation process.

💡Vertex

A vertex, also known as a node, is a fundamental unit of a graph, representing an entity such as a city in the video's example. Vertices are connected by edges, and the script discusses how algorithms determine the shortest path from one vertex to another.

💡Edge

An edge in a graph connects two vertices, representing a path or connection between them. The video mentions edges as having weights, such as distances between cities, which are crucial for calculating the shortest path.

💡Weight

In the context of graphs, a weight is a numerical value associated with an edge, indicating the cost or distance of traversing that edge. The video script discusses how weights are used in algorithms to determine the shortest path, with the sum of weights along a path being minimized.

💡Negative Cycle

A negative cycle in a graph is a cycle where the total sum of the edge weights is negative. The script warns that the presence of a negative cycle can make the shortest path undefined, as traversing the cycle an infinite number of times would result in a path with a cost less than any finite value.

💡BFS (Breadth-First Search)

Although not explicitly named in the script, the concept of breadth-first search is implied when discussing how algorithms explore all possible paths from the source vertex. BFS is an algorithm for traversing or searching tree or graph data structures, which the video contrasts with Dijkstra's algorithm that accounts for edge weights.

💡Priority Queue

A priority queue is an abstract data type in which each element has a priority, and the order in which elements are processed is determined by their priorities. The video script mentions the use of a priority queue in Dijkstra's algorithm to efficiently select the next vertex to relax.

💡Estimate

In the context of the video, an estimate refers to the current best guess of the shortest path to a vertex. The script describes how these estimates are initially set to infinity and then improved upon as the algorithm progresses through the relaxation steps.

Highlights

Introduction to the shortest path problem in graphs with a single source.

Explanation of the relaxation technique used in shortest path algorithms.

Discussion on modeling real-world problems like finding the shortest route from Rio de Janeiro to São Paulo as graph problems.

Definition of vertices and edges in the context of graph theory and their relation to cities and paths.

Explanation of how edge weights represent distances between cities in the graph model.

Introduction to the concept of path weight as the sum of the weights of all edges in the path.

Description of the all-pairs shortest path problem and the method to find the shortest path between all pairs of vertices.

Explanation of the optimal substructure property of shortest paths.

Discussion on the implications of negative weight edges and their impact on shortest path calculations.

Introduction to the Bellman-Ford algorithm and its ability to handle graphs with negative weight edges.

Explanation of the Dijkstra's algorithm and its limitations regarding negative weight edges.

Presentation of the algorithm's result as a shortest path tree rooted at the source vertex.

Description of the initialization step in the Dijkstra's algorithm where all distances are set to infinity except the source.

Explanation of the relaxation step in Dijkstra's algorithm where the shortest path estimates are updated.

Introduction to the use of priority queues in the Dijkstra's algorithm to efficiently select the next vertex to relax.

Discussion on the time complexity and practical applications of the Dijkstra's algorithm.

Overview of the algorithm's implementation and its steps using a visual example with a graph.

Conclusion of the lecture with a summary of the Dijkstra's algorithm and its significance in solving real-world shortest path problems.

Transcripts

[Música]

o

[Música]

olá pessoal sejam bem vindos à nossa

aula número 13 do projeto em análise

algoritmos nessa hora vemos o problema

de caminho mais curto de uma única

origem grafos

vamos ver a técnica de relaxamento e

vamos ver apenas um algoritmo que faz

essa tarefa que o algoritmo de destro

suponha que você deseja encontrar o

caminho mais curto possível

desde o rio de janeiro até são paulo

então entra aqui para aqui como é

terminar rota mais curta

nesse caso a gente pode modelar esse

problema como um problema em gráficos

você vai ter um grafo conversa encerrar

esta em que os vértices são as cidades e

as áreas são os caminhos entre essas

cidades se você vai ter um peso nessas

tarefas então cada aresta vai ter um

peso associado que seria por exemplo

nesse caso a distância entre o peso de

um caminhão como que vai ser calculado

então dá um caminhão p

aqui temos um caminho que vai de vencer

o avaí eo e terminei ver k vai ser

calculado como a soma dos preços de

todas as arestas que passam por esses

sete meses que seria essa fórmula 1

daqui então temos que o peso no caminho

p essa uma história dos preços das

arestas que vão de 90 cm não sou um

atleta e sair com lhe dizer um até cá

como definimos então o peso do caminho

mais curto de seu a tv de maneira

genérica a gente vai calcular os preços

de todos os caminhos possíveis

isso porque assim existe um caminho ou a

tv

pegamos todos os caminhos possíveis e o

atv e calculamos com o que vai ser o

mínimo então isso vai ser em tom é

definiu como o caminho mais curto desvio

antes eo atleta

então não existe um caminho de uma tv

essa distância deu à tv mais sedada mas

só definirá como infinito tem uma

característica importante nos caminhos

mais curtos que a subir estrutura ótima

está definido aqui nesses lá e depois

vamos ver um exemplo do que significa

isso seja um grafo g que tem um conjunto

levanta e se um conjunto de erez da

sombra foi orientado e compensamos isso

querem ser ponderado e seja um caminho

neste gráfico vamos supor que temos um

caminho que segui todos esses vetos e vê

uma tv cá

se a gente pega um sub caminho desse

caminho vamos supor que pegamos uma

parte desse sucesso desse caminho que

seria por exemplo esse caminho pj que

vai desde 96 atletas e j

esses subica minho também vai ser o

caminho mais curto dizia a tj se esse

caminho daqui era o caminho mais curto

deveu à tv cá de maneira sempre vamos

ver aqui então é sempre um sobre isso

suponha que você conhece qualquer uma o

menor caminho do rio de janeiro até são

paulo

se você já tem isso isso porque esse

realmente o melhor caminho do rio de

janeiro em são paulo

se a gente pega o sub caminho desse

caminho esse caminho também vai ser um

caminho mais curto entre essas cidades

por exemplo se a gente pega o caminho

desde agora tem que tá até são paulo

esse caminho aqui esse caminho aqui

também vai ser um sub caminho mais curto

entre a cidade e agora tem tá até são

paulo

uma outra característica que precisamos

é ver investigar e que acontece quando

temos áreas de pressão negativa

o carro pode vir a lista de peso

negativo sim claro no nosso exemplo

anterior que sobre a distância sobre

caminhos entre as cidades a distância

não pode ser negativo mas para outros 60

anos poderia ter-se uma distância

negativa 1 um peso negativo na verdade

nas áreas como nem sempre a descer grafo

que temos aqui em baixo os pesos do

caminho de caminhos mais curtos não vão

estar bem definidos caso assista um

ciclo de peso negativo

como nesse exemplo de quim aqui temos um

ciclo de peso negativo e seria esse de

quinta e se a p&g ps cujo valor seria

menos dois

toda vez que a gente passa por esse

ciclo a gente vai ter menos 2 - 2 - 2 -

2 - 2 - 2 se a gente passa infinitamente

por ele vai ser menos infinito

é então que aconteça com isso a gente

não pôde calcular qual que o caminho

mais curto quando a gente tem ciclos de

peso negativo se um ciclo de peso

negativo em algum grafo num caminho de

se a tv

então vamos definir que a distância

desse a tv - infinito

existem dois organismos conhecidos para

resolver o problema de caminho mais

curto de um homem de origem que são o

algoritmo de dastan e orgulho de ver na

foto o algoritmo de desta ele vai supor

que todos os presos as arestas um grafo

são negativos

então com ele por exemplo podemos

resolver o problema do caminho mais

curto de são paulo até qualquer outra

cidade do brasil por exemplo né e

organismo verma for ele permitem arestas

e pessoal negativo no gráfico sim o que

ele vai fazer

na verdade ele vai verificar se esses em

ciclos e caso esses ciclos ele vai

detectar isso e vai produzir uma

resposta correta para o problema

o resultado da busca do caminho mais

curto é uma árvore ray sada no na origem

então ele vai mostrar qual é o caminho

mais curto desde a origem em ciência a

tecnologia verde e acessível a partir

desse quem mais a gente já tinha falhado

isso antes também quando a gente

trabalhava com algoritmos de busca em

profundidade em buscas na largura

na verdade o algoritmo de busca em

largura em gráficos

porém nesse caso a gente não trabalhava

com os pesos entre é nessas áreas não

tínhamos peso nas arestas

nesse caso temos é temos um caso do mapa

uma distância entre uma cidade e outra

por exemplo

então o resultado do do caminho mais

curto resolver o problema o caminho mais

curto vai ser uma árvore

aqui temos um exemplo de um grafo e aqui

temos um exemplo das duas possíveis

árvores que poderia ser a solução do

caminho mais curto para esse grafo estão

mostrando se aqui então temos aqui

essa árvore que está enraizada em s

e ele está mostrando que o caminho mais

curto para ir de se ater e passar

exatamente porém saretta de si até que o

custo e 3 o caminho mais curto para ir

dance

a tx tem um pessoal de 9 e ela passa

pelo vértice ele passa pela está e ct-e

área tx e assim por diante

temos uma outra opção que também tem os

mesmos valores

é um caminho mais curto também mas que

passa por outras arestas

quem sabe aqui um caminho mais curto de

si até 3 o caminho mais curto de se a y

r 5

mas ela passa pela área está e citei

pela está tem destino certo que os

custos são iguais então são duas

possíveis soluções para o mesmo problema

o estado orismar de weimar for quanto o

agora os modais

para ele usa eles usam a técnica de

relaxamento

eles vão ter que calcular uma estimativa

do mapa do caminho mais curto que vão

chamar de de dever

então em de ver a gente vai aguardar o

limite superior sobre o peso do caminho

mais curto desde a origem ea tevê início

quando não sabemos nada um grafo esse

limite superior vai ser infinito não sei

qualquer chance de dizer se a teoria é

que se qualquer

então vou colocar infinito então

primeiro vamos fazer a inicialização

passou de inicialização que eu acabei de

falar

como não sabemos nada a estimativa de

qualquer e é o valor do caminho mais

curto até cada vez e ver mas ser

infinito não sabemos quem são os pais

não só colocar mil e sabemos que a

instância de origem e se a teoria inss

serão a gente já está no próprio vértice

agora então vamos ver o passo de

relaxamento

esse passo de relaxamento consiste em

verificar se podemos melhorar o caminho

mais curto para ver encontrado até agora

pela passagem através de u

se acontecer isso vamos atualizar a

nossa estimativa de e também que o pai é

então como key é feito isso se a gente

tem uma estimativa a tba tv de s

isso porque a gente tem é se a gente tem

aqui a gente tem uma estimativa de

qualquer instância passado por outros

vezes até 90 cv

isso porque ela é de dever e agora a

gente vai verificar se passado por uma

agente consiga melhorar isso não tá

agora vamos ter a estimativa até u

vamos ver se um samba a esta o v

a gente consiga melhorar essa estimativa

vamos supor que eu sei que o dever de 20

eu sei

que o dedé eo é tri é vou colocar um

número menor de 15 e à distância entre

um e vem e 3 seu olho aqui então passado

por um eu posso melhorar a minha

estimativa a tv

agora vai ser 18 no lugar de 20

isso é o que está sendo feito aqui se a

estimativa que eu tinha a tv é maior que

a estimativa que eu tenho até o mais o

pessoal da arysta o v

então eu posso melhorar a minha

estimativa como esse valor e aí a

polícia que em que o pai de ver o pai de

ver eu seja a gente está atualizando

quem que o pai de ver agora passava pelo

para chegar em ver esse é o processo de

relaxamento

então quem quer faz valores mobiliários

da extra ele vai calcular qual é o

caminho mais curto tem uma única origem

em um algoritmo orgulhoso

nesse caso ele só permite que as arestas

tenha peso positivo em consequentemente

não vai ter ciclos de peso negativo ele

não vai precisar se preocupar com isso

além disso o tempo de execução o curso

de processamento dele é inferior ao

coritiba for que um pouquinho mais

genérico que ele pode se trabalhar com

arestas negativas valores modais

trabalha com dois conjuntos evets o

conjunto esse que são os doentes cuja

distância para arraes shea conhecida é

ou seja é a definitiva e um conjunto

vermelho não sei se é que o conjunto de

veto e sem que a distância é conhecida

ainda é uma estimativa provisória seja

apenas em estimativa não sei se é

exatamente isso não

para isso o algoritmo vai utilizar duas

estruturas

o ec que vai ser um conjunto de eventos

cuja distância é definitiva e o que para

para guardar os 76 quando estância

provisória é esse que vai ser uma filha

de prioridade

mínima e aqui temos então o pessoal do

código do algoritmo de da strans

ele usa o algoritmo que faz a

inicialização das estimativas e o

relaxamento das estimativas aqui para

ver o funcionamento desse terrorismo

vou mostrar aqui um exemplo então

suponho que temos um grafo com cinco

vértice o vertis e é ct x e y en sei que

estão aqui também nessa tabela em baixo

e temos a qualquer o peso de cada uma

das areias neste gráfico também queremos

saber qual é o caminho mais curto desse

ato até todos os verdes e atingíveis a

partir desse aqui nessa tabela vamos

guardando qualquer estimativa que são os

pais que vai ter a fila de prioridades e

o que vai ter um conjunto esse certo

então no início o primeiro que vai ser

feito vai ser a um passo de

inicialização no momento inicializar a

gente vai colocar que a nossa estimativa

é infinito para todo mundo

os pais é exceto para o noé se que a

instância dsts e terceiro quem são os

pais todo mundo uniu a gente não sabe

quem é o pai na área da resposta

e aí depois a gente vai ver é

inicializar o conjunto e se com vazio e

o conjunto que com todos os répteis que

está aqui mostrado com 11 chega e aí

depois enquanto a filha não esteja vazia

o que vai ser feito

continuamos aqui enquanto a filha não

seja macia a não ser o mínimo do

conjunto que o mínimo do conjunto que

nesse caso é aquele que tem a estimativa

melhor nesse caso o fcs

vamos colocar em tom e se esse evento

disse

vamos colocar no conjunto esse maiúscula

esse aqui

ok o próximo passo é então fazer um

relaxamento das arestas

o que vamos nos perguntar nesse passo

será que podemos melhorar o caminho mais

curto

att que são um dos grandes ideais de

acidentes a esse é encontrado até agora

pela passagem através desse sim a gente

tem estava infinita a nossa estimativa

passando por esse a gente tem um caminho

mais curto que o tamanho 10 certo

faremos o mesmo com o outro vértice que

a gente sente a ele que o y e aí

perguntava será que podemos melhorar o

caminho mais curto até este não

encontraram até agora pela passagem

desse sim

a minha estimativa é infinito e agora eu

tenho uma estimativa de 5 passando por

pelo ipc s

então vamos atualizar esses valores aqui

então temos agora que os valores foram

atualizados para 5 e 10 aqui também

vamos atualizar nossa tabela a nossa

estimativa mudou e agora o próximo passo

é original ou extrair um mínimo da da

filha que tem o valor mínimo da fila na

filha eu tenho te x y e c que tem um

valor mínimo é o y então vou extrair o y

e vou colocar ele no conjunto e se estou

colocando aqui no conjunto e se depois

vamos passar de novo passo de

relaxamento no passo do relaxamento a

gente vai verificar todos os dentes

adjacentes à distância definitiva mínima

até o efeito senão já sabemos que cinco

que agora vamos ver os recentes certo

então será que podemos melhorar o

caminho mais curto para quem são os

agentes então os recentes vão ctx ec x e

certo será que podemos melhorar o

caminho mais curto para ter encontrado

até agora pela passagem através da y

então vamos lá se passamos

por aqui será que podemos melhorar a

instância a att sim se a gente passa por

esse caminho aqui vamos a ter uma

distância menor que vai ser oito

o mesmo perguntamos para x será que

podemos melhorar o caminho mais curto

para a x encontrado até agora pela

passagem através de y se a gente vai por

aqui vamos ter uma distância de 5 mais

93 se que o mesmo será que podemos

melhorar o caminho mais curto atc sim

a minha estimativa é infinito

se passamos por isso não vou ter cinco

mais 271 então vamos atualizar todos

esses valores na tabela

então vou ter a minha estimativa att

mudou que em 2008 a tx mudou que 14 e

até segunda o q7 e assim continuamos e

agora vamos perguntar quem é o menor

elemento que está na nossa filha ok é

que termine estância menor estimativa

menor é um vai acontecer

colocámos em tom e vai acontecer no

conjunto é esse

ok e agora temos a distância definitiva

a gente já sabe que a distância mínima

até o fcc e 7 e aí continuamos com os

vizinhos ele para ver se podemos

melhorar o caminho mais curto

e aí nós perguntamos será que podemos

melhorar o caminho mais curto para a x

encontrado até agora pela passagem

através de z

então estamos aqui a gente está aqui ea

gente tenta usar tenta chegar em x

usando esse areia aqui será que o valor

melhorar a estimativa do x fica melhor

então temos sim passamos por aqui 17 + 6

3 6 3 e melhor de 14 é então vamos mudar

o valor dele foi mudado para 3 se o

próximo passo vamos tirar o elemento que

o elemento menor com esse motivo o menor

da fila que o vento e ct colocamos ele

no conjunto e se verificamos

já sabemos a verdade é que ela está a

ser definitivo a mínima até 2078

verificamos sujacente sair perguntando

será que podemos melhorar o caminho mais

curto para x encontrado até agora pela

passagem através de t

então se a gente olha aqui se os amuos

pensar esta é que é a chegar em x será

que a estimativa fica melhor fica

vai ficar 8 mais 19 e aqui há a

exigência não se machuca era 3 então

melhorarmos a nossa estimativa o que

agora é 9 finalmente o o o vértice único

vai dizer que está na fila eu x quem

ontem vizinhos não têm mais nada então

já sabemos que a estância definitivo a

miníma de 96 x 109 e então por fim

acabamos com esse evento e já sabemos

coloquei-a a nossa árvore está a mostrar

aqui então a a nossa água e responsa em

saber que já sabemos quais são as

distâncias mínimas de cada vez e na

verdade a partir do fcs até todos os 86

atingíveis a partir desse a distância

mínima de 100 a y e cinco de distância

mínima de si até e 8 dez efe a x-9 dse c

e 7 c e as arestas pelas quais temos que

passar para as para chegar nesse nosso

está marcado aí na árvore no vermelho

bom essa foi a nossa aula número 3 se

sobre o algoritmo de da estrada

principalmente espero que vocês tenham

gostado

[Música]

[Música]

[Música]

[Música]