Uma pequena empresa transportadora envia diariamente seu caminhão para diversas cidades para fazer entregas. A quantidade de cidades visitadas pelo caminhão varia de acordo com a quantidade e destino das entregas a serem feitas. Sabendo-se antecipadamente por quantas cidades é necessário passar, o administrador da empresa consegue planejar um itinerário (rota) que o caminhão deverá seguir para fazer as entregas. No entanto, para algumas cidades de destino, existem múltiplos caminhos de acesso a elas. Isso significa que, nem todo itinerário planejado garantirá os menores caminhos a serem percorridos. Logo, é possível que um planejamento inadequado possa implicar em maiores distâncias percorridas, maior tempo entre as entregas e maior consumo de combustível. Isto evidencia maior custo no serviço de entregas e consequentemente, redução na margem de lucros da empresa.
Um exemplo genérico deste problema pode ser observado no Grafo ilustrado na Figura 01, onde alguns nós possuem múltiplos caminhos (arestas) de acesso:
Site utilizado para gerar o Grafo Graph Online