TP4

Le but de ce TP est d'appliquer la théorie des flots dans les graphes à des problèmes concrets.

On commencera par implémenter l'algorithme des graphes d'écarts. Il faut pour cela utiliser un algorithme de (plus courts) chemins. On pourra reprendre celui programmé au TP 3 ou utiliser un BFS (cf TD-TP 2).

Dans un deuxième temps, on l'appliquera au problème du mariage avec les données suivantes :

CLEOPATRE = "Cleopatre"
IPHIGENIE = "Iphigenie"
JULIETTE = "Juliette"
FANNY = "Fanny"
CHIMENE = "Chimene"
 
ACHILLE = "Achille"
CESAR = "Cesar"
RODRIGUE = "Rodrigue"
ROMEO = "Romeo"
MARIUS = "Marius"
 
LES_COUPLES = [(CLEOPATRE, ACHILLE), (CLEOPATRE, CESAR), (CLEOPATRE, ROMEO), 
               (IPHIGENIE, ACHILLE), (JULIETTE, CESAR), (JULIETTE, RODRIGUE), (JULIETTE, ROMEO),
               (FANNY, CESAR), (FANNY, MARIUS), (CHIMENE, RODRIGUE), (CHIMENE, ROMEO)]

On résoudra après le problème de "la bataille de la Marne", en supposant que,

• Au temps 0, on a autant de taxis que nécessaire dans la ville 14 ("Paris").
• Au temps 50, il faut qu'il y en ait le plus possible dans la ville 0 ("La Marne").
• Chaque ville (intermédiaire) a 10 places de parking.
• Les routes sont données dans le tableau suivant :

LES_ROUTES = [{'depart': 0, 'capacite': 2, 'arrivee': 1, 'longueur': 5},
{'depart': 0, 'capacite': 3, 'arrivee': 2, 'longueur': 3},
{'depart': 0, 'capacite': 6, 'arrivee': 1, 'longueur': 6},
{'depart': 1, 'capacite': 3, 'arrivee': 2, 'longueur': 6},
{'depart': 1, 'capacite': 7, 'arrivee': 4, 'longueur': 7},
{'depart': 1, 'capacite': 6, 'arrivee': 2, 'longueur': 7},
{'depart': 2, 'capacite': 7, 'arrivee': 4, 'longueur': 4},
{'depart': 2, 'capacite': 6, 'arrivee': 4, 'longueur': 8},
{'depart': 2, 'capacite': 2, 'arrivee': 5, 'longueur': 5},
{'depart': 3, 'capacite': 7, 'arrivee': 5, 'longueur': 5},
{'depart': 3, 'capacite': 3, 'arrivee': 5, 'longueur': 4},
{'depart': 3, 'capacite': 7, 'arrivee': 6, 'longueur': 4},
{'depart': 4, 'capacite': 7, 'arrivee': 5, 'longueur': 8},
{'depart': 4, 'capacite': 8, 'arrivee': 7, 'longueur': 3},
{'depart': 4, 'capacite': 4, 'arrivee': 7, 'longueur': 3},
{'depart': 5, 'capacite': 8, 'arrivee': 6, 'longueur': 8},
{'depart': 5, 'capacite': 4, 'arrivee': 7, 'longueur': 7},
{'depart': 5, 'capacite': 4, 'arrivee': 6, 'longueur': 5},
{'depart': 6, 'capacite': 5, 'arrivee': 9, 'longueur': 3},
{'depart': 6, 'capacite': 5, 'arrivee': 7, 'longueur': 3},
{'depart': 6, 'capacite': 7, 'arrivee': 8, 'longueur': 3},
{'depart': 7, 'capacite': 2, 'arrivee': 8, 'longueur': 8},
{'depart': 7, 'capacite': 2, 'arrivee': 10, 'longueur': 5},
{'depart': 7, 'capacite': 7, 'arrivee': 10, 'longueur': 4},
{'depart': 8, 'capacite': 3, 'arrivee': 11, 'longueur': 4},
{'depart': 8, 'capacite': 5, 'arrivee': 9, 'longueur': 3},
{'depart': 8, 'capacite': 8, 'arrivee': 10, 'longueur': 3},
{'depart': 9, 'capacite': 1, 'arrivee': 11, 'longueur': 8},
{'depart': 9, 'capacite': 4, 'arrivee': 12, 'longueur': 3},
{'depart': 9, 'capacite': 1, 'arrivee': 11, 'longueur': 7},
{'depart': 10, 'capacite': 5, 'arrivee': 12, 'longueur': 7},
{'depart': 10, 'capacite': 3, 'arrivee': 13, 'longueur': 3},
{'depart': 10, 'capacite': 7, 'arrivee': 11, 'longueur': 4},
{'depart': 11, 'capacite': 4, 'arrivee': 14, 'longueur': 8},
{'depart': 11, 'capacite': 2, 'arrivee': 12, 'longueur': 3},
{'depart': 11, 'capacite': 6, 'arrivee': 14, 'longueur': 6},
{'depart': 12, 'capacite': 5, 'arrivee': 13, 'longueur': 6},
{'depart': 12, 'capacite': 2, 'arrivee': 14, 'longueur': 7},
{'depart': 12, 'capacite': 2, 'arrivee': 14, 'longueur': 6},
{'depart': 13, 'capacite': 2, 'arrivee': 14, 'longueur': 5},
{'depart': 13, 'capacite': 2, 'arrivee': 14, 'longueur': 3},
{'depart': 13, 'capacite': 8, 'arrivee': 14, 'longueur': 6}]