Problema do caminho de custo mínimo

Prévia do material em texto

Problema do caminho de custo mínimo 
	Docente: Sofia Mara de Souza
 Discente:Ronival Pereira Lima
	De forma a reduzir seus custos operacionais, uma empresa de transporte de cargas deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o melhor caminho (o de menor distância) entre quaisquer duas cidades por ela servidas, de forma a que sejam minimizados os custos de transporte.
	Um possível modelo para este problema poderia ser: – G (V,A) V = { x | x é cidade } – A = { (xi , xj , d) | há uma conexão por estrada entre as cidades xi e xj , sendo d a distância que as separa }
	O problema de encontrar o caminho de custo mínimo entre dois vértices de um grafo é o mais importante relacionado com a busca de caminhos em grafos em vista de sua aplicação à várias situações de realidade.	
	Há um grande número de situações possível quando da obtenção deste caminho, a exemplo de: existência ou não de ciclos; determinação do caminho ou apenas do custo mínimo; etc. Dada esta diversidade de situações, há um número razoável de algoritmos que foram propostos ao longo do tempo, dentre os quais os algoritmos de Dijkstra e de Floyd.