Baixe o app para aproveitar ainda mais
Prévia do material em texto
2. Caminho mais rápido em transportes aéreos Pretende-se desenvolver um programa para ajudar a escolher o vôo ou vôos a tomar para viajar de um aeroporto de origem para um aeroporto de destino no menor tempo possível (desde a partida no aeroporto de origem até à chegada ao aeroporto de destino), sem restrição de hora de partida ou chegada. Os vôos oferecidos pelas companhias aéreas estão especificados num arquivo de texto (a ler pelo programa), com uma linha para cada vôo, indicando o número do vôo (sigla da companhia aérea seguido de um número atribuído pela companhia), o nome do aeroporto de origem, a hora de partida do aeroporto de origem, o nome do aeroporto de destino e a hora de chegada ao aeroporto de destino. No caso de um vôo com escalas, são indicados os aeroportos intermediários, por ordem, entre os aeroportos de origem e de destino, com a hora de chegada e a hora de partida a seguir ao nome de cada aeroporto intermediário. Os nomes de aeroportos são escritos sem espaços. Todas as horas são em tempo GMT. Exemplo de um arquivo com especificação de vôos: TP1982 Porto 09:00 Madrid 11:00 IB8717 Madrid 12:00 LasPalmasGranCanaria 15:00 15:30 SantaCruzTenerife 16:20 TP1985 Porto 09:30 Lisboa 10:30 PGA102 Lisboa 12:40 SantaCruzTenerife 16:00 16:30 LasPalmasGranCanaria 17:20 Supõe-se que todos os vôos se realizam diariamente. Supõe-se que podem entrar e sair passageiros em todos os aeroportos intermediários em que um vôo faz escala. Supõe-se que, para poder mudar de vôo num aeroporto, um passageiro precisa pelo menos de 30 minutos (entre a chegada num vôo e a partida noutro vôo). O programa deve ter como parâmetros de chamada (passados na linha de comandos) o nome do arquivo com a especificação dos vôos, o nome do aeroporto de origem e o nome do aeroporto de destino. O programa deve escrever no standard output o vôo ou vôos a tomar. No caso de vários vôos, o programa deve escrever uma linha para cada vôo. Para cada vôo a tomar, o programa deve mostrar o número do vôo, o aeroporto em que se deve tomar esse vôo, a hora de saída do vôo, o aeroporto em que se deve deixar esse vôo e a hora de chegada do vôo. Por exemplo, para os vôos acima especificados, e para viajar do Porto para SantaCruzTenerife o programa deve produzir o seguinte resultado: TP1985 Porto 09:30 Lisboa 10:30 PGA102 Lisboa 12:40 SantaCruzTenerife 16:00 Conceitualmente, este problema pode ser resolvido aplicando os algoritmos de caminhos mais curtos em grafos (nomeadamente o algoritmo de Dijkstra), sobre um grafo modificado conforme indicado na figura seguinte (relativamente aos vôos acima exemplificados). As letras "C" e "P" referem -se a chegadas e partidas, respectivamente. As ligações entre aeroportos são marcadas com o tempo de vôo correspondente. Em cada aeroporto, todas as chegadas são ligadas a todas as partidas, com o tempo de espera correspondente. O caminho mais curto entre Porto e SCT está indicado a traço mais forte. O programa deve ter opções (na forma de parâmetros passados na linha de comandos) para, caso o usuário pretenda, restringir as horas de saída e as horas de chegada.
Compartilhar