Algoritmos de Grafos: Kruskal, Dijkstra e A*

Algoritmo de Kruskal: O algoritmo de Prim constrói a MST (Minimum Spanning Tree) adicionando uma ligação de cada vez (a ligação parte entre os conjuntos resultados do corte do grafo). Enquanto que o método de Kruskal constrói a árvore ligação a ligação, mas fá-lo encontrando a ligação que une duas árvores numa floresta de MSTs.

O algoritmo inicia-se com uma floresta de V árvores (cada uma contendo unicamente um vértice) e com a ordenação das ligações por custo. É um método baseado nas ligações e é um algoritmo ganancioso (greedy).

Eficácia: Representando com uma matriz de adjacência:

• Com pesquisa baseada numa estrutura simples de dados: O(E log E).
• Com a utilização de filas de espera com prioridades: O(E + X log V), em que X é o número de ligações cujo custo é maior do que o maior custo de ligações da MST.

Grafos: Caminho mais curto (Grafos orientados e ponderados)

O caminho mais curto entre dois vértices, para o caso de redes (grafos orientados e ponderados), é o caminho orientado de s para t cujo peso (custo) não seja maior do que o custo de qualquer outro caminho de s para t.

O algoritmo de Dijkstra utiliza uma estratégia de menor custo (greedy) na visita dos diferentes vértices ao longo do processo. Este algoritmo funciona visitando vértices no grafo a partir de um ponto de partida. Examina rapidamente o vértice mais próximo (da origem) ainda não examinado, adicionando os seus vértices ao conjunto de vértices a serem examinados (expande-se a partir do ponto de partida até que atinga o objetivo).

Garante que encontra um caminho mais curto de um ponto de partida para um outro vértice, desde que nenhuma das ligações tenha custo negativo (podem existir uma ou mais soluções). O algoritmo de Dijkstra é correto, mas demasiado lento para algumas situações, pois ele explora todas as hipóteses.

Heurística é um método criado com o objetivo de encontrar soluções para um problema, sendo mais fácil encontrar respostas, ainda que imperfeitas. A utilização de heurísticas em algoritmos de caminho mais curto permite diminuir o número de vértices analisados em cada interação e, deste modo, tornar o processo mais rápido.

• No caso do algoritmo Greedy Best-First Search: utiliza a distância em linha reta para o objetivo. Deste modo, vamos escolher o vértice que parece estar mais perto do objetivo. Não garante que encontre o caminho mais curto, mas é rápido e aproximado.
• No caso do algoritmo A* Search: é o melhor e mais rápido a calcular. Não é tão lento como o Dijkstra, mas encontra o melhor caminho.