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.