ALGORÍTIMOS DE CAMINHAMENTOS

Prévia do material em texto

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 
 
 2 
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. 
 3 
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. 
As 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. 1: Grafo Original 
Fig. 2: Árvore Mínima 
de Suporte 
 4 
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; 
 
 
 5 
 
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. 
 
 
 
Fig. 3: Árvore Geradora 
do Grafo Original 
 6 
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. 
 7 
 
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]) porqueo 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 
 
2) 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 
 
 8 
3) 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 
 
4) Então, inclui-se x em PERM e a partir de x consulta-se os vértices adjacentes a ele 
que não estão em PERM, que no grafo G são u, v e y (Figura 4). Para todos os 
vértices adjacentes, que chamaremos z, calcula-se: 
 
 Se dist[z] > dist[x] + peso(x, z) 
 dist[z] = dist[x] + peso(x, z) 
 path[z] = x 
 Fim Se 
 
 
 
Fig. 7: Representação do Algoritmo de Dijkstra 
 
5) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor 
distância (Figura 5). Neste caso é o vértice y, pois dist[y] = 7. 
 9 
 
 
 
 
Fig. 8: Representação do Algoritmo de Dijkstra 
 
6) Inclui-se então y em PERM e a partir de y consulta-se os vértices adjacentes a ele 
que não estão em PERM, que no grafo G é apenas o vértice v (Figura 6). 
 
Se dist[v] > dist[y] + peso(y, v) 
 dist[v] = dist[y] + peso(y, v) 
 path[v] = y 
Fim Se 
 
 
 
Fig. 9: Representação do Algoritmo de Dijkstra 
 
7) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor 
distância (Figura 7). Neste caso é o vértice u, pois dist[u] = 8. 
 10 
 
 
Fig. 10: Representação do Algoritmo de Dijkstra 
 
8) Inclui-se então u em PERM e a partir de u consulta-se os vértices adjacentes a ele 
que não estão em PERM, que no grafo G é apenas o vértice v (Figura 8). 
 
 Se dist[v] > dist[u] + peso(u, v) 
 dist[v] = dist[u] + peso(u, v) 
 path[v] = u 
 Fim Se 
 
 
 
Fig. 11: Representação do Algoritmo de Dijkstra 
 
9) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor 
distância (Figura 9). Neste caso é o único vértice restante v e dist[v] = 9. 
 11 
 
 
Fig. 12: Representação do Algoritmo de Dijkstra 
 
10) Por fim faz-se v pertencer a PERM. Neste ponto, todos os vértices já estão em 
PERM e a busca é finalizada (Figura 13). 
 
 
 
Fig. 13: Representação do Algoritmo de Dijkstra 
 
3 ALGORITMO DE PRIM 
A característica principal do algoritmo de Kruskal é que ele seleciona a melhor 
arestas sem se preocupar da conexão com as arestas selecionadas antes. O resultado é uma 
proliferação de árvores que eventualmente se juntam para formar uma árvore. 
Já que sabemos que no final temos que produzir uma árvore só, por que não tentar 
fazer com que uma árvore cresça naturalmente até a obtenção da árvore geradora mínima? 
Assim, a próxima aresta selecionada seria sempre uma que se conecta à arvore que já 
existe. Isso é a idéia do algoritmo de Prim: 
 12 
No início o conjunto B contém um vértice arbitrário. A cada passo, o algoritmo 
considere todas as arestas que tocam B e seleciona a de menor peso. Depois, o algoritmo 
acrescenta em B o vértice ligada por essa aresta que não estava em B. O processo continua 
até que B contenha todos os vértices de G. 
3.1 Algoritmo 
função Prim(G = (N,A): grafo): conjunto de arestas 
T := {} 
B := Um vértice de G 
Enquanto B não contém todos os vértices 
(u,v) := aresta de menor peso tal que u V - B e v B 
T := T U {(u,v)} 
B := B U {u} 
Retornar T 
 
Para ilustrar, consideremos o grafo da figura 14, começando arbitrariamente pelo vértice a: 
 
Passo Aresta considerada Conjunto B 
Início - {a} 
1 (b,a) {a,b} 
2 (c,b) {a,b,c} 
3 (d,a) {a,b,c,d} 
4 (e,d) {a,b,c,d,e} 
5 (g,d) {a,b,c,d,e,g} 
6 (f,g) {a,b,c,d,e,f,g} 
 
 
 
 
 
 
 
Fig. 14: Grafo 
 13 
A figura a seguir ilustra a progressão na composição da árvore geradora: 
 
 
 
Para implementar eficientemente esse algoritmo, utiliza-se uma matriz de 
adjacência A[1..n, 1..n], onde cada elemento indica a distância entre dois vértices. Caso 
dois vértices não forem ligados por uma aresta o valor será . Para representar o conjunto 
B, podemos utilizar duas tabelas de n elementos, uma indicando para cada vértice o vértice 
de B que é mais perto, uma outra que dá a distância até o vértice de B que é mais perto. 
Fig. 15: Progressão na composição da 
árvore geradora. 
 14 
Seja mais_perto[1..n] e dist_mais_perto[1..n] essas duas tabelas, respectivamente. 
Para um vértice que já pertence a B, colocamos (-1) na entrada correspondente na tabela. 
3.2 Outro Algoritmo 
função Prim(L = [1..n, 1..n]: grafo): conjunto de arestas 
{Inicialmente consideramos que o vértice 1 é o único elemento de B} 
T := {} 
Para i := 2 até n: 
mais_perto[i] := 1 
dist_mais_perto[i] := L[i,1] 
Repetir n-1 vezes: 
min := 
Para j := 2 até n: 
Se 0 dist_mais_perto[j] < min então 
min := dist_mais_perto[j] 
k := j 
T := T U ((k,mais_perto[k])} 
dist_mais_perto[k] := -1 
Para j := 2 até n: 
Se L[k,j] < dist_mais_perto[j] então 
dist_mais_perto[j] := L[k,j] 
mais_perto[j] := k 
Retornar T 
Analisando esse algoritmo, conclui-se que ele tem um tempo de execução em 
O(n
2
). Qual é o melhor entre esse algoritmo e o algoritmo de Kruskal? Se o grafo tem 
muitas arestas, isto é, ele tem um número de arestas que se aproxima de n(n-1), o tempo de 
execução com o algoritmo de Kruskal é em O(n
2
 lg n), portanto pior que o algoritmo de 
Prim. Mas se o grafo é esparso, o número de arestas se aproxima de n. Nesse caso, o 
algoritmo de Kruskal está em O(n lg n) e é o melhor. Na verdade, existem outros 
algoritmos melhores no caso de grafo esparso. 
 
 
 15 
4 ALGORITMO DE BELLMAN-FORD 
 
O algoritmo de Bellman-Ford faz uso da mesma técnica utilizada pelo algoritmo 
de Dijkstra. Este algoritmo computa os caminhos mais curtos de um vértice inicial de 
origem a todos os demais, inclusive em grafos com pesos negativos. A única restrição é 
que o grafo não possua nenhum circuito de peso negativo. 
 
4.1 Algoritmo 
 
Entrada: (1) Grafo G com pesos nas arestas; (2) Vértice s de origem; (3) Matriz w de 
pesos das arestas; 
Saída: Caminho mais curto de s até todos os demais vértices de G 
 
para cada vértice v Є V f aça 
d[v] ∞ 
fim para 
d[s] 0 
para i 1 até |V | - 1 faça 
para cada aresta (u, v) Є E faça 
se d[v] > d[u] + w(u, v) então 
d[v] d[u] + w(u, v) 
fim se 
fim para 
fim para 
para cada aresta (u, v) Є E faça 
se d[v] > d[u] + w(u, v) então 
retorne FALSO 
fim se 
fim para 
retorne VERDADEIRO 
 
Como já foi dito, se existir um circuito negativo, não poderemos garantir que os 
caminhos encontrados nos grafos correspondem aos caminhos mais curtos. Ou seja, se 
existirem arestas (u, v) tais que w(u, v) + d[u] < d[v], o algoritmo retorna FALSO. Esse 
 16 
teste é realizado pelo passo 12 do algoritmo. A complexidade de tempo do algoritmo de 
Bellman-Ford é O(|E| |V|). Dessa forma, se você precisa resolver o problema dos 
caminhos mais curtos para um grafo com arestas com peso positivo, o algoritmode 
Dijkstra nos dá uma solução mais eficiente. Se todas as arestas do grafo possuem peso 
igual a 1, um algoritmo de busca em largura, que será discutido mais adiante, é o mais 
indicado. Por fim, para encontrar os caminhos mais curtos entre todos os vértices de um 
grafo com pesos nas arestas, vamos apresentar o algoritmo de Floyd-Warshall. 
 
5 ALGORITMO DE FLOYD-WARSHALL 
 
 
Se todas as arestas de G são não negativas, podemos usar o algoritmo de Dijkstra, o 
que nos dá um algoritmo de complexidade O(|V |
3
). Se o algoritmo contém arestas de peso 
negativo, mas sem circuitos de peso negativo, podemos usar o algoritmo de Bellman-Ford, 
que nos dá um algoritmo com complexidade de tempo O(|V |
2
|E|) ou O(|V |
4
), no caso de 
grafos densos. 
 
Para o algoritmo de Floyd-Warshall, vamos supor que temos uma matriz de pesos 
wn×n, tal que a posição w(i, j) da matriz de adjacências armazena o peso da aresta i j. 
 
Caso esta aresta não exista, w(i, j) = ∞. O algoritmo de Floyd-Warshall considera os 
vértices intermediários de um caminho mais curto P, ou seja, os vértices de P que não são 
os extremos e consiste de n iterações, onde n é o total de vértices do grafo. Na primeira 
iteração, trocamos a aresta i . j, para 1 = i, j = n, pelo caminho mais curto de i a j, exceto i 
e j, que passe somente pelo vértice 1. Esta operação é executada pela comparação entre 
w(i, 1) + w(1, j) e w(i, j) e selecionando o menor valor, onde w(i, j) = w0(i, j) corresponde 
ao peso da aresta i . j. O resultado desta comparação é chamado w1(i, j). Na segunda 
iteração, trocamos o caminho de i a j calculado durante a primeira iteração pelo caminho 
de menor peso de i a j que, desta vez, pode passar pelos vértices 1 e 2. Este caminho é 
determinado pela comparação entre w1(i, 2) + w1(2, j) e w1(i, j). O menor entre esses dois 
valores será w2(i, j). Durante a k-ésima iteração, computamos: 
 
wk(i, j) = min(wk-1(i, j), wk-1(i, k) + wk-1(k, j)) (2.1) 
 
para determinar o caminho mais curto entre i e j que passa somente pelos vértices 1, 2,..., k. 
 17 
O caminho mais curto entre cada par de vértices será encontrado após a n-ésima 
iteração. As posições w(k) ij em cada matriz indicam o peso de caminho mais curto de i a j 
que atravessa somente os vértices {1, 2, . . . , k}. Para simplificar, o grafo da figura não 
inclui os caminhos calculados a cada estágio dos algoritmos, mas estes não são difíceis de 
serem encontrados. 
 
5.1 Algoritmo 
 
Entrada: Matriz de adjacências An×n do grafo G, contendo os pesos das arestas 
Saída: Na matriz A, a distância entre todos os pares de vértices de G 
para k 1 até n faça 
para i 1 até n faça 
para j 1 até n faça 
w(i, j) min(w(i, j), w(i, k) + w(k, j)) 
fim para 
fim para 
fim para 
 
Ao final da execução, o algoritmo encontrará os caminhos mais curtos entre todos 
os pares de vértices do grafo de entrada. Este algoritmo possui complexidade de O(|V |
3
).