BCC204 - Teoria dos Grafos
Marco Antonio M. Carvalho
(baseado nas notas de aula do prof. Haroldo Gambini Santos)
Departamento de Computação
Instituto de Ciências Exatas e Biológicas
Universidade Federal de Ouro Preto
4 de novembro de 2015
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
1 / 38
Avisos
Site da disciplina:
I
http://www.decom.ufop.br/marco/
Moodle:
I
www.decom.ufop.br/moodle
Lista de e-mails:
I
[email protected]
Para solicitar acesso:
I
http://groups.google.com/group/bcc204
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
2 / 38
Conteúdo
1
Introdução
2
Algoritmo de Dijkstra
3
Bellman-Ford
4
Floyd-Warshall
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
3 / 38
Introdução
Grafo Não Ponderado
O caminho mais curto entre os vértices v e w de um determinado grafo não
ponderado é aquele que possui o menor número de arestas entre os referidos
vértices.
Pode ser obtido pela aplicação da BFS.
Grafo Ponderado
O caminho mais curto entre os vértices v e w de um determinado grafo ponderado
é aquele cuja soma dos pesos das arestas possui o menor valor possível dentre
todos os caminhos existentes entre os referidos vértices.
Claramente, em grafos ponderados, o menor caminho pode não ser aquele com
menor número de arestas.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
4 / 38
Usando BFS em Grafos Ponderados
Complexidade
Em um grafo ponderado, se o peso das arestas for inteiro e limitado por um
número k, então a complexidade é limitada por O(km).
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
5 / 38
Algoritmo Guloso
Rápido e Rasteiro! – Quick and Dirty!
A cada instante, selecione a aresta de menor peso!
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
6 / 38
Algoritmo de Dijkstra
Princípio
O algoritmo rotula os vértices durante a exploração de um grafo (orientado ou
não), para encontrar o menor caminho entre um vértice de origem e todos os
demais vértices
I
I
Grafos ponderados somente com pesos positivos;
Estruturalmente semelhante à BFS
I
I
I
I
I
I
Calcula a menor distância do vértice inicial aos seus vizinhos;
Calcula a menor distância dos vizinhos do vértice inicial aos seus próprios
vizinhos;
E assim sucessivamente...
Noção de camadas;
Atualiza as distâncias sempre que descobre uma menor.
Pode ser provado por indução!
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
7 / 38
Algoritmo de Dijkstra
Terminologia
I
Um vértice é dito fechado caso o caminho mínimo da origem até ele já foi
calculado;
I
Caso contrário, o vértice é considerado aberto;
I
F : Conjunto de vértices fechados;
I
A: Conjunto de vértices abertos;
I
N: Conjunto de vértices vizinhos ao vértice atual;
I
dt[i]: Vetor que armazena a distância entre o vértice de origem e o vértice i;
I
rot[i]: Vetor que armazena o índice do vértice anterior ao vértice i, no
caminho cuja distância está armazenada em dt[i];
I
\: subtração em conjuntos.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
8 / 38
Algoritmo de Dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Entrada: Grafo G = (V , E ) e matriz de pesos D={dij } para todas as arestas {i, j}
dt[1] ← 0; //considerando o vértice 1 como o inicial
rot[1] ← 0;
para i ← 2 até n faça
dt[i] ← ∞;
rot[i] ← 0;
A ← V;
F ← ∅;
enquanto F 6= V faça
r ← j ∈ A, tal que dt[j] é o mínimo dentre os elementos de A;
F ← F ∪ {r };
A ← A \ {r };
N ← N \ F ; //conjunto de vizinhos do vértice r menos os vértices já fechados
para i ∈ N faça
p ← min{dt[i], (dt[r ]+dri )};
se p < dt[i] então
dt[i] ← p;
rot[i] ← r ;
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
9 / 38
Algoritmo de Dijkstra
Complexidade
I
O laço enquanto da linha 8 é repetido O(n) vezes;
I
Usando estruturas simples, examinar o conjunto A no pior caso pode exigir
O(n) comparações;
I
Caso o conjunto N seja grande, pode ser necessário atualizar O(n) vértices.
I
Logo, em uma implementação simples, a complexidade é O(n2 ).
Alternativa
Se utilizarmos um heap e listas de adjacências para representar o grafo, a
complexidade cai para O((n + m)logm), porque determinar o menor elemento e
atualizar o heap pode ser feito em tempo logarítmico.
Recorde
A melhor implementação do algoritmo, do ano 2000, possui complexidade O(nloglogm).
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
10 / 38
Dijkstra – Exemplo
Grafo G . O vértice inicial será ‘a’.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
11 / 38
Dijkstra – Exemplo
Rotulação após a primeira iteração do algoritmo.
O primeiro número é rot[i] e o segundo, dt[i].
Os vértices de F serão marcados em azul.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
12 / 38
Dijkstra – Exemplo
Exame do vértice a.
rot[b], dt[b], rot[c], dt[c], rot[d] e dt[d] atualizados.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
13 / 38
Dijkstra – Exemplo
Exame do vértice d.
rot[e], dt[e], rot[f ], dt[f ], rot[g ] e dt[g ] atualizados.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
14 / 38
Dijkstra – Exemplo
Exame do vértice c.
rot[e] e dt[e] não são atualizados.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
15 / 38
Dijkstra – Exemplo
Exame do vértice b.
rot[f ] e dt[f ] são atualizados.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
16 / 38
Dijkstra – Exemplo
Exame do vértice e.
Apenas rot[i] e dt[i] são atualizados.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
17 / 38
Dijkstra – Exemplo
Exame do vértice f .
rot[g ], dt[g ], rot[h] e dt[h] atualizados.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
18 / 38
Dijkstra – Exemplo
Exame do vértice g .
Apenas rot[j] e dt[j] são atualizados, pois os outros caminhos são mais curtos.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
19 / 38
Dijkstra – Exemplo
Exame do vértice h.
rot[j] e dt[j] são atualizados, pois o novo caminho é mais curto.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
20 / 38
Dijkstra – Exemplo
Exame do vértice j.
Nenhuma atualização.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
21 / 38
Dijkstra – Exemplo
Caminho mais curto entre a e j.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
22 / 38
Algoritmo de Dijkstra
Crítica
O algoritmo é incapaz de calcular os caminhos mínimos caso existam arestas com
custo negativo;
O algoritmo só calcula os caminhos mínimos a partir de uma única origem;
Para calcular os caminhos mínimos de todos os vértices para todos os vértices, o
algoritmo deve ser executado uma vez para cada vértice do grafo, com
complexidade total O(n3 ) na implementação simples.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
23 / 38
Dijkstra - Limitação
3
s
a
I
No algoritmo, qualquer caminho de s para outro vértice v
deve passar apenas por vértices mais próximos de s;
I
No exemplo, o caminho mais curto entre s e a passa por b,
que é mais distante do que a!
­2
4
b
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
24 / 38
Algoritmo de Bellman-Ford
Ford-Moore-Bellman?
Alguns autores denominam o algoritmo de Ford-Moore-Bellman, em homenagem
aos três autores que propuseram o mesmo algoritmo em anos diferentes:
I
Lester Ford (1956);
I
Edward Moore (1957);
I
Richard Bellman (1958).
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
25 / 38
Algoritmo de Bellman-Ford
Princípio
Ao invés de fechar um vértice por iteração, como o algoritmo de Dijkstra, examina
todos os vértices de um grafo orientado por iteração até que atualizações não
sejam possíveis;
Determina o menor caminho entre um vértice de origem e todos os demais vértices
do grafo;
Com esta estratégia, é possível calcular caminhos mínimos em grafos com arestas
de peso negativo;
“Um caminho de i para j com k+1 arestas pode ser obtido a partir de um caminho
de i para j com k arestas”.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
26 / 38
Algoritmo de Bellman-Ford
Terminologia
I
N: Conjunto de vértices antecessores do vértice atual;
I
dt[i]: Vetor que armazena a distância entre o vértice de origem e o vértice i;
I
rot[i]: Vetor que armazena o índice do vértice anterior ao vértice i, no
caminho cuja distância está armazenada em dt[i];
I
altera: variável booleana que indica se houve alguma atualização na iteração
atual;
I
Γ− (i): antecessores do vértice i.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
27 / 38
Algoritmo de Bellman-Ford
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Entrada: Grafo G = (V , E ) e matriz de pesos D={dij } para todas as arestas {i, j}
dt[1] ← 0; //considerando o vértice 1 como o inicial
rot[1] ← 0;
para i ← 2 até n faça
dt[i] ← d1i ;
se ∃ (1, i) ∈ E então rot[i] ← 1;
senão rot[i] ← 0; dt[i] ← ∞;
para k ← 1 até n-1 faça
altera ← falso;
para i ← 2 até n faça
N ← Γ− (i);
para j ∈ N faça
se dt[i] > dt[j]+dji então
dt[i] ← dt[j]+dji ;
rot[i] ← j;
altera ← verdadeiro; //indica que houve alteração
se altera = falso então k ← n; ;
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
28 / 38
Algoritmo de Bellman-Ford
Complexidade
I
Após a inicialização, o laço para da linha 7 é repetido por no máximo n-1
vezes;
I
Em cada iteração, são calculados caminhos com k arestas entre a origem e os
demais vértices do grafo;
I
Para cada um dos n-1 vértices, todos seus antecessores são examinados;
I
O vértice original não é atualizado, logo, n-2 antecessores são analisados no
máximo;
I
Logo, em uma implementação simples, a complexidade é O(n3 ).
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
29 / 38
Ciclos de Custo Negativo
Exemplo de ciclo negativo entre os vértices 4 e 5.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
30 / 38
Ciclos de Custo Negativo
Bellman-Ford – Detecção
I
Em caminhos sem ciclos, o caminho mais longo consiste em n − 1 arestas, ou
iterações no laço principal do algoritmo;
I
Se na iteração n do algoritmo alguma atualização de distâncias for feita é
detectado o ciclo.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
31 / 38
Algoritmo de Floyd-Warshall
Histórico
O algoritmo proposto por Floyd em 1962 é baseado no algoritmo de Warshall do
mesmo ano para cálculo de fechos transitivos em grafos.
Princípio
O algoritmo de Floyd-Warshall calcula o menor caminho entre todos os pares de
vértices de um grafo ponderado que eventualmente possua arestas com peso
negativo, mas que não possua ciclos de custo negativo;
O algoritmo compara os caminhos entre os vértices i e j passando por k vértices
intermediários, k = 1, . . ., n;
Uma matriz armazena o valor dos menores caminhos entre os vértices, mas não
informa a composição do caminho.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
32 / 38
Algoritmo de Floyd-Warshall
Terminologia
I
L: Matriz que armazena os menores caminhos entre os vértices;
I
I
I
Inicialmente, L é inicializada com os pesos das arestas do grafo (dij );
Caso não haja aresta entre dois vértices i e j, dij = ∞.
lij : elemento da matriz L na linha i e coluna j.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
33 / 38
Algoritmo de Floyd-Warshall
1
2
3
4
5
6
Entrada: Grafo G = (V , E ) e matriz de pesos D={dij } para todas as arestas {i, j}
L ← D;//Inicializa os elementos da matriz L
para k ← 1 até n faça
para i ← 1 até n faça
para j ← 1 até n faça
se lij > lik + lkj então
lij ← lik + lkj ;
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
34 / 38
Algoritmo de Floyd-Warshall
Alternativa
Outra forma de entender o algoritmo de Floyd-Warshall é usando uma relação de
recorrência;
Seja dist(i, j, k) o comprimento do caminho mais curto entre i e j tal que apenas
os vértices {1, . . . , k} podem ser usados como intermediários.
Relação de recorrência
dist(i, j, k) = min{dist(i, k, k − 1) + dist(k, j, k − 1), dist(i, j, k − 1)}
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
35 / 38
Algoritmo de Floyd-Warshall
Complexidade
Os três laços aninhados são executados n vezes, logo, a complexidade final é
O(n3 ), ou mais precisamente, Θ(n3 ).
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
36 / 38
Exercício
Execute algoritmo de Bellman-Ford para o grafo abaixo.
Execute algoritmo de Floyd-Warshall e construa a matriz L para o grafo abaixo.
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
37 / 38
Dúvidas?
Marco Antonio M. Carvalho (UFOP)
BCC204
4 de novembro de 2015
38 / 38