Problema do Caminho Mínimo em Grafos

Prévia do material em texto

Caminho Mínimo 
Um problema de caminho mínimo consiste basicamente em determinar o caminho de menor 
custo entre dois nós de um determinado grafo (diagrama). Os nós desse grafo são pontos de 
referência de uma determinada região. Esses pontos podem ser esquinas, terminais de ônibus, portos, 
aeroportos ou outros locais específicos a serem considerados. Os arcos fornecem como informação, a 
distância, tempo, valor ou outro tipo de custo entre dois nós consecutivos. Problemas de caminho 
mínimo são bastante freqüentes na área de logística. 
Para ilustrarmos um problema de caminho mínimo bem como a resolução do problema 
utilizando o WinQSB, vamos considerar o seguinte grafo ilustrando algumas localidades e as 
respectivas distâncias, em quilômetros, entre os nós. 
 
 
 
Nesse caso, o nosso objetivo é determinar o menor caminho possível a ser percorrido para que 
um automóvel parta do ponto A e chegue ao ponto G. 
Para resolvermos um problema de caminho mínimo, o primeiro passo é construir uma tabela 
contendo os custos de cada arco, ou seja, os custos entre dois nós consecutivos. 
 
 
 A B C D E F G 
A 7 5 
B 7 8 9 7 
C 8 5 
D 5 9 15 6 
E 7 5 15 8 9 
F 6 8 11 
G 9 11 
 
Para utilizarmos o WinQSB, vamos clicar em Iniciar, WinQSB. Em seguida, é só clicar em Network 
Modeling: 
 
O próximo passo é clicar em File, New Problem. 
 
Agora vamos selecionar a opção Shortest Path Problem. Para esse exemplo, devemos 
considerar 7 nós, ou seja, digitar o número 7 no campo Number of Nodes e depois clicar em OK. 
 
Fazendo isso, teremos a seguinte tabela no WinQSB: 
 
Precisamos agora efetuar a troca dos nomes dos nós. Basta clicar em Edit e selecionar a opção 
Node Names: 
 
Agora é só digitar os respectivos nomes e clicar em OK: 
 
Preenchendo a tabela de acordo com os dados do problema, temos: 
 
Para resolvermos o problema, podemos selecionar a opção Solve and Analyze, Solve the 
Problem ou então basta clicar no ícone para obtermos a respectiva solução. 
 
A tela a seguir mostra as opções de porto inicial e ponto final do problema. Nesse caso, 
selecionaremos os pontos A e G, respectivamente: 
 
Para obtermos a solução do problema, basta clicar em Solve. 
 
A resposta do problema consiste em, partindo do nó A, passar pelos nós D e F até chegarmos 
ao destino que é o nó G. 
 
Caminho: A-D-F-G 
Total: 22 km