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