Projeto de Python - Waze para transporte público

versão 1

Data de entrega: 14/5 ate as 8:00

Individual ou em grupos de 2

Escreva um programa em Python que vai calcular o caminho mais rápido entre uma origem em um destino dado usando uma combinação de caminhar e usar transporte público. O programa recebe um grafo direcionado com um label e um valor nas arestas. O label indica o modo de transporte: "a pé", "linha 370", "linha 4567", "metro linha azul", etc. E o valor, o tempo em minutos para percorrer aquela aresta usando aquele modo.

O programa recebe o grafo (com as múltiplas arestas entre vértices), a origem e o destino, e deve imprimir a sequencia de vértices e modos, e o tempo esperado para chegar ao destino.

Por exemplo a saída:

a a-pe b a-pe c linha-370 f a-pe h a-pe i
17.5

indica que a pessoa deve ir a pé de a para b, de b para c, pegar a linha 370 em c, descer em f, e de la, andar para h e i. O percurso todo demorará 17.5 minutos (ou unidades de tempo)

Mas, como sabemos, há um custo em tempo em pegar um ônibus ou metro - temos que esperar até o ônibus chegar. Para esse projeto vamos assumir que o custo é fixo e é metade do período do ônibus - se o ônibus sai a cada 15 minutos do ponto inicial, em média esperaremos 7.5 minutos no ponto para pegar o ônibus. Assim para cada modo (que não a-pe) há um custo de "entrar no modo" (mas não ha custo em sair do modo).

Os dados tem a seguinte forma:

a b a-pe 0.4
b a a-pe 0.6
b c a-pe 0.5 
c b a-pe 0.5
c d a-pe 0.3
d c a-pe 0.3
a d linha-370 0.1
d f a-pe 3
f h linha-567 1.2
f h a-pe 12.3

linha-370 7.5
linha-567 12.0

a h

A primeira linha indica que a-pe de a para b demora 0.4. Na outra direção (de b para a) demora mais (subida?).

A linhas 9 e 10 indicam que de f para h demora 12 minutos a pe e 1.2 minutos no ônibus "linha 567".

Uma linha em branco separa as informações de espera para cada modo: pegar um ônibus da linha 370 demora 7.5 minutos.

E uma linha em branco separa a origem e destino: encontre o caminho que sai de a e vai até h.

Obviamente buscar o caminho mais curto num grafo implica em usar Dijkstra mas há talvez 2 problemas um usar o Dijkstra direto:

• possivelmente há mais de uma aresta entre dois vértices: os diferentes modos de transporte que percorrem a aresta de a para b.
• o custo de pegar um desses modos de transporte que não a-pe.

Talvez a parte mais difícil desse projeto é como incorporar desses 2 problemas no Dijkstra.

Seu programa será executado como

python3 prog3.py < arq1.in

Ou seja, você precisa chamar o programa de prog3.py e precisa ter as linhas no final:

if __name__ == "__main__":
     funcprincipal()

que indica que o Python executará funcprincipal (use o nome que vc quiser) como a primeira chamada do programa.