CAPÍTULO 7
Problemas de Fluxo em Redes
1. Conceitos fundamentais de grafos
Em muitos problemas que nos surgem, a forma mais simples de o descrever, é representá-lo em
forma de grafo, uma vez que um grafo oferece uma representação visual que trará vantagens na
construção de um modelo matemático com vista à resolução do problema.
Um grafo é uma estrutura constituída por dois conjuntos finitos : de vértices (nós ou nodos) e
de arestas (arcos ou ramos). Um grafo pode ser representado por G = (N, A), em que N = {1, ..., n} e A
= {1, ..., m} são os conjuntos de vértices e arestas, respectivamente, em que (A ⊆ N×N).
Cada aresta é representado por um par (i, j), com i ≠ j e i, j ∈ N, em que i é o vértice origem e j o
vértice destino. Uma aresta (i, j) diz-se não dirigida (não orientada), se (j, i) ∈ A e diz-se dirigida
(orientada), se (j, i) ∉ A.
Existem 3 tipos de grafos :
• orientado (dirigido)  todas as arestas são dirigidas,
• não orientado (não dirigido)  todas as arestas são não dirigidas e,
• misto  algumas arestas são dirigidas e outras são não dirigidas.
Um grafo diz-se completo, se entre quaisquer dois vértices existir uma aresta dirigida (grafos
dirigidos) ou não dirigida (grafos não dirigidos).
A densidade de um grafo é a razão entre a quantidade de arestas do grafo e a quantidade de
arestas do grafo completo com o mesma quantidade de vértices.
Dois vértices são adjacentes (vizinhos), se estiverem ligados por uma aresta. Duas arestas são
adjacentes se forem ambas incidentes relativamente ao mesmo vértice. Um vértice é de ordem k, se
tiver k arestas a ele adjacente.
90
Conceitos fundamentais de redes
Considere-se dois vértices, S e T, do grafo G. Um caminho de S para T, é uma sucessão de
vértices e arestas, p = [S = n1, (n1, n2), n2, ..., (nh-1, nh), nh = T]. No entanto, aquele caminho também
pode ser representado apenas pela sucessão de vértices (p = [S = n1, n2, ..., nh-1, nh = T]) ou de arestas
(p = [(S, n2), ..., (nh-1, T)]). O caminho p diz-se simples, se cada vértice e aresta pertencem à sucessão
uma única vez.
Um ciclo é um caminho em que S = T. Num ciclo simples, todos os vértices são distintos. Um
circuito (ciclo dirigido) é um ciclo formado por arestas dirigidas.
Um grafo dirigido sem ciclos dirigidos, diz-se acíclico. Um grafo diz-se ligado (conexo), se
existir um caminho entre quaisquer dois vértices.
Uma árvore é um grafo orientado com um e um só caminho simples entre quaisquer dois
vértices. Um subgrafo que seja uma árvore e contenha todos os vértices do grafo, é designado por
árvore abrangente (árvore total  ”Spanning Tree”).
2. Conceitos fundamentais de redes
Quando se associam valores aos vértices e/ou às arestas, o grafo designa-se geralmente por
rede. Neste caso, fala-se em nós (nodos) e arcos, e em vez de vértices e arestas, respectivamente.
Uma rede pode ser representada por G = (N, A, C), em que (N, A) é um grafo e C corresponde
ao conjunto de valores associados aos arcos (“comprimentos“) : ao arco (i, j) está associado o valor cij.
De uma maneira geral, os conceitos utilizados em grafos são extensíveis às redes.
Considere-se um caminho p de S para T, na rede G. O “comprimento“ do caminho p
corresponde à soma dos “comprimentos“ dos arcos que pertencem àquele caminho; ou seja,
C(p) =
∑
c ij
(i , j) ∈ p
O conjunto de todos os caminhos de S para T, numa rede qualquer G, identifica-se por P.
Define-se árvore mínima (árvore de caminhos mais curtos) com raiz em S, como a árvore que
contém todos os nós de N acessíveis a partir de S, em que para cada nó n2 o único caminho de S para
n2 é o caminho mais curto (de comprimento mínimo) na rede G que liga S a n2.
Problemas de Fluxo em Redes
O Problema do Caminho Mais Curto
91
3. O Problema do Caminho Mais Curto
Os problemas de caminho mais curto, são fundamentais e frequentes quando se estuda redes de
transportes e de comunicação. Este problema surge quando se pretende determinar o caminho mais
curto, mais barato ou mais fiável, entre um ou vários pares de nós de uma rede.
Existem três tipos de problemas de caminho mais curto :
(i) de um nó para outro,
(ii) de um nó para todos os outros,
(iii) entre todos os pares de nós.
No entanto, os dois primeiros são essencialmente o mesmo problema.
Sejam S e T dois nós de uma rede G = (N, A, C), em que a cada arco é associado apenas um
valor (comprimento do arco). O comprimento de um caminho de S para T, é a soma dos
comprimentos dos arcos que o compõem.
O problema do caminho mais curto entre os nós S e T, tem por objectivo determinar o caminho
de valor mínimo existente em P. Ou seja, determinar p ∈ P tal que C(p) ≤ C(q), ∀ q ∈ P.
Algumas observações relacionadas com este tipo de problemas :
• o comprimento de um caminho é maior do que o de qualquer dos seus subcaminhos;
• qualquer subcaminho de um caminho mais curto, é ele próprio um caminho mais curto
(princípio da optimalidade);
• para uma rede com n nós, qualquer caminho mais curto tem no máximo n-1 arcos (no
caminho mais curto entre dois nós, não existem nós repetidos).
Matematicamente, este problema pode ser formulado da seguinte forma :
Minimizar Z =
∑ ∑ c ij x ij
i∈N j∈N
sujeito a
∑ x Sj = 1
j∈N
∑ x ij − ∑ x jk = 0 ,
i∈N
∀j ∈ N − { S , T }
k∈N
∑ x iT = 1
i∈N
em que,
1,
x ij = 
0 ,
se (i, j) pertence ao caminho
se (i, j) não pertence ao caminho
Existem vários algoritmos eficientes para resolver problemas de caminho mais curto, sendo os
mais conhecidos os algoritmos de Dijkstra (i e ii) e de Floyd (iii).
Problemas de Fluxo em Redes
92
O Problema do Caminho Mais Curto
3.1. Algoritmo de Dijkstra
Este algoritmo, que foi apresentado por Dijkstra e que só pode ser aplicada a redes cujos arcos
têm associados comprimentos não negativos, baseia-se num processo de rotulação dos nós da rede e
classificação dos respectivos rótulos. A cada nó i é atribuído um rótulo [ξi, πi], o qual pode ser
permanente ou temporário. Isto quer dizer o seguinte :
[ξi, πi] permanente, representa o caminho mais curto de S para i
ξi ← nó que antecede i no caminho mais curto de S para i
πi ← valor do caminho mais curto de S para i
[ξi, πi] temporário, representa um caminho mais curto de S para i
ξi ← nó que antecede i no melhor caminho, até ao momento, de S para i
πi ← valor do melhor caminho, até ao momento, de S para i
O rótulo temporário de um nó representa um limite superior da distância mais curta de S a esse
nó, uma vez que o caminho que lhe está associado pode ser ou não o mais curto.
O algoritmo consiste em rotular os nós da rede, começando pelo S, de uma forma ordenada,
segundo as distâncias de cada nó a S : escolher o nó com rótulo temporário com menor valor de π,
que se torna permanente, para depois serem varridos todos os seus adjacentes, de forma a actualizar
os rótulos destes (temporários). O algoritmo termina quando não existirem nós com rótulos
temporários. Inicialmente apenas o nó S é permanente, sendo os restantes temporários.
Algoritmo :
Passo 1.
[ξS, πS] = [S, 0]
(caminho mais curto para S custa 0 e não tem nós intermédios)
[ξi, πi] = [S, CSi], ∀ i ∈ N − { S } e (S, i) ∈ A
[ξi, πi] = [−, ∞], ∀ i ∈ N − { S } e (S, i) ∉ A
Temporários = N − { S }
Permanentes = { S }
(Temporários = conjunto de nós com rótulos temporários)
(Permanentes = conjunto de nós com rótulos permanentes)
Passo 2.
Se Temporários = ∅
Então
(todos os nós têm rótulos permanentes)
STOP
k = nó de Temporários tal que πk é mínimo
(k : πk = min { πx , x ∈ Temporários })
Temporários = Temporários − { k }
Permanentes = Permanentes ∪ { k }
(k passou a permanente)
Problemas de Fluxo em Redes
O Problema do Caminho Mais Curto
93
Passo 3.
Para todo o j ∈ N tal que (k, j) ∈ A e j ∈ Temporários Fazer
Se πk + Ckj < πj
Então
πj = πk + Ckj
ξj = k
Regressar ao Passo 2.
O algoritmo apresentado, determina o caminho mais curto entre um dado nó S e todos os
outros nós da rede. Portanto, no fim do algoritmo, para se verificar se existe caminho entre S e um
qualquer nó k, bastando analisar o valor de πk : se πk = ∞ então não existe caminho. Se existir caminho
mais curto de S para k, este pode ser determinado percorrendo (em sentido inverso) a 1ª parte dos
rótulos dos nós (ξ) de k até S, da seguinte forma :
Caminho = { k }
i=k
Enquanto i ≠ S Fazer
i = ξi
Caminho ← Caminho ∪ { i }
Exemplo :
Determinar o caminho mais curto entre o nó S = 1 e todos os outros nós da seguinte rede :
Problemas de Fluxo em Redes
94
O Problema do Caminho Mais Curto
Passo 1.
Colocar rótulo permanente no nó 1 e rótulos temporários nos restantes nós.
Permanentes = { 1 }
Temporários = { 2, 3, 4, 5, 6, 7, 8 }
Passo 2.
k = 4, pois π4 = min { π2, π3, π4, π5, π6, π7, π8 } = min { 4, 5, 2, 12, ∞, ∞, ∞ }
Permanentes = Permanentes ∪ { 4 } = { 1, 4 }
Temporários = Temporários − { 4 } = { 2, 3, 5, 6, 7, 8 }
Passo 3.
Varrer todos os nós adjacentes a 4, com rótulos temporários e actualizar os seus rótulos:
π3 = min { π3, π4 + C43 } = min { 5, 2 + 1 } = 3
⇒ [ξ3, π3] = [4, 3]
π6 = min { π6, π4 + C46 } = min { ∞, 2 + 11 } = 13
⇒ [ξ6, π6] = [4, 13]
Passo 2.
k = 3, pois π3 = min { π2, π3, π5, π6, π7, π8 } = min { 4, 3, 12, 13, ∞, ∞ }
Permanentes = Permanentes ∪ { 3 } = { 1, 3, 4 }
Temporários = Temporários − { 3 } = { 2, 5, 6, 7, 8 }
Problemas de Fluxo em Redes
O Problema do Caminho Mais Curto
95
Passo 3.
Varrer todos os nós adjacentes a 3, com rótulos temporários e actualizar os seus rótulos :
π2 = min { π2, π3 + C32 } = min { 4, 3 + 3 } = 4
⇒ [ξ3, π3] = [1, 4] (sem alteração)
π8 = min { π8, π3 + C38 } = min { ∞, 3 + 13 } = 16
⇒ [ξ8, π8] = [3, 16]
Passo 2.
k = 2, pois π2 = min { π2, π5, π6, π7, π8 } = min { 4, 12, 13, ∞, 16 }
Permanentes = Permanentes ∪ { 2 } = { 1, 2, 3, 4 }
Temporários = Temporários − { 2 } = { 5, 6, 7, 8 }
Passo 3.
Varrer todos os nós adjacentes a 2, com rótulos temporários e actualizar os seus rótulos :
π5 = min { π5, π2 + C25 } = min { 12, 4 + 1 } = 5
⇒ [ξ5, π5] = [2, 5]
Passo 2.
k = 5, pois π5 = min { π5, π6, π8 } = min { 5, 13, 16 }
Permanentes = Permanentes ∪ { 5 } = { 1, 2, 3, 4, 5 }
Temporários = Temporários − { 5 } = { 6, 7, 8 }
Problemas de Fluxo em Redes
96
O Problema do Caminho Mais Curto
Passo 3.
Varrer todos os nós adjacentes a 5, com rótulos temporários e actualizar os seus rótulos :
π7 = min { π7, π5 + C57 } = min { ∞, 5 + 6 } = 11
⇒ [ξ7, π7] = [5, 11]
π8 = min { π8, π5 + C58 } = min { 16, 5 + 9 } = 14
⇒ [ξ8, π8] = [5, 14]
Passo 2.
k = 7, pois π7 = min { π6, π7, π8 } = min { 13, 11, 14 }
Permanentes = Permanentes ∪ { 7 } = { 1, 2, 3, 4, 5, 7 }
Temporários = Temporários − { 7 } = { 6, 8 }
Passo 3.
Varrer todos os nós adjacentes a 7, com rótulos temporários e actualizar os seus rótulos :
π8 = min { π8, π7 + C78 } = min { 14, 11 + 7 } = 14
⇒ [ξ8, π8] = [5, 14] (sem alteração)
Passo 2.
k = 6, pois π6 = min { π6, π8 } = min { 13, 14 }
Permanentes = Permanentes ∪ { 6 } = { 1, 2, 3, 4, 5, 6, 7 }
Temporários = Temporários − { 6 } = { 8 }
Passo 3.
Varrer todos os nós adjacentes a 6, com rótulos temporários e actualizar os seus rótulos :
π8 = min { π8, π6 + C68 } = min { 14, 13 + 8 } = 14
⇒ [ξ8, π8] = [5, 14] (sem alteração)
Passo 2.
k = 8, pois π8 = min { π8 } = min { 14 }
Permanentes = Permanentes ∪ { 8 } = { 1, 2, 3, 4, 5, 6, 7, 8 }
Temporários = Temporários − { 8 } = ∅
Passo 3.
Não existem nós adjacentes a 8, com rótulos temporários.
Problemas de Fluxo em Redes
O Problema do Caminho Mais Curto
97
Passo 2.
Temporários = ∅
⇒ Fim do algoritmo.
Resultados após o término do algoritmo :
caminho mais curto entre os nós 1 e 8 calcula-se da seguinte forma :
p={8}
i=8
Como i ≠ 1 então { i = ξi = ξ8 = 5 ; p = p ∪ { i } = { 5, 8 }
Como i ≠ 1 então { i = ξi = ξ5 = 2 ; p = p ∪ { i } = { 2, 5, 8 }
Como i ≠ 1 então { i = ξi = ξ2 = 1 ; p = p ∪ { i } = { 1, 2, 5, 8 }
Como i = 1 então termina o processo.
Logo, o caminho mais curto entre 1 e 8 é p = { 1, 2, 5, 8 } e o comprimento é C(p) = 14 (= π8).
a árvore de caminho mais curto do nó 1 para todos os outros é a seguinte :
e tem um comprimento total de 34 (Σ cij na árvore de caminhos mais curtos).
3.2. Algoritmo de Floyd
Ao pretender-se determinar o caminho mais curto entre todos os pares de nós, pode-se aplicar o
algoritmo de Dijkstra n vezes, utilizando cada nó, sucessivamente, como origem. No entanto, existem
outros algoritmos para resolver este problema, como é o caso do algoritmo de Floyd, desde que não
haja circuitos negativos  os arcos podem ter comprimentos negativos.
Considere-se uma rede G = (N, A, D). Um arco (i, j) designa-se por arco básico, se constituir o
caminho mais curto entre os nós i e j. Um caminho mais curto entre quaisquer dois nós da rede será
totalmente constituído por arcos básicos (embora existam arcos básicos não pertencentes ao caminho
mais curto).
O algoritmo de Floyd utiliza a matriz D, de ordem n, das distâncias directas mais curtas entre
nós. Os nós que não são adjacentes (não existe arco a ligá-los) têm associado uma distância directa
Problemas de Fluxo em Redes
98
O Problema do Caminho Mais Curto
infinita. Como os nós são (por convenção) adjacentes com eles próprios, têm associado um arco de
comprimento 0. Os ciclos próprios são ignorados.
Entre cada par de nós não ligados por um arco básico é criado um arco, através de um processo
identificado por “tripla ligação“ :
dij ← min { dij , dik + dkj }
Fixando um k, a “tripla ligação“ é efectuada para todos os nós i, j ≠ k.
Após efectuar a “tripla ligação“ para cada k ∈ N com i, j ∈ N − { k }, a rede (na matriz D alterada
ao longo deste processo) é apenas constituída por arcos básicos. Logo, o comprimento associado a
cada arco dirigido do nó i ao nó k, é o caminho mais curto entre aqueles dois nós.
Para conhecer todos os nós intermédios num dado caminho, mantém-se paralelamente uma
matriz P, de ordem n, onde o elemento Pij representa o primeiro nó intermédio entre os nós i e j.
Algoritmo :
Passo 1.
D = matriz das distâncias directas
Pij = j,
∀ i, j ∈ N
k←0
Passo 2.
Se k ≥ n Então STOP
k←k+1
Passo 3.
Se Dij > Dik + Dkj
(i, j ≠ k  não se considera a linha e a coluna k)
Então
Dij ← Dik + Dkj
Pij ← Pik
No final, os elementos da matriz D são as distâncias mais curtas entre qualquer par de nós.
Exemplo :
Determinar o caminho mais curto entre todos os pares de nós da seguinte rede :
Problemas de Fluxo em Redes
O Problema do Caminho Mais Curto
99
Passo 1.
0 8 5 


D = 3 0 ∞
∞ 2 0 
1 2 3 


P = 1 2 3 
1 2 3
k=0
Passo 2.
0 ≥ 3 (n = 3)
Falso
k=k+1=1
Passo 3.
D22 < D21 + D12 (0 < 3 + 8 = 11)
D23 > D21 + D13 (∞ > 3 + 5 = 8)
⇒
D23 = D21 + D13 = 8;
P23 = P21 = 1
D32 < D31 + D12 (2 < ∞ + 8)
D33 < D31 + D13 (0 < ∞ + 5)
0 8 5 


D = 3 0 8
∞ 2 0
1 2 3 


P = 1 2 1 
1 2 3
Passo 2.
1≥3
Falso
k=k+1=2
Passo 3.
D11 < D12 + D21 (0 < 8 + 3 = 11)
D13 < D12 + D23 (5 < 8 + 8 = 16)
D31 > D32 + D21 (∞ > 2 + 3 = 5)
⇒
D31 = D32 + D21 = 5;
P31 = P32 = 2
D33 < D32 + D23 (0 < 2 + 8)
0 8 5 


D = 3 0 8
5 2 0
1 2 3 


P = 1 2 1 
2 2 3
Passo 2.
2≥3
Falso
k=k+1=3
Passo 3.
D11 < D13 + D31 (0 < 5 + 5 = 10)
D12 > D13 + D32 (8 > 5 + 2= 7)
⇒
D12 = D13 + D32 = 7;
D21 < D23 + D31 (3 < 8 + 3 = 11)
Problemas de Fluxo em Redes
P12 = P13 = 3
100
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
D22 < D23 + D32 (0 < 8 + 2)
1 3 3 


P = 1 2 1 
2 2 3
0 7 5 


D =  3 0 8
5 2 0
Passo 2.
3≥3
Verdadeiro
STOP (termina o algoritmo)
Resultados após o final do algoritmo :
o comprimento do caminho mais curto entre os nós 1 e 2 é 7 (D12 = 7);
o caminho mais curto entre os nós 1 e 2 é { 1, 3 (P12 = 3), 2 (P32 = 2) }.
4. O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
A árvore abrangente mínima (“Minimum Spanning Tree”), é a árvore abrangente com o menor
comprimento entre todas as árvores abrangentes. O comprimento de uma árvore abrangente é o
somatório dos comprimentos associados aos respectivos arcos.
Note-se que, em geral, a árvore abrangente mínima é diferente da árvore de caminho mais curto
entre um nó origem e todos os outros nós da rede (calculada pelo algoritmo de Dijkstra).
Algoritmo 1 :
Passo 1.
Toma-se arbitrariamente um nó S e atribui-se-lhe um rótulo permanente nulo : πS = 0.
Aos restantes nós da rede atribuem-se rótulos temporários :
πj = CSj
se (S, j) ∈ A
πj = ∞
se (S, j) ∉ A
Permanentes = { S }
Temporários = N − { S }
Passo 2.
k = nó com rótulo temporário que possua menor valor (que é vizinho de um nó i);
Permanentes = Permanentes ∪ { k }
Temporários = Temporários − { k }
O arco com o mínimo valor Cik = πk passa a fazer parte da árvore abrangente mínima
Se Temporários = ∅
Então STOP (foi determinada a árvore abrangente mínima)
Problemas de Fluxo em Redes
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
Passo 3.
Para todo o j ∈ N tal que (k, j) ∈ A e j ∈ Temporários Fazer
πj = min { πj, Ckj }
Voltar ao Passo 2.
Exemplo :
Determinar a árvore abrangente mínima da seguinte rede :
Passo 1.
Colocar rótulo permanente no nó 1 e rótulos temporários nos restantes nós :
π1 = 0
π2 = 4;
π3 = 5;
π4 = 2;
π5 = 12
π6 = π7 = π8 = ∞
Permanentes = { 1 }
Temporários = { 2, 3, 4, 5, 6, 7, 8 }
Passo 2.
k=4
Permanentes = Permanentes ∪ { 4 } = { 1, 4 }
Temporários = Temporários − { 4 } = { 2, 3, 5, 6, 7, 8 }
O arco (1, 4) passa a fazer parte da árvore abrangente mínima, pois C14 = π4 = 2
Passo 3.
π3 = min { 5, 1 } = 1
π6 = min { ∞, 11 } = 11
Passo 2.
k=3
Permanentes = Permanentes ∪ { 3 } = { 1, 4, 3 }
Temporários = Temporários − { 3 } = { 2, 5, 6, 7, 8 }
O arco (4, 3) passa a fazer parte da árvore abrangente mínima, pois C43 = π3 = 1
Problemas de Fluxo em Redes
101
102
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
Passo 3.
π2 = min { 4, 3 } = 3
π8 = min { ∞, 13 } = 13
Passo 2.
k=2
Permanentes = Permanentes ∪ { 2 } = { 1, 4, 3, 2 }
Temporários = Temporários − { 3 } = { 5, 6, 7, 8 }
O arco (3, 2) passa a fazer parte da árvore abrangente mínima, pois C32 = π2 = 3
Passo 3.
π5 = min { 12, 1 } = 1
Passo 2.
k=5
Permanentes = Permanentes ∪ { 5 } = { 1, 4, 3, 2, 5 }
Temporários = Temporários − { 5 } = { 6, 7, 8 }
O arco (2, 5) passa a fazer parte da árvore abrangente mínima, pois C25 = π5 = 1
Passo 3.
π7 = min { ∞, 6 } = 6
π8 = min { 13, 9 } = 9
Passo 2.
k=7
Permanentes = Permanentes ∪ { 6 } = { 1, 4, 3, 2, 5, 7 }
Temporários = Temporários − { 7 } = { 6, 8 }
O arco (5, 7) passa a fazer parte da árvore abrangente mínima, pois C57 = π7 = 6
Passo 3.
π8 = min { 9, 7 } = 7
Passo 2.
k=8
Permanentes = Permanentes ∪ { 8 } = { 1, 4, 3, 2, 5, 7, 8 }
Temporários = Temporários − { 8 } = { 6 }
O arco (7, 8) passa a fazer parte da árvore abrangente mínima, pois C78 = π8 = 7
Passo 3.
π6 = min { 11, 8 } = 8
Problemas de Fluxo em Redes
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
103
Passo 2.
k=6
Permanentes = Permanentes ∪ { 6 } = { 1, 4, 3, 2, 5, 7, 8, 6 }
Temporários = Temporários − { 6 } = ∅
O arco (8, 6) passa a fazer parte da árvore abrangente mínima, pois C86 = π6 = 8
Como Temporários = ∅ STOP
(foi determinada a árvore abrangente mínima)
Resultados após o final do algoritmo :
a árvore abrangente mínima (árvore que visita todos os nós) é a seguinte :
a árvore abrangente mínima tem um comprimento total igual a 28 (2 + 1 + 3 + 1 + 6 + 7 + 8).
Existe uma outra versão do algoritmo de PRIM, que opera sobre a matriz das distâncias (custos)
da rede.
Algoritmo 2 :
Passo 1.
Riscar a 1ª coluna e marcar a 1ª linha.
Passo 2.
Seleccionar o menor elemento (Cij) das linhas marcadas (não considerar as colunas riscadas).
Se tiverem todas as colunas riscadas, STOP  foi determinada a árvore abrangente mínima.
Passo 3.
Riscar a coluna j e marcar a linha j.
Voltar ao Passo 2.
Os arcos que constituem a árvore abrangente mínima, são os correspondentes aos seleccionados, e o
seu valor é o somatório daqueles Cij .
Problemas de Fluxo em Redes
104
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
Exemplo :
Determinar o árvore abrangente mínima da rede do exemplo apresentado neste capítulo.
Passo 1. Riscar a 1ª coluna e marcar a 1ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
0
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
Passo 2. O menor elemento não riscado da linha 1 (a única seleccionada) é : C14 = 2
Passo 3. Riscar a 4ª coluna e marcar a 4ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
0
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
Passo 2. O menor elemento não riscado das linhas 1 e 4 (as seleccionadas) é : C43 = 1
Passo 3. Riscar a 3ª coluna e marcar a 3ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
0
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
Problemas de Fluxo em Redes
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
105
Passo 2. O menor elemento não riscado das linhas 1, 3 e 4 (as seleccionadas) é : C32 = 3
Passo 3. Riscar a 2ª coluna e marcar a 2ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
0
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
Passo 2. O menor elemento não riscado das linhas 1, 2, 3 e 4 (as seleccionadas) é : C25 = 1
Passo 3. Riscar a 5ª coluna e marcar a 5ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
0
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
Passo 2. O menor elemento não riscado das linhas 1, 2, 3, 4 e 5 (as seleccionadas) é : C57 = 6
Passo 3. Riscar a 7ª coluna e marcar a 7ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
0
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
Problemas de Fluxo em Redes
106
O Problema da Árvore Abrangente Mínima -- algoritmos de PRIM
Passo 2. O menor elemento não riscado das linhas 1, 2, 3, 4, 5 e 7 (as seleccionadas) é : C78 = 7
Passo 3. Riscar a 8ª coluna e marcar a 8ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
0
Passo 2. O menor elemento não riscado das linhas 1, 2, 3, 4, 5, 7 e 8 (as seleccionadas) é : C86 = 8
Passo 3. Riscar a 6ª coluna e marcar a 6ª linha :
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
4
5
2
12
4
0
3
2
12
1
−
1
5
3
0
1
−
−
−
−
6
−
−
−
−
−
−
−
−
−
−
−
0
−
−
−
13
9
8
7
−
−
−
13
−
1
0
−
11
−
−
−
−
0
−
6
9
−
8
−
0
7
0
Passo 2. Como todas as colunas se encontram riscadas, então STOP  foi determinada a árvore
abrangente mínima.
Resultados no final do algoritmo :
A árvore abrangente mínima é constituída pelos seguintes arcos :
(1, 4), (2, 5), (3, 2), (4, 3), (5, 7), (7, 8) e (8, 6)
O valor da árvore abrangente mínima é :
2 + 1 + 3 + 1 + 6 + 7 + 8 = 28
Como se pode verificar, a árvore é a mesma que foi determinada pela versão anterior.
Problemas de Fluxo em Redes
O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
107
5. O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
Neste capítulo, será estudado o problema de fluxo máximo numa rede G. Os valores associados
aos arcos desta rede, bij, representam as respectivas capacidades, isto é, a quantidade máxima de
fluxo que pode ser enviada pelos arcos. Estes valores terão que ser positivos (bij ≥ 0). Portanto, podese definir a rede da seguinte forma : G = (N, A, B), em que B = [bij].
Em problemas de fluxo máximo, existem 2 nós especiais : nó origem e nó terminal. Com a
resolução do problema de fluxo máximo, pretende-se determinar a quantidade máxima de unidades
de fluxo que podem ser enviados de um nó origem S para um nó terminal T.
O fluxo no arco (i, j) é designado por xij. Devido às restrições de capacidade nos arcos, tem-se o
conjunto de restrições :
0 ≤ xij ≤ bij,
para todo (i, j) ∈ A
[1]
Além disso, em cada nó (excepto em S e T) deve haver conservação de fluxo : a quantidade de fluxo
que chega a um nó é igual à quantidade de fluxo que sai desse nó; ou seja,
∑ x ij = ∑ x jk
i
para todo j ≠ S, T
[2]
k
Como existe conservação de fluxo em todos os nós, o fluxo que sai do nó S é igual ao fluxo que chega
ao nó T; isto é,
∑ x Si = f = ∑ x jT
i
[3]
j
onde f é o valor de fluxo
Portanto, com a resolução do problema de fluxo máximo, pretende-se determinar o valor do
fluxo nos arcos xij [1], que maximize o valor do fluxo f, sujeito às restrições de capacidade [2] e de
conservação de fluxo [3].
Matematicamente, este problema pode ser formulado da seguinte forma :
Maximizar f = ∑ x Sj
j
sujeito a
∑ x ij = ∑ x jk
i
para todo j ≠ S, T
∑ x Si = ∑ x jT
i
[2]
k
[3]
j
0 ≤ xij ≤ bij,
para todo (i, j) ∈ A
Dado um caminho qualquer de S para T numa rede,
p = [ S = n1, n2, n3, . . . , nk-1, nk = T ],
Problemas de Fluxo em Redes
[1]
108
O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
a quantidade máxima de fluxo que pode ser enviada de S para T, satisfazendo [1], [2] e [3], por aquele
caminho, é a seguinte :
min { bij : (i, j) ∈ p }.
Logo, o arco com a menor capacidade fica “saturado”, não podendo passar mais fluxo por ele.
Um corte (“cut”) é o conjunto de todos os arcos de um subconjunto de nós para o seu
complementar : o corte ( X , X) é o conjunto de todos os arcos (i, j), tal que i ∈ X e j ∈ X . A remoção de
todos os arcos do corte, desliga a rede em duas ou mais partes.
A capacidade de um corte é :
C( X , X) =
∑ b ij ,
com i ∈ X e j ∈ X .
( i , j)
Em geral, C( X , X) ≠ C( X , X) .
Um corte separando S de T, com uma capacidade mínima, designa-se por corte mínimo.
Teorema do “fluxo máximo  corte mínimo” (“max flow  min cut”).
Para qualquer rede com capacidades de valor inteiro associadas aos arcos, o fluxo máximo do nó
origem S, para o nó terminal T, é igual à capacidade de um corte mínimo que separa S de T.
Enquanto existir um caminho de aumento de fluxo (c.a.f.) satisfazendo uma das condições :
• xij < bij  arco “forward” (sentido correcto) : pode enviar-se fluxo adicional de i para j,
• xji > 0  arco “backward” (sentido inverso) : pode enviar-se fluxo adicional de i para j,
diminuindo o fluxo que existe de j para i,
é possível aumentar a quantidade de fluxo a enviar de S para T.
Assumindo que as capacidades dos arcos são valores inteiros, definido um caminho de
aumento de fluxo constituído por arcos “forward”e arcos “backward”, o fluxo a enviar de S para T
pode ser alterado de ε unidades :
ε = min { ε1, ε2 } [inteiro positivo]
com ε1 = min { bij − xij } nos arcos “forward” do c.a.f.
ε2 = min { xji } nos arcos “backward” do c.a.f.
O valor do fluxo é, então, aumentado em ε unidades nos arcos “forward” e diminuído em ε
unidades nos arcos “backward”.
Como a capacidade de um corte mínimo é um número finito e em cada caminho de aumento de
fluxo, o fluxo é aumentado de pelo menos 1 unidade, o fluxo máximo obtém-se após um número
finito de iterações.
Um fluxo é máximo, se e só se, não existir um caminho de aumento de fluxo.
Problemas de Fluxo em Redes
O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
109
Algoritmo de Ford−Fulkerson :
Este algoritmo, é um modo sistemático de pesquisar todos os possíveis c.a.f. de S para T,
atribuindo rótulos aos nós para indicar a direcção em que o fluxo pode ser aumentado. Cada nó pode
estar num dos 3 estados :
• rotulado e varrido ⇒ tem um rótulo e todos os seus vizinhos estão rotulados;
• rotulado e não varrido ⇒ tem um rótulo, mas nem todos os seus vizinhos estão rotulados;
• não rotulado ⇒ não tem rótulo.
O rótulo do nó j tem 2 partes : [i+, ε(j)] (ou [i−, ε(j)]), em que,
• i+ (ou i−) : índice de um nó i, indicando que pode-se enviar fluxo de i para j (ou de j para i)
• ε(j) : fluxo máximo adicional que se pode enviar de S para j.
Algoritmo :
Passo 1.
S ← [S+, ∞]
S fica rotulado e varrido
Passo 2. (processo de rotulação)
j (rotulado e não varrido) ← [i+, ε(j)] ou [i−, ε(j)]
Para todo o k ∈ N tal que (j, k) ∈ A e xjk < bjk Fazer
k ← [j+, ε(k)]
com ε(k) = min { ε(j), bjk − xjk }
Para todo o k ∈ N tal que (k, j) ∈ A e xkj > 0 Fazer
k ← [j−, ε(k)]
com ε(k) = min { ε(j), xkj }
j fica rotulado e varrido.
Todos os k ficam rotulados e não varridos.
Se (T está rotulado) ou (não é possível rotular T)
Então (foi determinado um c.a.f.) ou (não existe c.a.f. ⇒ o fluxo actual é máximo)
Senão Regressar ao Passo 2 (início)
Passo 3. (mudança de fluxo)
T ← [k+, ε(T)]
⇒
xkT = xkT + ε(T)
Enquanto k ≠ S Fazer
Se k ← [j+, ε(k)] ⇒
xjk = xjk + ε(T)
Se k ← [j−, ε(k)] ⇒
xkj = xkj − ε(T)
k←j
Apagar os rótulos e regressar ao Passo 1.
Problemas de Fluxo em Redes
110
O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
Exemplo :
Considere a rede em baixo, onde os valores correspondem às capacidades e ao fluxo nos arcos.
Pretende-se determinar o fluxo máximo a enviar do nó 1 para o nó 4, atendendo a que o fluxo
actual enviado entre aqueles 2 nós é de 2 unidades.
Passo 1.
Fluxo actual = 2
1 ← [1+, ∞]
RotuladosVarridos = ∅
RotuladosNãoVarridos = { 1 }
NãoRotulados = { 2, 3, 4 }
Passo 2.
j ← 1 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 1 : 2 e 3.
2 não pode ser rotulado, pois b12 = x12
3 ← [1+, min { ε(1), b12 − x12 }] ≡ [1+, min { ∞, 1 }] ≡ [1+, 1]
RotuladosVarridos = { 1 }
RotuladosNãoVarridos = { 3 }
NãoRotulados = { 2, 4 }
Passo 2.
j ← 3 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 3 : 2 e 4.
2 ← [3−, min { ε(3), x23 }] ≡ [3−, min { 1, 1 }] ≡ [3−, 1]
4 não pode ser rotulado, pois b34 = x34
RotuladosVarridos = { 1, 3 }
RotuladosNãoVarridos = { 2 }
NãoRotulados = { 4 }
Problemas de Fluxo em Redes
O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
111
Passo 2.
j ← 2 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 2 : 4.
4 ← [2+, min { ε(2), b24 − x24 }] ≡ [2+, min { 1, 3 }] ≡ [2+, 1]
RotuladosVarridos = { 1, 3, 2 }
RotuladosNãoVarridos = { 4 }
NãoRotulados = ∅
Como T = 4 foi rotulado, foi determinado um caminho de aumento de fluxo.
Passo 3. (mudança de fluxo : o aumento de fluxo é de ε(4) = 1 unidades)
fluxo = fluxo + ε(4) =2 + 1 = 3
4 ← [2+, 1]
⇒
x24 = x24 + ε(4) = 0 + 1 = 1
2 ← [3−, 1]
⇒
x23 = x23 − ε(4) = 1 − 1 = 0
3 ← [1+, 1]
⇒
x13 = x13 + ε(4) = 1 + 1 = 2
Passo 1.
Fluxo actual = 3
1 ← [1+, ∞]
RotuladosVarridos = ∅
RotuladosNãoVarridos = { 1 }
NãoRotulados = { 2, 3, 4 }
Passo 2.
j ← 1 (rotulado e não varrido)
Vizinhos (não rotulados) do nó 1 : 2 e 3.
2 não pode ser rotulado, pois b12 = x12
3 não pode ser rotulado, pois b13 = x13
Como não é possível rotular mais nenhum nó, e como o nó T = 4 não foi rotulado, então não
existe caminho de aumento de fluxo; logo, o fluxo actual é máximo.
Problemas de Fluxo em Redes
112
O Problema do Fluxo Máximo -- algoritmo de Ford-Fulkerson
Resultados a retirar após o final do algoritmo :
Fluxo máximo = 3.
X={1}
X = { 2, 3, 4 }
C(X, X ) = b12 + b13 = 3 = Fluxo máximo
Problemas de Fluxo em Redes