algoritmos em grafos

Prévia do material em texto

1
BCM0506: Comunicação e RedesBCM0506: Comunicação e Redes
Semana 3Semana 3
Algoritmos em GrafosAlgoritmos em Grafos
Santo André, fevereiro de 2017
Parte 1: Algoritmos de Busca
3
Rediscutindo: Representações Rediscutindo: Representações 
em Grafosem Grafos
Matriz de Adjacência
Matriz de Incidência 
Lista de Adjacência
4
Matriz de AdjacênciaMatriz de Adjacência
A matriz de adjacência de um grafo tem colunas e linhas indexadas pelos vértices
Se A for a matriz de adjacência de índices i e j, A(i,j) = 1 se os vértices i e j forem 
conectados por uma aresta, e A(i,j) = 0, caso contrário 
Em grafos não orientados a matriz de adjacência é sempre simétrica, i.e., A(i,j) = A(j,i)
5
Exemplo: Grafo Não Orientado Exemplo: Grafo Não Orientado 
e Matriz de Adjacênciae Matriz de Adjacência
Como este grafo é não orientado, a matriz de adjacência é simétrica, ou seja, A(i,j) = 
A(j,i)
6
Exemplo: Grafo Orientado e Exemplo: Grafo Orientado e 
Matriz de AdjacênciaMatriz de Adjacência
7
Matriz de IncidênciaMatriz de Incidência
A Matriz de Incidência representa 
computacionalmente um grafo em que as linhas 
representam os vértices, e as colunas, as arestas
Assim, dado um grafo com n vértices e m arestas, 
podemos representá-lo por uma matriz B n x m, 
guardando informações sobre a incidência de 
vértices em cada aresta 
Para representar um grafo sem pesos nas arestas e 
orientado, basta que as entradas da matriz B 
contenham +1 se a aresta chega no vértice, -1 se a 
aresta parte do vértice, e 0 caso a aresta não 
chegue nem parta no/do vértice
8
Exemplo: Matriz de Incidência Exemplo: Matriz de Incidência 
de Grafo Orientadode Grafo Orientado
9
Exemplo: Matriz de Incidência Exemplo: Matriz de Incidência 
de Grafo Não Orientadode Grafo Não Orientado
 e1 e2 e3 e4
 1 1 1 0 1
 1 0 0 0 2
B(i,j) = 0 1 0 1 3
 0 0 1 1 4
http://en.wikipedia.org/wiki/Incidence_matrix
Obs – Em caso de aresta na 
forma de laço (self-loop), 
podemos representá-la com o 
número “2” na respectiva 
posição “linha x coluna”
10
Lista de AdjacênciaLista de Adjacência
O vetor de listas de adjacência de um grafo tem uma lista encadeada para cada um de 
seus vértices
A lista de cada vértice v contém todos os vértices vizinhos que podem ser alcançados a 
partir de v
11
Exemplo: Lista de AdjacênciaExemplo: Lista de Adjacência
Adj[1] = {2}
Adj[2] = 
{1,3,5}
Adj[3] = {4}
Adj[4] = {1,5}
Adj[5] = {2}
Lista encadeada (Linked list)
12
Grafos PonderadosGrafos Ponderados
Um grafo pode ser ponderado ou não ponderado
 Se todas as arestas apresentarem um mesmo peso (ou custo), diz-se que o grafo é não 
ponderado, e todas as arestas são consideradas com custo igual a 1
O grafo será ponderado se diferentes arestas possuírem custos distintos 
13
Exemplo: Grafos Ponderados e Exemplo: Grafos Ponderados e 
Não PonderadosNão Ponderados
Pode-se ainda 
representar um grafo não 
ponderado ignorando os 
custos das arestas
Em um grafo não 
ponderado, todas as 
arestas possuem custo 
igual a 1
Em grafos ponderados, 
representa-se entre 
parênteses o custo da 
aresta
14
Caminhos em GrafosCaminhos em Grafos
Um  caminho  num grafo é uma sequência de 
vértices dotada da propriedade de que cada 
novo vértice é adjacente ao anterior
A origem de um caminho é o primeiro vértice do 
caminho, e o término é o último vértice
Diz-se que um caminho com origem s e 
término t vai de s a t (em inglês, s - source, e t - target)
Dizemos que uma aresta v w → pertence a um 
caminho se o vértice w é o sucessor de v no 
caminho
Todas as arestas de um caminho apontam no 
mesmo sentido, de um vértice para o seu 
sucessor
15
Caminhos em GrafosCaminhos em Grafos
Costuma-se diferenciar caminho de passeio 
em grafos
Em um caminho de s a t não pode haver nenhum 
vértice repetido, enquanto em um passeio isso 
pode acontecer
O  comprimento  de um caminho é o número de 
termos da sequência menos um
Em outras palavras, é o número de arestas do caminho 
Em grafos não orientados, a existência de 
caminhos é uma propriedade simétrica:  para 
quaisquer dois vértices s e t, existe caminho de 
s a t, se e somente se, existe caminho de t a s 
http://en.wikipedia.org/wiki/Path_(graph_theory)
16
Exemplo de CaminhoExemplo de Caminho
Para o exemplo a seguir (não orientado e não ponderado), o caminho 1 a 3 deve ser 
passando pelo vértice 2 (por escolha)
Caminho 1 a 3: 1 2 3→ →
Caminho 3 a 1: 3 2 1→ →
17
Exemplo de CaminhoExemplo de Caminho
Para grafos orientados (ponderados ou não) o caminho de s a t pode ser diferente do 
caminho de t a s
Exemplo:
Caminho 1 a 3: 
1 2 3→ →
Caminho 3 a 1: 
3 4 1→ →
18
Busca ou Travessia em GrafosBusca ou Travessia em Grafos
Um algoritmo de busca (ou varredura) é um 
algoritmo que examina, sistematicamente, todos 
os vértices e todas as arestas de um grafo 
Cada aresta é examinada uma só vez
Depois de visitar a ponta inicial de uma aresta, 
o algoritmo percorre a aresta e visita sua ponta 
final
Para justificar a palavra "busca", devemos 
imaginar que o algoritmo percorre o grafo 
buscando todos os vértices que são acessíveis a 
partir de um determinado vértice em questão, 
sem considerar especificamente seu objetivo até 
que o encontre
19
Busca ou Travessia em GrafosBusca ou Travessia em Grafos
Há muitas maneiras de fazer uma tal busca
Cada estratégia de busca é caracterizada pela ordem em que os vértices são visitados   
Assim, a ordem de visita torna-se essencial se desejamos determinar outras 
propriedades além da mera característica de um determinado vértice ser alcançado a 
partir de outro
20
Busca ou Travessia em GrafosBusca ou Travessia em Grafos
Os algoritmos de busca em grafos podem então nos mostrar outras características de 
grafos
Os algoritmos mais comumente discutidos são
busca em largura busca em profundidade
http://en.wikipedia.org/wiki/Depth-first_searchhttp://en.wikipedia.org/wiki/Breadth-first_search
21
Busca em LarguraBusca em Largura
No algoritmo de busca em largura, a lista de 
vértices obedece a política FIFO (First-In First-
Out, ou o primeiro a entrar será o primeiro a sair – 
Fila): o vértice que sai da lista é sempre o que está 
lá há mais tempo 
O algoritmo pinta de preto todos os vértices que 
podem ser alcançados a partir de um vértice de 
origem até alcançar o vértice de destino
A principal característica desse algoritmo é que a 
busca segue um modelo de parametrização pela 
distância a partir da origem
No exemplo a seguir, vamos supor que estejamos 
buscando o caminho entre 1 e 5
22
Exemplo: Busca em LarguraExemplo: Busca em Largura
No início todos os vértices são pintados de branco
Para o exemplo abaixo, o vértice de origem é o 1, 
sendo marcado com “largura” igual a zero
O algoritmo pinta de cinza este vértice e o coloca em 
uma fila Q, mapeando também seus vizinhos
Neste caso, ele se conecta apenas com o vértice 2 
Q = 1
Q – queue (fila, em inglês)
23
Exemplo: Busca em LarguraExemplo: Busca em Largura
No próximo passo, o vértice 1 é retirado da fila Q e 
pintado de preto, enquanto o vértice 2 é mapeado com 
“largura” igual a 1 e inserido na fila Q
O vértice 2 é então pintado de cinza e seus vizinhos 
são mapeados
No caso, os vértices 1, 3 e 5
Q = 2
24
Exemplo: Busca em LarguraExemplo: Busca em Largura
O vértice 2 é retirado da fila Q e pintado de preto, 
enquanto os vértices 3 e 5 são pintados de cinza, 
colocados na fila Q e mapeados com “largura” igual a 
2
O vértice 1 não é colocado na fila (apesar de haver 
uma conexão), pois já está pintado de preto
Q = 3, 5
25
Exemplo: Busca em LarguraExemplo: Busca em Largura
O vértice 3 é retirado da fila Q e pintado de preto, 
enquanto o vértice 4 é pintado de cinza, colocado na 
fila Q e mapeado com “largura” igual a 3
Q = 5, 4Obs – Quando um vértice é pintado de preto, isso 
significa que todos os seus 
nós adjacentes já foram 
“descobertos”,ou seja, não 
podem ter a cor branca
26
Exemplo: Busca em LarguraExemplo: Busca em Largura
Em seguida o vértice 5 também é visitado, pintado de 
preto e retirado da fila Q
Como sua única conexão é com o vértice 2 (já pintado 
de preto), nada é feito
Q = 4
27
Exemplo: Busca em LarguraExemplo: Busca em Largura
No término da execução deste exemplo, o vértice 4 é 
pintado de preto e retirado da fila Q
Como suas conexões levam a vértices já pintados de 
preto (1 e 5), nada é feito e a fila torna-se vazia 
(fim do algoritmo)
Q vazia
28
Exemplo: Busca em LarguraExemplo: Busca em Largura
Para o caminho entre origem e destino parte-se do 
vértice de destino, examinado seus predecessores até 
chegar à origem
Depois inverte-se o vetor conseguido
Para este exemplo, o caminho é 1 2 5→ →
A seguir é apresentado um pseudocódigo do algoritmo 
de busca em largura
Q vazia
29
Pseudocódigo: Busca em LarguraPseudocódigo: Busca em Largura
Busca_largura(Adj,origem,destino) // Adj é a lista de adjacência do grafo
t = tamanho de Adj;
para u = 1 até t,
 cor(u) = branco; //Todos os vértices são pintados de branco
fim
cor(origem) = cinza; //O vértice de origem é pintado de cinza
fila(1) = origem; i = 1; f = 2; //O vértice de origem é colocado na fila
enquanto i < f,
 u = fila(i); i = i + 1; c = Adj{u}; //O vértice mais antigo é retirado da fila
 se (c não é vazio), //Todos os vértices adjacentes de u serão
 para v = 1 até tamanho de c, //”descobertos” e pintados de cinza
 se cor(c(v)) == branco,
 cor(c(v)) = cinza;
 predecessor(c(v)) = u; //u passa a ser o “pai” de c(v)
 fila(f) = c(v); f = f + 1; //c(v) vai para o fim da fila(f)
 fim
 fim
 fim
 cor(u) = preto; // depois que todos os vértices adjacentes a
Fim // u foram examinados, u é pintado de preto
 
caminho(1) = destino; prev = predecessor(destino);
enquanto (prev != origem),
 caminho(tamanho do caminho + 1) = prev; destino = prev;
 prev = predecessor(destino);
fim
caminho(tamanho do caminho + 1) = prev; //Caminho na ordem inversa (decrescente)
para i = 1 até tamanho de caminho
 caminho2(i) = caminho(tamanho do caminho-i+1);
Fim //Caminho na ordem natural (crescente)
1
2
3 4 5 6 7
30
Exemplo: Simulação do Algoritmo de Busca em LarguraExemplo: Simulação do Algoritmo de Busca em Largura
Adj[1] = {2}
Adj[2] = 
{1,3,5}
Adj[3] = {4}
Adj[4] = 
{1,5}
Adj[5] = {2}
1 2
i f Q (fila) u c(v) Adj(u)
1 2 (1) - - -
3
i f Q (fila) u c(v) Adj(u)
1 2 (1) - - -
2 3 (2) (1) (2) (2)
i f Q (fila) u c(v) Adj(u)
1 2 (1) - - -
2 3 (2) (1) (2) (2)
3 4 (3) (2) (3) (3,5)
3 5 (3,5) (2) (5) (3,5)
4
i f Q (fila) u c(v) Adj(u)
1 2 (1) - - -
2 3 (2) (1) (2) (2)
3 4 (3) (2) (3) (3,5)
3 5 (3,5) (2) (5) (3,5)
4 6 (5,4) (3) (4) (4)5 6
i f Q (fila) u c(v) Adj(u)
1 2 (1) - - -
2 3 (2) (1) (2) (2)
3 4 (3) (2) (3) (3,5)
3 5 (3,5) (2) (5) (3,5)
4 6 (5,4) (3) (4) (4)
5 7 (4) (5) - -
7
i f Q (fila) u c(v) Adj(u)
1 2 (1) - - -
2 3 (2) (1) (2) (2)
3 4 (3) (2) (3) (3,5)
3 5 (3,5) (2) (5) (3,5)
4 6 (5,4) (3) (4) (4)
5 7 (4) (5) - -
6 8 - (4) - -
31
Busca em ProfundidadeBusca em Profundidade
A estratégia seguida pela busca em profundidade é, como seu nome implica, procurar cada 
vez mais fundo no grafo 
Nessa busca as arestas são exploradas a partir do vértice v mais recentemente 
descoberto que ainda possui arestas inexploradas saindo dele
Lógica LIFO (Last-In First-Out ou pilha)
Quando todas as arestas alcançadas a partir do vértice de origem são visitadas, a busca 
regressa para explorar as arestas que partem do vértice do qual v foi descoberto
Para o exemplo a seguir, tentaremos descobrir o 
caminho de 1 a 5
32
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
No início todos os vértices são brancos, mas 
partindo do vértice 1, este é pintado de cinza e 
sua aresta é examinada, levando ao vértice 2
O vértice 1 é marcado com distância 0
33
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
O vértice 1 é pintado de preto
O vértice 2 é pintado de cinza; enquanto suas arestas 
serão examinadas, é atribuída a ele a distância 1
A primeira aresta de 2 leva ao vértice 1, já pintado 
de preto
Partindo para a segunda aresta, esta leva ao vértice 3
34
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
O vértice 3 é então pintado de cinza e a ele é 
atribuída uma distância 2
Sua única aresta é examinada, levando ao vértice 4
35
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
O vértice 3 é pintado de preto e o vértice 4 é pintado 
de cinza, sendo que a ele é atribuída a distância 3
Suas arestas serão examinadas. A primeira leva a um 
nó já pintado de preto, logo não precisa ser analisada
A segunda, leva ao vértice 5
36
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
O vértice 4 é pintado de preto e o vértice 5 é pintado 
de cinza, sendo que a ele é atribuída a distância 4
Sua aresta é examinada, constatando-se que leva a 
um vértice já pintado de cinza
37
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
O vértice 5 é pintado de preto e parte-se para o 
exame da última aresta pertencente ao vértice 2
38
Exemplo: Busca em Exemplo: Busca em 
ProfundidadeProfundidade
Como neste momento esta aresta remete a um vértice já 
pintado de preto (vértice 5), o vértice 2 também é 
pintado de preto e o algoritmo é terminado
Diferentemente da busca em largura, este algoritmo 
produz um caminho 1 → 2 3 4 5 para o caminho → → →
de 1 a 5 
39
Busca em Profundidade:DetalhesBusca em Profundidade:Detalhes
O algoritmo de busca em profundidade na sua 
forma mais robusta utiliza um recurso 
computacional chamado recursão, em que uma 
dada função “chama a si mesma”
Um pseudocódigo para o algoritmo de busca em 
profundidade que encontra o caminho entre dois 
vértices é mostrado a seguir
Claramente há uma grande diferença no modo de 
implementação e nos resultados dos dois 
algoritmos
Desta forma, quando há a necessidade de 
obtenção do caminho mínimo entre dois vértices, 
outros algoritmos devem ser utilizados
40
Pseudocódigo: Busca em ProfundidadePseudocódigo: Busca em Profundidade
Busca_profundidade(Adj,origem,destino) //Adj é a lista de adjacência do grafo
t = tamanho de Adj;
para u = 1 até t,
 cor(u) = branco; //Todos os vértices são pintados de branco
fim
caminho(1) = origem;
c = busca_em_prof(Adj,origem,destino,caminho);
 
função busca_em_prof(Adj,u,d,caminho) //Retorna um caminho
cor(u) = cinza; //O vértice origem é pintado de cinza
v = Adj[u];
caminho2 = caminho;
se (v não é vazio),
 para i = 1 até tamanho(v), //O último vértice do caminho é testado para
 se (caminho(tamanho(caminho))) != d), //ver se é diferente do vértice destino
 se (v(i) == d),
 cor(v(i)) = preto;
 caminho = caminho2;
 caminho(tamanho(caminho2)+1) = d; 
 Salto; //O caminho final foi encontrado
 senão se (cor(v(i)) == branco),
 caminho = caminho2;
 caminho(tamanho(caminho2)+1) = v(i);
 c = busca_em_prof(Adj,v(i),d,caminho);
 caminho = c;
 fim
 fim
 fim
 cor(u) = preto;
fim
41
DistânciaDistância
Um caminho C num grafo é mínimo se não existe outro caminho 
com a mesma origem e o mesmo término que C, e com 
comprimento menor que o de C
A  distância  de um vértice s a um vértice t num grafo é o 
comprimento de um caminho mínimo de s a t
Se não existe caminho algum de s a t, a distância de s a t é infinita  
A distância de s a t é d se e somente se 
(1) existe um caminho de comprimento d de s a t  e  
(2) nenhum caminho de s a t tem comprimento menor que d 
Em geral, num grafo direcionado a distância de um vértice s a 
um vértice t é diferente da distância de t a s
Se o grafo é não orientado,entretanto, as duas distâncias são 
iguais
42
Grafos PonderadosGrafos Ponderados
Muitas aplicações associam um número a cada aresta 
de um grafo.  Diremos que esse número é o custo da 
aresta, que pode ser remetido a uma característica 
física da conexão
Por exemplo, se duas arestas de um grafo 
representam conexões de cabos óticos entre cidades 
A, B e C (vértices do grafo), sendo que a distância 
entre A e B é o dobro da distância de A a C, então 
pode-se atribuir um custo maior à aresta que liga os 
vértices A e B
Dependendo da aplicação, pode ser mais apropriado 
dizer  "peso" ou "comprimento" no lugar de "custo" 
43
Exemplo: Caminho de Custo Exemplo: Caminho de Custo 
MínimoMínimo
Se o grafo ponderado e direcionado abaixo for 
tomado como exemplo, o caminho mínimo C de 1 a 
5 tem custo d igual a 2, levando a um caminho 
1 2 5→ →
Perceba que existe um outro caminho 1 2 3 → →
 4 5, mas este possui custo → → d igual a 5
Parte 2: Algoritmos de 
Caminhos Mínimos
45
Busca de Caminhos MínimosBusca de Caminhos Mínimos
Para a busca de caminhos mínimos em grafos, há algoritmos especialmente desenvolvidos 
para executar essa tarefa
Entretanto há formas específicas para tratar o problema, sendo diferentes quando se 
buscam caminhos mínimos a partir de um dado vértice ou quando se buscam os caminhos 
mínimos entre todos os pares de vértices
46
Caminho Mínimo com Origem FixaCaminho Mínimo com Origem Fixa
Problema dos Caminhos Mínimos com Origem Fixa:
 Dado um vértice s de um grafo com custos nos 
arcos, encontrar, para cada vértice t que pode ser 
alcançado a partir de s, um caminho mínimo simples 
de s a t
Todos os algoritmos para esses problemas exploram 
a seguinte propriedade básica: 
 Propriedade Triangular:  Para quaisquer vértices x, 
y e z de um grafo com custos não negativos nos 
arcos, tem-se 
d(x,z)  ≤  d(x,y) + d(y,z) , sendo d(i,j) a distância de i a 
j 
x y
z
x x xy y y
z z
z
47
Algoritmo de DijkstraAlgoritmo de Dijkstra
Um algoritmo eficiente para a obtenção do 
caminho mínimo em grafos com custos não 
negativos é o chamado algoritmo de Dijkstra 
O algoritmo pode ser usado, em particular, 
para encontrar um caminho de custo mínimo 
de um dado vértice a outro, ou a todos os 
outros vértices
O algoritmo de Dijkstra funciona de forma 
iterativa, passo a passo, como mostrado a 
seguir
A entrada é a matriz de adjacência do grafo
48
Algoritmo de DijkstraAlgoritmo de Dijkstra
1. O primeiro passo é atribuir uma distância para todos os pares de 
vértices
1. De início é atribuída uma distância infinita para todos, menos para o vértice 
de origem, que recebe distância zero
2. Marque todos os vértices como não visitados e defina o vértice 
inicial como vértice atual
3. Para este vértice atual, considere todos os seus vértices vizinhos 
não visitados e calcule a distância a partir do vértice inicial
1. Se a distância for menor do que a definida anteriormente, substitua a distância 
4. Quando todos os vizinhos do vértice atual forem visitados, 
marque-o como visitado, o que fará com que ele não seja mais 
analisado (sua distância é mínima e final)
5. Eleja o vértice não visitado com a menor distância (a partir do 
vértice inicial) como o vértice atual e continue a partir do passo 3
49
Exemplo: Algoritmo de DijkstraExemplo: Algoritmo de Dijkstra
Para o exemplo a seguir, o vértice 1 é o vértice inicial e o vértice atual do início do 
algoritmo
A distância dele para todos os outros vértices é mostrada em vermelho
A distância para seu vizinho (vértice 2) é igual a 1
D = 1
D = ∞
D = ∞
D = ∞
D = 0
50
Exemplo: Algoritmo de DijkstraExemplo: Algoritmo de Dijkstra
O vértice 2 passa a ser o vértice atual
A partir dele, atingem-se os vértices 3 e 5, sendo as respectivas distâncias calculadas 
para 2 (ao invés de infinito) e 2
D = 1
D = 2
D = 2
D = ∞
D = 0
D = 1
51
Exemplo: Algoritmo de DijkstraExemplo: Algoritmo de Dijkstra
O vértice 3 é o vértice atual
A partir dele alcança-se o vértice 4, c/ distância 4
Em seguida, visita-se o vértice 5, mas sua distância não muda
Neste ponto todos os vértices foram visitados e o 
vetor de distâncias mínimas a partir do vértice 1 é 
D = [0 1 2 4 2]
D = 1
D = 2
D = 2
D = 4
D = 0
D = 2
52
Pseudocódigo: DijkstraPseudocódigo: Dijkstra
Dijkstra(grafo,origem)
para cada vértice v em grafo //Inicialização 
 distancia[v] = Infinito; //Cada vértice é inicializado 
com dist. infinita
 predecessor[v] = -1; //Guarda os vértices do 
caminho mínimo
fim
distancia[origem] = 0;
Q = todos os vértices de grafo; //Vértices nâo visitados ficam em Q
enquanto (Q não estiver vazio) faça, //Enquanto houver vértices nâo 
visitados 
 u = vértice do grafo com menor distância à origem;
 se (distancia[u] == Infinito)
 Salta o laço;
 fim
 remova u de Q;
 para cada vizinho v de u
 d = distancia[u] + distancia entre u e v;
 se (d < distancia[v]),
 distancia[v] = d;//Somente o menor caminho interessa 
 predecessor[v] = u;//Todos os vértices do caminho mínimo
 fim
 fim
 fim
fim
53
Algoritmo de Dijkstra: ExemploAlgoritmo de Dijkstra: Exemplo
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5
Algorithms for VLSI Design Automation, Sabih H. Gerez
Qual o caminho mínimo entre “1” e “2”?
54
D = 4
D = 3
D = 6
D = 2
Algoritmo de Dijkstra: SimulaçãoAlgoritmo de Dijkstra: Simulação
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5
Algorithms for VLSI Design Automation, Sabih H. Gerez
Qual o caminho mínimo entre “1” e “2”?
D = 6
D = 1
D = ∞
D = ∞
D = 3
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5
D = 6
D = 1
D = ∞
D = 6
D = 2
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5
D = 6
D = 1
D = 3
D = 6
D = 2
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5 D = 1
D = 4
D = 3
D = 5
D = 2
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5 D = 1
D = 4
D = 3
D = 5
D = 2
1
2
3
4
5
6
6
1
1
1
3
1
2
1
2
5 D = 1
1 2 3
4 5 6
D = 0 D = 0 D = 0
D = 0D = 0D = 0
55
Algoritmo de Dijkstra: Algoritmo de Dijkstra: 
Outro ExemploOutro Exemplo
1 
2
3 4
5
10
50
30
100
10
60
20
Data Structures and Algorithms, Aho, Hopcroft & Ullman
Qual o valor do caminho mínimo entre “1” e “2, 3, 4 e 5”?
Iteração S
Vértice 
Atual
D[2] D[3] D[4] D[5]
Origem {1} 1 10 ∞ 30 100
1 {1,2} 2 60 30 100
2 {1,2,4} 4 50 90
3 {1,2,4,3} 3 60
4 {1,2,4,3,5} 5 10 50 30 60
- Se durante a simulação o predecessor de cada nó 
for armazenado num vetor, então o caminho mínimo 
entre dois nós pode ser facilmente refeito 
- Assim, P[2] = 1, P[3] = 4, P[4] = 1 e P[5] = 3
Para refazer o caminho mínimo entre os nós 1 e 5, 
por ex., basta seguir os predecessores em ordem 
reversa: 1, 4, 3, 5
56
Caminhos mínimos entre todos Caminhos mínimos entre todos 
os pares de vérticesos pares de vértices
O Algoritmo de Floyd-Warshall é um algoritmo muito eficiente para encontrar todas as 
distâncias mínimas dos pares de caminhos em um grafo 
Em aplicações em que se faz necessária a criação de uma matriz de caminhos mínimos ao 
invés de um vetor, ou seja, ao invés de aplicar o algoritmo de Dijkstra para cada vértice 
considerado como origem, este algoritmo de Floyd-Warshall é mais aconselhável
57
Algoritmo de Floyd-WarshallAlgoritmo de Floyd-Warshall
O algoritmo de Floyd-Warshall deve primeiramente modificar a matriz de adjacência do 
grafo, de modo que todas as posições dos pares de vértices em que não houver 
conexões recebam como valor Infinito, exceto a diagonal principal (que deve manter os 
zeros)
Um pseudocódigo da implementação é mostrado a seguir, sendo a entrada do programa a 
própria matriz de adjacência
O programa retorna uma matriz com todos os pares de caminhos mínimos
58
Pseudocódigo: Algoritmo de Pseudocódigo: Algoritmo de 
Floyd-WarshallFloyd-Warshall
FloidWarshall(MatrizAdj)
para cada linha i em MatrizAdj
para cada coluna j em MatrizAdj
se (MatrizAdf[i][j] == 0 && i != j)
MatrizAdj[i][j] = Infinito;
fim
fim
fim
t = numero de linhas de MatrizAdj;
Cmin = MatrizAdj;
para k == 1 atét,
para i == 1 até t,
para j == 1 até t,
Cmin[i][j] = min(Cmin[i][j],Cmin[i][k]+Cmin[k]
[j]);
fim
fim
fim
retorna Cmin;
fim
59
Algoritmo de Floyd-WarshallAlgoritmo de Floyd-Warshall
k 
i j
C k-1
[i,k
]
C
k-1 [k,j]
Ck-1[i,j]
Data Structures and Algorithms, Aho, Hopcroft & Ullman
- O Algoritmo de Floyd-Warshall executa n iterações sobre a cópia da 
Matriz de Adjacência C[i,j]
-Ele explora o fato de que após k iterações sobre a cópia da Matriz 
Adjacente, o caminho mínimo entre os vértices i e j pode eventualmente ser 
um caminho com um vértice k intermediário
- Por isso, o algoritmo escolhe o custo mínimo na k-ésima iteração:
- Ckmin[i,k] = min(Ck-1min[i][j],Ck-1min[i][k]+Ck-1min[k][j])
- Esta fórmula é particularmente válida quando não há uma aresta entre i e j, 
e na respectiva posição da matriz de adjacência foi atribuído o valor infinito
60
Algoritmo de Floyd-WarshallAlgoritmo de Floyd-Warshall
2 
1 3
8 2
5
Data Structures and Algorithms, Aho, Hopcroft & Ullman
3
 1 2 3 
 0 8 5 1
C0(i,j) = 3 0 ∞ 2
 ∞ 2 0 3
 1 2 3 
 0 8 5 1
C1(i,j) = 3 0 8 2
 ∞ 2 0 3
 1 2 3 
 0 8 5 1
C2(i,j) = 3 0 8 2
 5 2 0 3
 1 2 3 
 0 7 5 1
C3(i,j) = 3 0 8 2
 5 2 0 3
C1(2,3) = min(C0(2,3), C0(2,1)+C0(1,3)) => k=1
C2(3,1) = min(C1(3,1), C1(3,2)+C1(2,1)) => k=2 C3(1,2) = min(C2(1,2), C2(1,3)+C2(3,2)) => k=3
61
Referências BibliográficasReferências Bibliográficas
T. H. Cormen, C. H. Leiserson, R. L. Rivest, C. Stein. ”Algoritmos: 
Teoria e Prática”, Editora Campus, 2002.
R. Sedgewick. “Algorithms in C”, Addison Wesley, 1990.
A. V. Aho, J. E. Hopcroft, J. D. Ullman. “Data Structures and 
Algorithms”, Addison-Wesley, 1987.
http://www.ime.usp.br/~pf/algoritmos_para_grafos/; acessado em 
30.09.12
http://www.ime.usp.br/~pf/analise_de_algoritmos/lectures.html ; 
acessado em 30.09.12
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ; acessado em 
30.09.12
http://www.algorithmist.com/index.php/Floyd-Warshall
%27s_Algorithm ; acessado em 30.09.12
62
Tarefa (parte 1)Tarefa (parte 1)
1.Um grafo não ponderado é representado pela lista de adjacências Adj = {[2]; 
[3]; [4,5,8]; []; [6,7]; [1]; [9]; [10]; [10]; []}. Represente graficamente este 
grafo e aplique o algoritmo de busca em largura e busca em profundidade para 
encontrar o caminho entre os vértices 1 e 10. 
2. Considere um grafo orientado e ponderado que seja representado pela matriz 
de adjacência abaixo. Simule o algoritmo de Dijkstra e determine o vetor de 
distâncias a partir do vértice 1. Faça gráficos para mostrar a evolução do 
algoritmo.
63
Tarefa (parte 2)Tarefa (parte 2)
3. Uma rede de informação possui uma topologia representada por um grafo cuja matriz de 
adjacências é dada a seguir.
Após um certo tempo de operação t o roteador representado pelo vértice 2 cai, deixando de 
existir as conexões que chegam e saem deste vértice. Passado um tempo t após a queda do 
vértice 2 o vértice 6 também cai e após 2t é a vez do vértice 12 sair de operação. 
Utilizando recursos computacionais, faça uma análise dos custos representados para o 
escoamento de informação devido à inoperabilidade destes roteadores e justifique suas 
afirmações por meio de gráficos e tabelas. Qual destas falhas representa a principal falha 
individual? Dica: analise as estatísticas para os caminhos mínimos globais em cada situação.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63