Algoritmos em grafos pesados

Nos últimos artigos dedicámo-nos a grafos simples, mas existem muitas variações ao conceito base de grafo. Alguns exemplos do que é possível incluem: grafos com múltiplas arestas entre nós; grafos com arestas de um nó para ele próprio; grafos com cores nos nós e/ou nas arestas; grafos com pesos nos nós e/ou nas arestas; qualquer combinação dos anteriores.

O foco deste artigo são grafos pesados, ou seja, grafos em que cada aresta tem um valor ou peso associado. O propósito deste peso é de representar vários casos importantes, por exemplo, distâncias entre nós. Como devem imaginar, este tipo de situações é muito frequente e por isso tem uma conjunto de algoritmos próprio, alguns dos quais iremos estudar neste artigo.

Iremos ver vários algoritmos para três classes de problemas, com vantagens e aplicações em situações diferentes. Opcionalmente, incluímos alguns tópicos extra por problema para consolidarem o que sabem e verem outras aplicações.

Distâncias de uma fonte única

O primeiro problema que iremos ver é o problema do caminho mais curto de fonte única. O objetivo é calcular o caminho mais curto que começa num dado nó, para todos os outros nós.

Iremos ver um conjunto de algoritmos que se aplicam a este problema e que têm restrições diferentes.

Algoritmo de Dijsktra

O primeiro algoritmo é dos algoritmos mais conhecidos de grafos. Chama-se algoritmo de Dijsktra e funciona da seguinte forma:

Algoritmo de Bellman-Ford

O segundo algoritmo é útil para ser aplicado a grafos em que nem todas as arestas têm pesos positivos, uma falha do algoritmo de DIjsktra. Veremos como funciona:

* Extras

Se quiserem saber um pouco mais sobre este tipo de coisa, um conceito muito interessante e que permite tirar muitas ideias sobre a estrutura dos caminhos mais curtos é o da "árvore de caminhos/distâncias mais curtas". Normalmente não é preciso calculá-lo explicitamente, pode-se usar apenas o que resulta da aplicação de um dos algoritmos acima. É um conceito um pouco mais avançado e é por isso que é opcional.

Distâncias de múltiplas fontes

Já vimos como calcular as distâncias a partir de um nó, mas outro conceito importante é calcular distâncias entre todos os pares de nós. Veremos um algoritmo que faz exatamente isso.

Algoritmo de Floyd-Warshall

Este algoritmo é o mais conhecido e o mais eficiente que se conhece para o problema geral de calcular o caminho mais curto entre todos os pares de vértices. Vejamos como funciona:

* Extras

Além do problema base a que se destina, o algoritmo de *Floyd-Warshall" é muito versátil e por isso aplica-se a algumas variações do problema de distâncias. Vejamos alguns exemplos:

Árvores de suporte de custo mínimo

O último problema que iremos ver é o determinar a árvore de suporte de custo mínimo de um grafo. Uma árvore de suporte de um grafo é um subgrafo que é uma árvore e que inclui todos os vértices do grafo original. Como o nome indica, a árvore de suporte de custo mínimo é a árvore de suporte cuja soma dos pesos das arestas é minimizada. Isto tem vários paralelos interessantes para situações práticas e é por isso útil em diferentes problemas, como iremos ver.

Algoritmo de Prim

O primeiro algoritmo que iremos ver é o algoritmo de Prim. Sem mais demoras aqui está ele:

Algoritmo de Kruskal

Finalmente vamos ver um algoritmo que é mais simples de implementar e que por isso é normalmente o mais usado em concursos de programação. Porém, necessita de uma estrutura de dados que apesar de simples não é trivial, nomeadamente o union-find. Esta estrutura será abordada noutro artigo, mas faremos-lhe uma breve introdução aqui também. Ai está, então, o algoritmo:

* Extras

Existem algumas variações interessantes do problema. É curioso como os algoritmos base que vimos se aplicam tão bem (ou seja, sem mudar quase nada) a vários desses problemas que à primeira vista não pareciam possuir o mesmo tipo de propriedade greedy. Vejamos alguns deles:

Aplicações

Para terminar bem, vamos a um problema para cada uma dos três problemas:

E mais dois extras, um para aplicar o Bellman-Ford e outro para juntar várias ideias de grafos:

Conclusão

Para consolidar todos os tópicos anteriores, aqui estão um conjunto de artigos extra que podem ser interessantes: