Algoritmos em Grafos
Celso C. Ribeiro
Caroline T. Rocha
PARTE 3: CAMINHOS MAIS LONGOS
E SEQÜENCIAMENTO DE TAREFAS
Algoritmos em Grafos
2
Caminhos mais Longos
Adaptação dos algoritmos para o problema de caminho
mais curto
f
f* = mínimo f(x) = - máximo {- f(x)}
f*
x*
- f*
-f
Condição: o grafo não pode ter circuitos de comprimento
positivo.
Multiplicar as distâncias por (-1) e aplicar
o algoritmo para caminhos mais curtos
Algoritmos em Grafos
3
Caminhos mais Longos
Alternativa: adaptar os algoritmos de caminhos mais curtos
para que calculem caminhos mais longos.
Inicializar S  {2,3,...,n},
S  {1},
(1) 0,
(j) c1j se j1+
- caso contrário
Enquanto S   faça
Selecionar jS tal que (j)= maxiS{(i)}
e todos os predecessores de j já pertençam a S
S  S – {j}
S  S  {j}
Para iS e ij+ faça
(i)  max{(i,(j)+cji}
fim-enquanto
Algoritmos em Grafos
4
Caminhos mais Longos
Problema central de seqüenciamento de tarefas
Os grandes projetos exigem acompanhamento constante e
perfeita coordenação das tarefas, de modo a:
evitar atrasos
evitar custos adicionais
Problema de seqüenciamento:
Objetivo: determinar a ordem e o calendário de execução das
tarefas.
Tarefa
duração
restrições (precedências)
Representação por um grafo
Algoritmos em Grafos
5
Caminhos mais Longos
Exemplo:
Preparação da construção de um prédio:
1.
2.
3.
4.
5.
Executar o aterro (10 dias)
Instalar um guindaste (2 dias)
Fazer as fundações (6 dias)
Ligações elétricas (3 dias)
Instalação de esgotos (5 dias)
Restrições:
• O guindaste só pode funcionar após as ligações elétricas
estarem prontas.
• O guindaste é necessário para fazer as fundações.
• A instalação dos esgotos e as fundações só podem ser
executadas após o final do trabalho de aterro.
Algoritmos em Grafos
6
Caminhos mais Longos
PERT (Program Evaluation and Review Technique)
Rede PERT:
nós: representam etapas (instantes privilegiados do projeto)
- etapa INÍCIO
- etapa FIM
arcos: representam tarefas
- tarefas reais de duração positiva
- tarefas virtuais (ou fictícias) de duração nula para exprimir
as restrições de precedência.
Grafo potenciais-etapas (nós são etapas)
Algoritmos em Grafos
7
Caminhos mais Longos
Uma etapa x é atingida quando todas as tarefas (reais e
fictícias) correspondendo a arcos dos quais x é extremidade
final foram concluídas.
t1
x
t2
y
t3
Só é possível iniciar a execução da tarefa correspondente
ao arco (x, y) depois que a etapa x tiver sido atingida.
Algoritmos em Grafos
8
Caminhos mais Longos
Exemplo: A tarefa 1 deve estar terminada para que a tarefa 5
possa ser iniciada.
4
a
3
3
2
I
2
F
5
I
1
6
5
F
10
b
Supressão de arcos inúteis:
3
a
2
I
6
F
2
5
10
b
Algoritmos em Grafos
9
Caminhos mais Longos
Resolver um problema de seqüenciamento de tarefas
corresponde a:
determinar um calendário de execução
determinar as tarefas críticas (aquelas cujo atraso provoca
um atraso na execução do projeto como um todo)
controlar o desenvolvimento do projeto e saber, a cada
instante, atualizar as previsões iniciais
Algoritmos em Grafos
10
Caminhos mais Longos
Etapa x:
(x): data mais cedo (data mínima em que a etapa x pode ser
atingida)
(x): data mais tarde (data máxima em que a etapa x pode
ser atingida sem que resulte em atraso na execução do
projeto como um todo)
Uma tarefa é dita crítica se qualquer atraso em sua
execução se repercute automaticamente na duração do
projeto.
Caminho crítico:
formado por
tarefas críticas
Algoritmos em Grafos
11
Caminhos mais Longos
Para que a etapa x possa ser atingida, é necessário que
todos os caminhos de I a x tenham sido percorridos.
(x) = comprimento do caminho mais longo de
I a x considerando-se (I) = 0.
Tarefa u = (x,y):
(u) = (y) - (x) - d(u) é a folga da tarefa u.
u  caminho crítico
I(u)
x
u
(u) = 0
T(u)
y
O grafo PERT não tem circuitos.
Algoritmos em Grafos
12
Caminhos mais Longos
Algoritmo PERT
S  {I}, (I)  0
Enquanto  x  S tal que todos seus
predecessores estão em S faça
(x)  max{u: T(u)= x}{(I(u))+d(u)}
S  S  {x}
fim-enquanto
S  {F}, (F)  (F)
Enquanto  x  S tal que todos seus
sucessores estão em S faça
(x)  min{u: I(u)= x}{(T(u))-d(u)}
S  S  {x}
fim-enquanto
Calcular (u)  (T(u))-(I(u))–d(u), u  U
Algoritmos em Grafos
13
Caminhos mais Longos
3
a
Exemplo:
I
2
F
0
5
10
(I) = 0
6
b
S={I}
ITERAÇÃO 1: (b) = 10
S={I, b}
ITERAÇÃO 2: (a) = 10
S={I, a, b}
ITERAÇÃO 3: (F) = 16
S={I, a, b, F}
(F) = 16
S={F}
ITERAÇÃO 1:
(a) = 10
S={F, a}
ITERAÇÃO 2:
(b) = 10
S={F, b, a}
ITERAÇÃO 3:
(I) = 0
S={F, b, a, I}
Algoritmos em Grafos
14
Caminhos mais Longos
Grafo potenciais-tarefas:
nó  tarefa
arco(i,j)  se a tarefa i deve preceder a tarefa j
4
3
3
I
2
2
F
5
1
6
5
10
3
4
0
3
2
0
I
6
F
2
10
0
1
5
5
10
Algoritmos em Grafos
15
Caminhos mais Longos
A tarefa j só pode começar após a
metade da execução da tarefa i:
A tarefa j só pode começar um
tempo t após o fim de i:
A tarefa j só pode começar após
a data bj:
di/2
i
j
di + t
i
j
bj
I
j
Algoritmos em Grafos
16
Caminhos mais Longos
TAREFAS
DURAÇÃO
ANTERIORES
A
7
-
B
3
A
1
B
D
8
A
E
2
D, C
F
1
D, C
1
D, C
C
GRAFO POTENCIAIS-ETAPAS:
(2)=14
(2)=10
2
B
I
(I)=0
(I)=0
A
7
(1)=7
(1)=7
H
C
3
1
G
D
8
1
3
J
K
(3)=15 F
(3)=15 1
G
1
3
E 2
2 1
(4)=21
F
(4)=21
H
K
E, G ,J 1
4
J
H
2
5
6
3
(5)=16
(6)=19
(5)=16
(6)=19
F
(F)=22
(F)=22
Algoritmos em Grafos
17
Caminhos mais Longos
Cálculo das folgas:
(u) = (T(u)) – (I(u)) – d(u)
(A) = 7 – 0 – 7 = 0
(B) = 14 – 7 – 3 = 4
(C) = 15 – 10 – 1 = 4
(D) = 15 – 7 – 8 = 0
(E) = 21 – 15 – 2 = 4
(F) = 16 – 15 – 1 = 0
(G) = 21 – 15 – 1 = 5
(H) = 19 – 16 – 3 = 0
(J) = 21 – 19 – 2 = 0
(K) = 22 – 21 – 1 = 0
Caminho crítico:
ADFHJK
Algoritmos em Grafos
18
Caminhos mais Longos
GRAFO POTENCIAIS-TAREFAS:
B
3
0
G
DURAÇÃO
ANTERIORES
A
7
-
B
3
A
C
1
B
D
8
A
E
2
D, C
F
1
D, C
G
1
D, C
H
3
F
J
2
H
K
1
E, G ,H
1
7
I
1
C
TAREFAS
1
8
A
D
8
7
2
E
K
1
F
1
8
F
1
H
3
J
Algoritmos em Grafos
19