Teoria dos Grafos
Algoritmos
em Grafos
– p. 1/39
Algoritmos em Grafos
Como representar computacionalmente um grafo?
– p. 2/39
Algoritmos em Grafos
Como representar computacionalmente um grafo?
e1
v1 v2
e2
e5 e7 e3
e6
v4 e4 v3
– p. 2/39
Algoritmos em Grafos
Como representar computacionalmente um grafo?
e1 e2 e3 e4 e5 e6 e7
e1 v1 1 1 0 0 1 0 1
v1 v2
e2 v2 1 1 1 0 0 0 0
e5 e7 e3 v3 0 0 1 1 0 0 1
e6
v4 0 0 0 1 1 2 0
v4 e4 v3
Matriz de incidência
– p. 2/39
Algoritmos em Grafos
Como representar computacionalmente um grafo?
e1
v1 v2
e2
e5 e7 e3
e6
v4 e4 v3
– p. 3/39
Algoritmos em Grafos
Como representar computacionalmente um grafo?
v1 v2 v3 v4
e1 v1 0 2 1 1
v1 v2
e2 v2 2 0 1 0
e5 e7 e3 v3 1 1 0 1
e6
v4 1 0 1 1
v4 e4 v3
Matriz de adjacência
– p. 3/39
Algoritmos de busca em Grafos
Muitas problemas algorítmicos consiste na
exploração de um grafo. Logo, é importante obter
um processo sistemático de como “caminhar”
pelas arestas e vértices de um grafo.
Vamos descrever dois algoritmos de busca em
grafos:
busca em largura
busca em profundidade
– p. 4/39
Busca em largura
– p. 5/39
Busca em largura
1. põe na fila um vértice qualquer u de G e
marque-o como alcançado
– p. 5/39
Busca em largura
1. põe na fila um vértice qualquer u de G e
marque-o como alcançado
2. enquanto fila = ∅ faça
v ← elemento da frente da fila (retire v da fila)
para toda aresta (v, w), tal que w ainda não
foi alcançado, marque w como alcançado e
põe w na fila
– p. 5/39
Busca em profundidade
– p. 6/39
Busca em profundidade
1. empilhe um vértice qualquer u de G e marque-o
como alcançado
– p. 6/39
Busca em profundidade
1. empilhe um vértice qualquer u de G e marque-o
como alcançado
2. enquanto pilha = ∅ faça
v ← elemento do topo-da-pilha
se existe aresta (v, w), tal que w ainda não
foi alcançado, então marque w como
alcançado e empilhe w; senão desempilha v
– p. 6/39
Exercícios
1. Descreva, algoritmos para responder as
seguintes perguntas, dado um grafo G:
G é conexo?
G tem circuito?
G é bipartido?
G é biconexo?
– p. 7/39
Para implementar
http://br.spoj.com/problems/PEDAGIO
– p. 8/39
Algoritmos em grafos
O problema do camínho mínimo
– p. 9/39
O problema do caminho mínimo
Seja G um grafo simples tal que a cada aresta e
associamos um custo c(e) ≥ 0. O problema do
caminho mínimo consiste em encontar um
caminho de menor custo entre dois vértices dados,
digamos u e v.
– p. 10/39
O problema do caminho mínimo
1 2
2 6 5 9 7 9
3
8 1 6 2
u v
1 2 3
4 1
7 4
9 1
– p. 11/39
O problema do caminho mínimo
Para resolver este problema, vamos estudar o
algoritmo de Dijkstra (1959). Como veremos, este
algoritmo não só encontra o caminho mínimo de u
a v, mas de u a qualquer outro vértice do grafo.
– p. 12/39
O problema do caminho mínimo
Para resolver este problema, vamos estudar o
algoritmo de Dijkstra (1959). Como veremos, este
algoritmo não só encontra o caminho mínimo de u
a v, mas de u a qualquer outro vértice do grafo.
O algoritmo de Dijkstra pode ser visto como uma
generalização da busca em largura.
Vamos assumir que c(x, y) = ∞ se (x, y) ∈
/ E(G).
– p. 12/39
Algoritmo de Dijkstra
1. d(u) ← 0; S ← {u};
2. Para cada v ∈ (V (G) − {u}) faça d(v) ← c(u, v);
– p. 13/39
Algoritmo de Dijkstra
1. d(u) ← 0; S ← {u};
2. Para cada v ∈ (V (G) − {u}) faça d(v) ← c(u, v);
3. Enquanto S = V (G) faça
“escolha v ∈ V (G) − S tal que d(v) seja
mínimo”;
S ← S ∪ {v};
Para cada w ∈ V (G) − S faça
d(w) ← min{d(w), d(v) + c(v, w)};
– p. 13/39
Corretude do algoritmo de Dijkstra
Teorema:O algoritmo de Dijkstra determina
corretamente as distâncias de u a cada vértice de
V (G).
– p. 14/39
Corretude do algoritmo de Dijkstra
Teorema:O algoritmo de Dijkstra determina
corretamente as distâncias de u a cada vértice de
V (G).
Prova: Suponha o contrário, ou seja, que existe um
vértice v tal que o valor d(v) calculado pelo
algoritmo não é a distância mínima de u a v.
Consideremos o primeiro vértice v nessa condição
durante a execução do algoritmo (ou seja, a
primeira vez que o algoritmo erra).
– p. 14/39
Corretude do algoritmo de Dijkstra
Então a distância de u a v é menor do que d(v), e
para todo vértice w ∈ S a distância de u a w está
correta, ou seja, é d(w).
– p. 15/39
Corretude do algoritmo de Dijkstra
Considere um caminho P de u a v cujo custo é
menor do que d(v). Então P contém um vértice
interno w fora de S (senão o algoritmo teria
escolhido P ). Logo, a distância de u a w é menor
do que a distância de u a v, pois os custos são
todos não negativos. Mas isto contradiz a escolha
de v pelo algoritmo (w deveria ter sido escolhido
nesta iteração). Portanto, o algoritmo está correto.
– p. 16/39
Exercícios
1. Determine um caminho mínimo entre os vértices u e v .
1 2
2 6 5 9 7 9
3
8 1 6 2
u v
1 2 3
4 1
7 4
9 1
– p. 17/39
Exercícios
2. Determine um caminho mínimo entre os vértices u e v .
5 5
3 4 5 5
1
9 2 9
u v
2 1 6
6 3
9 2
– p. 18/39
Exercícios
3. Determine um caminho mínimo entre os vértices u e v .
2
2
1 6 8
4 1 6 5
5 5 2
6 9 3
u 4 2 v
1 4
3
8
8 7
7
10
– p. 19/39
Exercícios
4. Qual o tempo gasto pelo algoritmo de Dijkstra?
5. O algoritmo de Dijkstra funciona corretamente
se as arestas tiverem pesos negativos?
– p. 20/39
Para implementar
https://www.spoj.com/problems/SAMER08A/
– p. 21/39
Algoritmo de Bellman-Ford-Moore
Seja D = (V, A) um grafo dirigido, possivelmente
com custos negativos nas arestas, mas sem
circuitos negativos, e seja u um vértice de D. O
algoritmo de Bellman-Ford-Moore (1956, 1958)
determina a distância de u aos demais vértices de
D.
– p. 22/39
Algoritmo de Bellman-Ford-Moore
Seja D = (V, A) um grafo dirigido, possivelmente
com custos negativos nas arestas, mas sem
circuitos negativos, e seja u um vértice de D. O
algoritmo de Bellman-Ford-Moore (1956, 1958)
determina a distância de u aos demais vértices de
D.
Para cada vértice v mantemos uma distância
tentativa d(v) de u até v. No início d(u) = 0 e
d(v) = ∞ para os demais vértices de D.
– p. 22/39
Algoritmo de Bellman-Ford-Moore
O algoritmo de Bellman-Ford-Moore pode ser
resumido no seguinte laço iterativo:
Enquanto existir arco (v, w) tal que
d(v) + c(v, w) < d(w) faça
d(w) = d(v) + c(v, w)
– p. 23/39
Algoritmo de Bellman-Ford-Moore
5
∞
6 −2 ∞
−4
−3 7
2
u 0
8 ∞
7
9
∞
– p. 24/39
Algoritmo de Bellman-Ford-Moore
5
6
6 −2 ∞
−4
−3 7
2
u 0
8 ∞
7
9
7
– p. 24/39
Algoritmo de Bellman-Ford-Moore
5
6
6 −2 4
−4
−3 7
2
u 0
8 2
7
9
7
– p. 24/39
Algoritmo de Bellman-Ford-Moore
5
2
6 −2 4
−4
−3 7
2
u 0
8 2
7
9
7
– p. 24/39
Algoritmo de Bellman-Ford-Moore
5
2
6 −2 4
−4
−3 7
2
u 0
8 −2
7
9
7
– p. 24/39
Algoritmo de Bellman-Ford-Moore
1. Para cada v ∈ V (G) faça d(v) ← ∞;
2. d(u) ← 0;
– p. 25/39
Algoritmo de Bellman-Ford-Moore
1. Para cada v ∈ V (G) faça d(v) ← ∞;
2. d(u) ← 0;
3. Para i = 1 até |V (G)| − 1 faça
Para cada arco (v, w) ∈ E(G) faça
Se d(w) > d(v) + c(v, w) então
d(w) ← d(v) + c(v, w)
– p. 25/39
Algoritmo de Bellman-Ford-Moore
1. Para cada v ∈ V (G) faça d(v) ← ∞;
2. d(u) ← 0;
3. Para i = 1 até |V (G)| − 1 faça
Para cada arco (v, w) ∈ E(G) faça
Se d(w) > d(v) + c(v, w) então
d(w) ← d(v) + c(v, w)
4. Para cada arco (v, w) ∈ E(G) faça
Se d(w) > d(v) + c(v, w) então
retorne(“impossível”)
– p. 25/39
Exercícios
1. Qual o tempo gasto pelo algoritmo de
Bellman-Ford-Moore?
– p. 26/39
Algoritmos em grafos
Camínho mínimo entre
todos os pares de vértices
Algoritmo de Floyd – Warshall
– p. 27/39
Algoritmo de Floyd – Warshall
Seja D = (V, A) um grafo dirigido, possivelmente
com custos negativos nas arestas, mas sem
circuitos negativos. O algoritmo de Floyd –
Warshall (1959, 1962) determina a distância entre
cada par de vértices de D.
– p. 28/39
Algoritmo de Floyd – Warshall
Seja D = (V, A) um grafo dirigido, possivelmente
com custos negativos nas arestas, mas sem
circuitos negativos. O algoritmo de Floyd –
Warshall (1959, 1962) determina a distância entre
cada par de vértices de D.
O algoritmo mantém uma distância parcial para
cada par de vértices u e v, e vai melhorando este
valor até que o valor correto seja encontrado.
– p. 28/39
Algoritmo de Floyd – Warshall
O algoritmo de Floyd – Warshall é um exemplo de
programação dinâmica.
– p. 29/39
Algoritmo de Floyd – Warshall
O algoritmo de Floyd – Warshall é um exemplo de
programação dinâmica. Suponha que os vértices
de D estejam numerados de 1 a n.
– p. 29/39
Algoritmo de Floyd – Warshall
Para cada par de vértices i e j, e um inteiro k, um
caminho mínimo entre i e j que utiliza somente
vértices internos do conjunto {1, 2, . . . , k} pode ser:
– p. 30/39
Algoritmo de Floyd – Warshall
Para cada par de vértices i e j, e um inteiro k, um
caminho mínimo entre i e j que utiliza somente
vértices internos do conjunto {1, 2, . . . , k} pode ser:
um caminho que utiliza somente vértices
internos do conjunto {1, 2, . . . , k − 1}; ou
um caminho de i a k concatenado a um
caminho de k a j, ambos utilizando somente
vértices internos do conjunto {1, 2, . . . , k − 1}.
– p. 30/39
Algoritmo de Floyd – Warshall
Seja f (i, j, k) a distância entre os vértices i e j
utilizando somente vértices internos do conjunto
{1, 2, . . . , k}.
– p. 31/39
Algoritmo de Floyd – Warshall
Seja f (i, j, k) a distância entre os vértices i e j
utilizando somente vértices internos do conjunto
{1, 2, . . . , k}.
Os valores iniciais de f são f (i, j, 0) =
– p. 31/39
Algoritmo de Floyd – Warshall
Seja f (i, j, k) a distância entre os vértices i e j
utilizando somente vértices internos do conjunto
{1, 2, . . . , k}.
Os valores iniciais de f são f (i, j, 0) = c(i, j).
– p. 31/39
Algoritmo de Floyd – Warshall
Seja f (i, j, k) a distância entre os vértices i e j
utilizando somente vértices internos do conjunto
{1, 2, . . . , k}.
Os valores iniciais de f são f (i, j, 0) = c(i, j).
A fórmula geral é:
f (i, j, k) = min{f (i, j, k−1), f (i, k, k−1)+f (k, j, k−1)}
– p. 31/39
Algoritmo de Floyd – Warshall
Seja f (i, j, k) a distância entre os vértices i e j
utilizando somente vértices internos do conjunto
{1, 2, . . . , k}.
Os valores iniciais de f são f (i, j, 0) = c(i, j).
A fórmula geral é:
f (i, j, k) = min{f (i, j, k−1), f (i, k, k−1)+f (k, j, k−1)}
O que queremos é calcular o valor f (i, j, n).
– p. 31/39
Algoritmo de Floyd – Warshall
4 −2
3
2 3
−1 2
– p. 32/39
Algoritmo de Floyd – Warshall
v1 v2 v3 v4
1
v1 0 ∞ −2 ∞
4 −2
3
v2 4 0 3 ∞
2 3
v3 ∞ ∞ 0 2
−1 2 v4 ∞ −1 ∞ 0
4
k=0
– p. 32/39
Algoritmo de Floyd – Warshall
v1 v2 v3 v4
1
v1 0 ∞ −2 ∞
4 −2
3
v2 4 0 2 ∞
2 3
v3 ∞ ∞ 0 2
−1 2 v4 ∞ −1 ∞ 0
4
k=1
– p. 33/39
Algoritmo de Floyd – Warshall
v1 v2 v3 v4
1
v1 0 ∞ −2 ∞
4 −2
3
v2 4 0 2 ∞
2 3
v3 ∞ ∞ 0 2
−1 2 v4 3 −1 2 0
4
k=2
– p. 34/39
Algoritmo de Floyd – Warshall
v1 v2 v3 v4
1
v1 0 ∞ −2 0
4 −2
3
v2 4 0 2 4
2 3
v3 ∞ ∞ 0 2
−1 2 v4 3 −1 2 0
4
k=3
– p. 35/39
Algoritmo de Floyd – Warshall
v1 v2 v3 v4
1
v1 0 −1 −2 0
4 −2
3
v2 4 0 2 4
2 3
v3 5 1 0 2
−1 2 v4 3 −1 2 0
4
k=4
– p. 36/39
Algoritmo de Floyd – Warshall
1. Para i = 1, 2, . . . , n faça d(i, i) ← 0;
2. Para cada par de vértices i, j faça
d(i, j) ← c(i, j);
– p. 37/39
Algoritmo de Floyd – Warshall
1. Para i = 1, 2, . . . , n faça d(i, i) ← 0;
2. Para cada par de vértices i, j faça
d(i, j) ← c(i, j);
3. Para k = 1 até n faça
Para i = 1 até n faça
Para j = 1 até n faça
Se d(i, k) + d(k, j) < d(i, j)
então d(i, j) ← d(i, k) + d(k, j)
– p. 37/39
Exercício
1. Execute o algoritmo de Floyd – Warshall para o
grafo abaixo.
2
1 2
3 −1
3 5
1
−2 4
−1
4 5
– p. 38/39
Exercício
2. Execute o algoritmo de Floyd – Warshall para o
grafo abaixo.
2
3 4
1
8
1 3
1
−4 2 −5
4 5
6
– p. 39/39
