Menor Caminho no Grafo

Prévia do material em texto

Menor Caminho no Grafo 
 
Analisando as possibilidades de percurso no grafo, o caminho de menor distância que 
encontrei foi: 
A - B - E - D - C - A 
Somando as distâncias de cada trecho: 
6 + 10 + 3 + 4 + 5 = 28 
Também é possível fazer o mesmo percurso no sentido contrário: 
A - C - D - E - B - A 
Nesse caso, a soma também é 28. Outros caminhos possíveis acabam apresentando uma 
distância maior. 
Assim, o menor percurso para passar por todas as cidades uma única vez e voltar à cidade 
inicial é de 28 unidades de distância. 
 
Autor: Carlos Alberto Menezes Dos Santos 
RA:2820363 
Curso: Eng. Produção 
 
	Menor Caminho no Grafo