Problema do menor caminho

PROBLEMA DO MENOR CAMINHO
Consiste em encontrar o menor caminho entre uma origem e um destino, dentro de uma rede, minimizando o custo de travessia de um grafo, entre dois nós (ou vértices), custo este dado pela soma dos pesos de cada aresta percorrida.

Origem – Ponto de ônibus de partida
Destino – Ponto de ônibus de chegada
Rede – Itinerários disponíveis das diversas linhas de ônibus que abastecem determinada área geográfica.
Pesos de cada aresta – Distância, trânsito em determinado horário de pico, problemas viários.

1 - Determinada região da cidade possui diversas linhas de ônibus que a alimentam.

2 - O conjunto das linhas de ônibus de determinada região da cidade perfazem uma rede complexa de itinerários.

3 – Cada itinerário passa por vários pontos e conforme a ocasião leva a pontos diferentes ou iguais aos outros.

4 – Cada Ponto pode ser alimentado por várias linhas.

5 – Cada Itinerário pode possuir pontos em comum com outros.

6 – Os pontos estão localizados nos logradouros, cujos nomes são conhecidos pelos usuários das linhas e serão usados como locais de origem e destino.

Observação: Em um mesmo logradouro o itinerário de uma linha pode passar duas vezes, uma na ida outra na volta.

Descrição das formas de escolha das melhores rotas pelos passageiros:

O comportamento dos usuários do transporte coletivo na hora de fazer a escolha da rota pode ser classificado em dois tipos segundo a literatura existente: no tipo I o passageiro espera um ônibus de uma linha determinada, e no tipo II o passageiro espera o primeiro ônibus a aparecer no ponto de parada, de um subconjunto de linhas consideradas atrativas.

No primeiro grupo estão aqueles que se baseiam no conceito de rota mínima, ou seja, o usuário do sistema de transporte coletivo utilizará a rota que minimize seu custo generalizado. O usuário já sabe qual é a linha que tem o menor custo generalizado para chegar até seu destino, e somente espera um ônibus daquela linha, o que