Projeto de Python - Dijkstra

Data de entrega: 26/6 ate as 23:59

Escreva um programa em Python que vai calcular o caminho mais rápido entre uma origem em um destino dado. O programa recebe um grafo direcionado e informação sobre a distancia e velocidade máxima na aresta, e recebe também informação sobre a velocidade real na áreas e deve calcular o cominho mais rápido (assumindo que o motorista andará na maior velocidade permitida em cada aresta) entre uma origem e um destino dados.

Os dados tem a seguinte forma:

25.0
a b 0.4
a c 0.5 50.0
b d 1.2
b z 0.2 
z f 0.3 40.0

a b 12.5
a c 4.1
b z 0
a
z

A primeira linha indica a velocidade máxima default nas ruas da cidade, neste case, se não ha indicação de velocidade máxima na rua, assume-se que seja 25k/h

As linhas seguintes são as arestas direcionadas que possuem 3 ou quatro valores. Os dois primeiros são os vértices. O terceiro valor é a distancia em quilômetros entre os vértices. Se houver um quarto valor ele é a velocidade máxima naquele trecho e naquele sentido. O fato da velocidade máxima entre a e c ser 50k/h não significa que ele seja a velocidade no sentido de c para a. Na verdade pode não haver uma aresta de c para a (ou seja esse trecho da rua é mão única).

Ao final do grafo haverá uma linha sem dados. A partir deste ponto os dados indicam as velocidades atuais nas arestas. Neste momento a velocidade possível de a para b é só 12.5 k/h. Note que nem todas as arestas terão uma linha de atualização da sua velocidade real. Note também que algumas ruas podem ter velocidade máxima de 0k/h ou seja a rua esta fechada e aquela aresta temporariamente não existe.

Finalmente haverá duas linhas com a origem (a) e o destino (z).

Calcule o caminho mais rápido entre a origem e o destino.

Se:

• a origem não for um dos vértices do grafo imprima Origem nao existe (sem acento)
• o destino não for uma dos vértices do grafo imprima Destino nao existe
• se não houver caminho possível entre a origem e o destino imprima Nao existe caminho
• se houver caminho, imprima o tempo de transito em minutos (sem casas decimais), e na próxima linha a sequencia de vértices, da origem ate o destino separados por um branco.

Por exemplo:

18
a b d e g z

indica que o tempo de transito será de 18 minutos (truncado!!) e que o caminho mais rápido é de a para b para d … até z

Seu programa será executado no Susy 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__":
     funcprincipa()

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