Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Prévia do material em texto

TEORIA DOS 
GRAFOS E ANÁLISE 
DE ALGORITMOS 
OBJETIVOS DE APRENDIZAGEM
 > Descrever o algoritmo de Dijkstra.
 > Explicar o algoritmo de Bellman-Ford.
 > Ilustrar o funcionamento e as aplicações dos algoritmos de Dijkstra e 
Bellman-Ford.
Introdução
Os algoritmos de custos de caminho mínimo oferecem soluções para encontrar 
o percurso de menor distância entre dois vértices s e t visando a cruzar um único 
caminho para chegar ao destino. Existe um problema intrínseco a essa aborda-
gem em relação à utilização de caminhos somente positivos, negativos e ciclos 
negativos. Esse problema é instruído em forma de grafos: o algoritmo de Dijkstra 
ataca o problema de encontrar uma árvore de caminhos baratos com raiz r no 
grafo de custos positivos em suas arestas e o de Bellman-Ford soluciona o mesmo 
problema, com o diferencial de atacar grafos com arestas de custos positivos ou 
negativos. Neste capítulo, vamos apresentar as diferenças conceituais de uma 
solução para outra, bem como o desenvolvimento de seus algoritmos e suas 
aplicações no mundo real. 
Algoritmos 
de Dijkstra e 
Bellman-Ford
Hygo Sousa de Oliveira
Algoritmo de Dijkstra
Em 1959, o cientista da computação holandês Edsger Wybe Dijkstra propôs 
um algoritmo de rotulação de vértices para encontrar os caminhos mais 
curtos de um vértice de origem para todos os demais vértices em grafos 
com custos positivos nas arestas (GOLDBARG; GOLDBARG, 2012). Em ou-
tras palavras, o problema de caminhos mínimos de fonte única consiste 
em encontrar o caminho mínimo de um dado vértice fonte (inicial) para 
todos os outros vértices. O algoritmo de Dijkstra resolve o problema 
de caminhos mínimos de fonte única em um grafo ponderado G = (V, 
E), onde V representa o conjunto de vértices e E indica o conjunto de 
arestas. Além disso, todos os pesos de arestas devem ser não negativos 
(CORMEN et al., 2012). 
O algoritmo de Dijkstra guarda um conjunto S de vértices com pesos 
finais de caminhos mínimos que partem de um, vértice fonte predefinido. 
Conforme Cormen et al. (2012), a ideia básica do algoritmo consiste em 
selecionar repetidamente um vértice u ∈ V – S que tenha a mínima esti-
mativa do caminho mínimo, adicionar o vértice u a S e relaxar todas as 
arestas que saem do vértice u. O relaxamento de aresta (u, v) consiste em 
testar se é possível melhorar caminho mínimo para um vértice v passando 
por um vértice u; caso seja possível melhorar o caminho mínimo, o valor 
de d[v] é atualizado, onde d[v] armazena o valor de estimativa do caminho 
mínimo entre os vértices do grafo. Na Figura 1, é ilustrado o processo de 
relaxamento de uma aresta, ou seja, a atualização dos pesos dos caminhos 
caso exista um melhor caminho.
Figura 1. Processo de relaxamento de uma aresta.
Fonte: Cormen et al. (2012, p. 531).
O processo de encontrar os caminhos mais curtos por meio do algoritmo 
de Dijkstra é ilustrado passo a passo na Figura 2. 
Algoritmos de Dijkstra e Bellman-Ford2
Figura 2. Algoritmo de Dijkstra.
Fonte: Cormen et al. (2012, p. 538).
Verificando o algoritmo da Figura 2, é possível observar, na linha 02, que 
os valores d[v] de estimativa de caminhos mínimos de todas as arestas são 
inicializados como ∞, e a linha 04 inicializa o conjunto S como o conjunto 
vazio. A linha 05 inicializa a fila de prioridades mínimas Q para conter todos 
os vértices em V, enquanto a linha 06 coloca a condição que, enquanto a fila 
de prioridades Q for diferente de vazio, serão executados os demais passos 
do algoritmo. Assim, a linha 07 realiza a extração do menor vértice u da fila 
de prioridade Q = V – S e a linha 08 o adiciona ao conjunto S. Por fim, o laço 
de repetição das linhas 09 a 11 realizam o processo de relaxamento.
O algoritmo de Dijkstra sempre escolhe o vértice “mais leve” ou “mais 
próximo” em V – S para adicionar ao conjunto S. Assim, podemos dizer 
que ele utiliza uma “estratégia gulosa” (CORMEN et al., 2012). 
Algoritmo de Bellman-Ford
O algoritmo de Bellman-Ford resolve o problema de caminho mínimo de fonte 
única encontrado no algoritmo de Dijkstra em que os pesos de arestas podem 
ser negativos (CORMEN et al., 2012). O problema em questão está relacionado 
a encontrar uma árvore de custo mínimo em um grafo G, com raiz ou início 
em s. O grafo G precisa ser um grafo dirigido, com fonte em um vértice s e 
função de peso w, de modo a atribuir peso às arestas E, onde o algoritmo 
Algoritmos de Dijkstra e Bellman-Ford 3
de Bellman-Ford devolve um valor verdade que indica se existe ou não um 
ciclo de peso negativo que pode ser alcançado a partir de sua fonte s. Caso o 
ciclo negativo exista, o algoritmo indica que não é possível encontrar solução 
alguma. Em contrapartida, não havendo qualquer ciclo negativo, o algoritmo 
produz os caminhos mínimos de G e seus pesos.
A Figura 3 apresenta o comportamento da proposta do algoritmo, dividida 
em três etapas: inicialização, relaxamento e checagem de ciclos negativos. A 
inicialização é responsável por padronizar as distâncias estabelecidas ao ciclo 
de resolução do problema. Já o papel do relaxamento é calcular o caminho 
mínimo, enquanto a verificação de ciclos rastreia a possibilidade de calcular 
um caminho mínimo sem que haja algum ciclo negativo. Haverá o cálculo do 
caminho mais curto caso não seja detectada a presença de ciclo negativo que 
possa ser alcançado da fonte, uma vez que o caminho pode passar infinitas 
vezes por esse ciclo, obtendo caminhos cada vez menores.
Figura 3. Algoritmo de BellIFord para caminhos mínimos com o início em uma fonte.
Fonte: Adaptada de Dasgupta, Papadimitriou e Vazirani (2009).
Os ciclos negativos impedem que seja encontrado um caminho mínimo. A 
Figura 4 aborda um grafo com as iterações na matriz ao lado. Caso o peso da 
aresta (E, B) fosse alterado para –4, o grafo passaria a ter um ciclo negativo 
na seguinte ordem: A -> E -> B -> A. Existe um caminho de comprimento 2 
dos vértices A até E. No entanto, ao percorrer o ciclo, existe um caminho de 
comprimento 1 e, percorrendo múltiplas vezes, é possível encontrar caminhos 
de comprimento 0, 1, 2 e assim por diante.
Algoritmos de Dijkstra e Bellman-Ford4
Figura 4. Exemplo do algoritmo de Bellman-Ford ilustrado em um grafo.
Fonte: Dasgupta, Papadimitriou e Vazirani (2009, p. 118).
A sequência de passos da Figura 5 apresenta o funcionamento do algoritmo 
de Bellman-Ford. Por meio desse exemplo, é possível acompanhar as etapas 
de inicialização e relaxamento junto com uma tabela final, que contém a 
distância calculada dos vértices em relação ao vértice do A de início do grafo.
Figura 5. (a) Passo a passo do algoritmo de Bellman-Ford em um grafo direcionado G e (b) 
tabela final com as distâncias calculadas dos vértices em relação ao vértice do A.
Fonte: Adaptada de Cormen et al. (2009).
Algoritmos de Dijkstra e Bellman-Ford 5
Aplicações dos algoritmos de Dijkstra 
e Bellman-Ford
Aplicação do algoritmo de Dijkstra
Considerando a propriedade do algoritmo de Dijkstra em encontrar o 
caminho mais próximo de um vértice fonte aos demais vértices de um 
grafo, podemos aplicar o algoritmo em um mapa de cidades para calcular 
a menor distância de uma cidade em relação às demais cidades do mapa. 
Considere um mapa que contém cinco cidades: s, t, x, y e z. Nesse exemplo, 
queremos saber qual é o caminho mínimo da cidade s para as demais 
cidades do mapa. 
Para calcular esses caminhos mínimos, vamos executar o algoritmo de 
Dijkstra. Veja, na Figura 6, o passo a passo do algoritmo. 
Figura 6. Execução do algoritmo de Dijkstra para calcular os caminhos mínimos.
Fonte: Adaptada de Cormen et al. (2012). 
Inicialmente, (a) os valores d[v] de estimativa de caminhos mínimos 
de todas as arestas são inicializados como ∞, e, (b) partindo da cidade 
inicial s, são verificadas as distâncias das cidades adjacentes, no caso, 
as cidades t e y. Após essa verificação, o vértice da cidade y é retirado da 
fila de prioridades, pois possui o menor caminho em relação à cidade t, 
Algoritmos de Dijkstra e Bellman-Ford6e, em seguida, ela é adicionada ao conjunto de cidades já processadas. 
Em (c), é realizado o mesmo processo, agora para verificar o caminho 
mínimo das cidades adjacentes à cidade y (exceto a cidade s, que já foi 
removida da fila prioridades). Nessa verificação, a cidade z é removida da 
fila de prioridades e adicionada ao conjunto S, de cidades processadas. 
Em (d), são realizados os mesmos passos de (b) e (c), enquanto, em (e), 
é realizado o processo de relaxamento, quando é atualizado o caminho 
mínimo entre a cidade s e a cidade x. Por fim, a cidade x é removida da 
fila de prioridades e adicionada ao conjunto S, de modo que o algoritmo 
de Dijkstra conseguiu calcular os caminhos mínimos da cidade s para as 
demais cidades do mapa.
Diversos problemas do mundo real podem ser resolvidos por meio 
do algoritmo de Dijkstra: percurso mais curto/rápido entre duas 
cidades, transmissão de dados em uma rede de computadores, reconhecimento 
de voz, segmentação de imagens, etc. Assim, por exemplo, o algoritmo de Dijkstra 
pode proporcionar economia de tempo e custos em viagens entre cidades, pois 
fornece as menores rotas partindo de uma cidade inicial para um conjunto de 
cidades, facilitando, inclusive, o processo de logística de várias empresas, como 
empresas de entregas.
Aplicação do algoritmo de Bellman-Ford
Uma das aplicações mais exploradas para o algoritmo de Bellman-Ford 
está relacionada ao problema de arbitragem triangular. No exemplo da 
Figura 7, de oportunidade arbitrária, apresentado por Sedgewick (2018) é 
dado o seguinte cenário. Considere um mercado para transações financei-
ras. A tabela em “rates.txt” mostra as taxas de conversão entre moedas. 
A primeira linha do arquivo é o número V de moedas, então o arquivo 
terá uma linha por moeda, fornecendo seu nome seguido pelas taxas 
de conversão para as outras moedas. Uma oportunidade de arbitragem 
é um ciclo direcionado em que o produto das taxas de câmbio é maior 
do que um. Por exemplo, nossa tabela diz que 1.000 dólares americanos 
comprarão 1.000,00 × 0,741 = 741 euros, então podemos comprar 741 × 1,366 
= 1.012,206 dólares canadenses com nossos euros e, finalmente, 1.012,206 
× 0,995 = 1.007,14497 dólares americanos com nossos dólares canadenses: 
um lucro de 7,14497 dólares.
Algoritmos de Dijkstra e Bellman-Ford 7
Figura 7. Uma oportunidade arbitrária.
Fonte: Sedgewick (2018, documento on-line).
Se trocarmos os pesos das arestas pelo seu respectivo log, verificaremos 
a existência de um ciclo negativo. Logo, o problema pode ser modelado 
pela busca de um ciclo negativo no grafo, e podemos utilizar o algoritmo de 
Bellman-Ford para resolver esse tipo de problema.
A busca por caminhos mínimos geralmente é realizada por métodos gulosos 
e de programação dinâmica, como os algoritmos de Dijkstra e Bellman-Ford, 
que vimos neste capítulo, os quais podem ser aplicados em uma variedade de 
casos. Sua aplicação mais comum é em cálculos de rotas realizados em GPS 
(sistema de posicionamento global) para encontrar as menores distâncias 
entre cidades e em redes de computadores, em que esses algoritmos podem 
ser utilizados para indicar as melhores rotas de tráfego de informação.
Referências
CORMEN, T. H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Porto Alegre: AMGH, 2009.
GOLDBARG, M.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. Rio de Janeiro: 
Elsevier, 2012.
SEDGEWICK, R.; WAYNE, K. Algorithms: shortest paths. 2018. Disponível em: https://
algs4.cs.princeton.edu/44sp/. Acesso em: 18 mar. 2021.
Leitura recomendada
DIJKSTRA, E. W. A note on two problems in connexion with graphs. Numerische Mathe-
matik, nº 1, p. 269–271, 1959.
Algoritmos de Dijkstra e Bellman-Ford8
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Algoritmos de Dijkstra e Bellman-Ford 9

Mais conteúdos dessa disciplina