# -*- coding:utf-8 -*- __nom_fichier__ = "liaisons aeriennes" __author__ = "fay7 : Christine Fay-Varnier" __date__ = "décembre 2024" from sys import maxsize def liaison_directe(table_tarifs, ville_depart, ville_arrivee): """ @param table_tarifs: dictionnaire tel que table[ville_depart] = liste des liaisons [(ville_arrivee, tarif),...] @param ville_depart: ville de départ @param ville_arrivee: ville d'arrivée @return: True si une liaison existe entre depart et arrivee et son cout False et 0 sinon """ if ville_depart not in table_tarifs: # la ville de départ n'existe pas dans la table # on retourne echec dans ce cas return False, 0 # sinon, on recherche une liaison directe for (destination, prix) in table_tarifs[ville_depart]: # on recherche dans toutes les liaisons au depart de la ville de depart # une liaison est composee d'une ville d'arrivee et d'un tarif if ville_arrivee == destination: return True, prix return False, 0 def liaison_indirecte(table_tarifs, ville_depart, ville_arrivee): """ @param table_tarifs: dictionnaire tel que table[ville_depart] = liste des liaisons [(ville_arrivee, tarif),...] @param ville_depart: ville de départ @param arrivee: ville d'arrivée @return: recherche si une lisaison avec une escale au plus existe entre les villes depart et arrivee La fonction retourne un tuple (code du resultat, cout, escale) False si aucun liaison indirecte n'existe, -1, "" True si une liaison avec une escale existe, son prix total et l'escale """ # recherche d'une liaison avec escale for escale, cout_portion1 in table_tarifs[ville_depart]: # recherche d'une liaison entre l'escale potentielle et l'arrivee direct, cout_portion2 = liaison_directe(table_tarifs, escale, arrivee) if direct: # liaison directe entre dest et arrivee cout_total = cout_portion2 + cout_portion1 return True, cout_total, escale # sinon pas de liaison possible avec au plus une escale return False, -1, "" def recherche_liaison(table_tarifs, ville_depart, ville_arrivee): """ @param table_tarifs: dictionnaire tel que table[ville_depart] = liste des liaisons [(ville_arrivee, tarif),...] @param ville_depart: ville de départ @param arrivee: ville d'arrivée @return: recherche si une lisaison avec une escale au plus existe entre les villes depart et arrivee si plusieurs liaisons existent on retourne la moins chere La fonction retourne un tuple (code du resultat, cout, escale) -1 si une des deux villes n'existe pas dans la table, -1 et "" 1 si une liaison directe existe, son prix et "" 0 si aucun liaison n'existe, -1, "" 2 si une liaison avec une escale existe, son prix total et l'escale """ # verirification de la coherence des donnees if ville_depart not in table_tarifs: # si la ville de départ n'est pas dans la table return -1, -1, "" # recherche d'une liaison directe direct, cout = liaison_directe(table_tarifs, ville_depart, arrivee) if direct: return 1, cout, "" # initialisation du resultat optimal sinon coutmin = maxsize code_escale = 0 # recherche d'une liaison avec escale for dest, cout_portion1 in table_tarifs[ville_depart]: # recherche d'une liaison entre l'escale potentielle et l'arrivee direct, cout_portion2 = liaison_directe(table_tarifs, dest, arrivee) if direct: # il y a une liaison directe # liaison directe entre dest et arrivee code_escale = 2 cout_total = cout_portion2 + cout_portion1 # recherche de la liaison de cout minimal if cout_total < coutmin: escale = dest coutmin = cout_total if code_escale == 2: # on a trouve une liaison avec escale return 2, coutmin, escale # sinon pas de liaison possible avec au plus une escale return 0, -1, "" if __name__ == '__main__': # definition du dictionnaire des liaisons existantes tableTarif = dict(Nancy=[("Paris", 250), ("Toulouse", 300), ("Ajaccio", 450)], Paris=[("Rome", 150), ("Madrid", 180), ("Londres", 120), ("Amsterdam", 170), ("Nancy", 250)], Toulouse=[("Biarritz", 100), ("Madrid", 120), ("Nancy", 300)], Madrid=[("Barcelone", 120), ("Las_Palmas", 500), ("Paris", 180), ("Toulouse", 120)], Londres=[("Amsterdam", 130), ("Edimbourg", 150), ("Paris", 120)], Rome=[("Paris", 150)], Ajaccio=[("Nancy", 450)], Amsterdam=[("Paris", 170), ("Londres", 130)], Edimbourg=[("Londres", 130)], Biarritz=[("Toulouse", 100)], Barcelone=[("Madrid", 120)], Las_Palmas=[("Madrid", 120)]) # a tester depart = "Nancy" arrivee = "Paris" code, prix, escale = recherche_liaison(tableTarif, depart, arrivee) if code == 1: print("Liaison directe entre ", depart, " et ", arrivee, "de cout : ", prix, " euros") elif code == 2: print("Liaison avec escale à ", escale, " entre ", depart, " et ", arrivee, "de cout : ", prix, " euros") else: print("pas de liaison possible avec au plus une escale entre ", depart, " et ", arrivee) depart = "Las Palmas" arrivee= "Barcelone" code, prix, escale = recherche_liaison(tableTarif, depart, arrivee) if code == 1: print("Liaison directe entre ", depart, " et ", arrivee, "de cout : ", prix, " euros") elif code == 2: print("Liaison avec escale à ", escale, " entre ", depart, " et ", arrivee, "de cout : ", prix, " euros") else: print("pas de laison possible avec au plus une escale entre ", depart, " et ", arrivee) depart = "Nancy" arrivee = "Madrid" code, prix, escale = recherche_liaison(tableTarif, depart, arrivee) if code == 1: print("Liaison directe entre ", depart, " et ", arrivee, "de cout : ", prix, " euros") elif code == 2: print("Liaison avec escale à ", escale, " entre ", depart, " et ", arrivee, "de cout : ", prix, " euros") else: print("pas de laison possible avec au plus une escale entre ", depart, " et ", arrivee)