Problema do caminho de custo mínimo

                   

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)

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.