Algoritmos de Caminhamento

Algoritmos de Caminhamento

(Parte 1 de 3)

SUMÁRIO

INTRODUÇÃO 2

1 ALGORITMO DE KRUSKAL 3

1.1 Árvore Mínima de Suporte (MST) 3

1.2 Utilizando o MST 4

1.3 Problema da Árvore de Ligações Mínimas 4

1.4 Algoritmo 5

1.5 Melhorias no Algoritmo 6

2 ALGORITMO DE DIJKSTRA 6

2.1 Funcionamento do Algoritmo 6

3 ALGORITMO DE PRIM 11

3.1 Algoritmo 12

3.2 Outro Algoritmo 14

4 ALGORITMO DE BELLMAN-FORD 15

4.1 Algoritmo 15

5 ALGORITMO DE FLOYD-WARSHALL 16

5.1 Algoritmo 17

CONCLUSÃO 18

REFERÊNCIAS BIBLIOGRÁFICAS 19

INTRODUÇÃO

Este trabalho tem como objetivo apresentar os Algoritmos de Caminhamento, descrevendo suas características e particularidades, discutindo os processos que os englobam, mostrar com representações gráficas o seu funcionamento e estudar os códigos.

1 ALGORÍTMO DE KRUSKAL

Este algoritmo utiliza três conjuntos e, t e vs. T é usado para guardar as arestas da árvore expandida. O algoritmo trabalha transformando uma floresta expandida de g em uma única árvore. O conjunto vs contém os conjuntos das árvores da floresta expandida. Inicialmente vs contém todos os vértices de g, onde cada vértice é um conjunto unitário.

A

Fig. 1: Grafo Original

s arestas são escolhidas por ordem crescente de custo. Quando uma aresta une duas sub-árvores da floresta expandida, estas são unidas em vs, quando não, ela é descartada, pois forma ciclo.

1.1 Árvore Mínima de Suporte (Mst)

Mst (minimum spannig tree) ou msct - árvore geradora de peso mínimo (minimum cost spanning tree) - uma árvore mínima de suporte (mst) de um grafo ponderado é o conjunto de arestas ligando todos os vértices, tais que a soma dos pesos das arestas é, pelo menos, tão baixa quanto a soma dos pesos de qualquer outro conjunto de arestas ligando todos os vértices.

Exemplo:

Fig. 2: Árvore Mínima de Suporte

1.2 Utilizando o Mst

Dado um grafo conexo não orientado g, com peso positivo nas arestas (e à r+), encontrar uma árvore geradora de g de peso mínimo. Para resolver este problema acima o algoritmo de Kruskal é uma das opções, temos outras opções como o Prim e o Boruvka.

O algoritmo de Kruskal é guloso. Como o nome sugere, estratégia usada por esse algoritmo consiste na escolha da melhor solução em determinados instantes. Isto é, ele faz uma escolha ótima localmente esperando que esta escolha leve a uma solução ótima global. Por vezes conduz a uma solução ótima, mas nem sempre isso ocorre.

1.3 Problema da Árvore de Ligações Mínimas

- Descrição do Problema:

encontrar a árvore de comprimento total mínimo sobre uma rede orientada ou não de distância, tempos, etc.

- Algorítmos de Kruskal:

.construir uma lista das arestas da rede e ordená-las por ordem crescente de distâncias.

.começar por escolher a 1ª aresta da lista;

.repetir 2 até todos os vértices fazerem parte da árvore identificada;

.a árvore de ligações mínimas é constituídas pelas arestas escolhidas e tem comprimento total igual a soma dos comprimentos das arestas;

- Casos Especiais:

- se, no ponto 3, temos arcos alternativos com igual comprimento e ao escolher ambos formam-se ciclos, então existem soluções degeneradas;

- se existirem n conjunto de m arcos nas condições anteriores então existirão mxn soluções

ótimas;

Fig. 3: Árvore Geradora

do Grafo Original

1.4 Algoritmo

Função Kruskal (G=(V,E): grafo; Comprimento: E->R): conjunto de arestas

{inicialização}

Ordenar E por ordem crescente do comprimento

N |V|

T Ǿ {arestas da árvore geradora mínima}

Inicializar n conjuntos, cada um com nó de V

{laço guloso}

repita

e {u,v}// a menor aresta não considerada

ucomp achar(u)

vcomp achar(v)

se ucomp ≠ vcomp então

juntar (ucomp,vcomp)

T T U {e}

até |T| = n-1

retornar T

A complexidade do algoritmo pode ser analisada:

- Ordenação das arestas;

- Inicialização dos conjuntos disjuntos;

- Gasto para achar as arestas;

- Gasto para junção.

1.5 Melhoras no Algoritmo

Pode-se colocar uma busca e ordenação mais eficientes, nas buscas de união pode-se utilizar “halving”, “mergesort” é outra dica para se utilizar na ordenação.

2 ALGORITMO DE DIJKSTRA

O algoritmo de Dijkstra é o mais famoso dos algoritmos para cálculo de caminho de custo mínimo entre vértices de um grafo e, na prática, o mais empregado.

Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. O algoritmo pode ser usado sobre grafos orientados (dígrafos), ou não, e admite que todas as arestas possuem pesos não negativos (nulo é possível). Esta restrição é perfeitamente possível no contexto de redes de transportes, onde as arestas representam normalmente distâncias ou tempos médios de percurso; poderão existir, no entanto, aplicações onde as arestas apresentam pesos negativos, nestes casos o algoritmo não funcionará corretamente.

2.1 Funcionamento do Algoritmo

Assumiremos um conjunto, Chama-lo-emos PERM, que contém inicialmente apenas o vértice fonte (raiz da busca) s. A qualquer momento PERM contém todos os vértices para os quais já foram determinados os menores caminhos usando apenas vértices em PERM a partir de s. Para cada vértice z fora de PERM matemos a menor distância dist[z] de s a z usando caminhos onde o único vértice que não está em PERM seja z. É necesssário também armazenar o vértice adjacente (precedente) a z neste caminho em path[z].

Como fazer com que PERM cresça, ou seja, qual vértice deve ser incluído em PERM a seguir? Tomamos o vértice, entre todos os que ainda não pertencem a PERM, com menor distância dist. Acrescentamos então este vértice chamemo-lo de current, a PERM, e recalculamos as distâncias (dist) para todos os vértices adjacentes a ele que não estejam em PERM, pois pode haver um caminho menor a partir de s, passando por current, do que aquele que havia antes de current ser agregado a PERM. Se houver um caminho mais curto precisamos também atualizar path[z] de forma a indicar que current é o vértice adjacente a z pelo novo caminho mínimo.

Vejamos o funcionamento do algoritmo sob uma outra representação:

  1. Defini-se inicialmente o nó de origem (raiz), neste caso s, e inclui-se este nó em PERM (Figura 1). Atribui-se zero a sua distância (dist[s]) porque o custo de ir de s a s é obviamente 0. Todos os outros nós i tem suas distâncias (dist[i]) inicializadas com um valor bastante grande ("infinito").

Fig. 4: Representação do Algoritmo de Dijkstra

  1. A partir de s consulta-se os vértices adjacentes a ele, que no grafo G são u e x (Figura 2). Para todos os vértices adjacentes, que chamaremos z, calcula-se:

Se dist[z] > dist[s] + peso(s, z)

   dist[z] = dist[s] + peso(s, z)

   path[z] = s

Fim Se

Fig. 5: Representação do Algoritmo de Dijkstra

  1. Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância (Figura 3). Neste caso é o vértice x, pois dist[x] = 5.

Fig. 6: Representação do Algoritmo de Dijkstra

(Parte 1 de 3)

Comentários