Problemas de Menor Caminho
 Se considerarmos uma rede na qual o arco signifique a
distância entre dois pontos (nós) e desejarmos achar a
rota que une estes pontos com distância mínima,
teremos um problema do tipo do Menor caminho.
 Este tipo de problema pode ser generalizado e aplicado
a distribuição de produtos, entre outros.
Capítulo 5
Problemas de Menor Caminho
Exemplo
 Considere a rede abaixo que representa a ligação
rodoviária entre duas cidades (A e B). O tamanho dos
arcos representa a distância entre pontos da malha
rodoviária entre as cidades.
30
1
3
40
20
20
B
A
30
Capítulo 5
2
30
4
20
Problemas de Menor Caminho
Exemplo
 Este problema pode ser visto como um problema de
rede de distribuição com um ponto de oferta de um
caminhão (A=-1) e ponto de demanda de um caminhão
(B=+1) e os demais pontos da malha sem demanda ou
30
oferta (=0)
3
1
40
20
20
[-1]
B
A
30
Capítulo 5
2
30
4
20
[+1]
Problemas de Menor Caminho
Exemplo
Capítulo 5
Problemas de Menor Caminho
Exemplo
Capítulo 5
Problemas de Menor Caminho
Solução
Capítulo 5
Problema do Fluxo Máximo
 Nesse tipo de problema temos uma rede de nós e arcos,
e desejamos que o maior fluxo de uma grandeza possa
fluir de um determinado nó para outro.
 Nesse tipo de problema mais de um caminho pode ser
utilizado simultaneamente.
 Aplicações

Rede de distribuição de água, luz, gás e tráfego na internet.
Capítulo 5