TP4

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

Le fait de tester toutes vos créations n'est plus explicitement demandé car cela doit encore & toujours être fait.

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).

Si on le souhaite, on peut considérer qu'il peut y avoir plusieurs arcs entre deux mêmes sommets. La représentation des graphes doit alors en tenir compte.

Mais ceci n'et pas obligatoire.

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}]

Les routes sont à double sens (il ne faut pas se fier aux appellations "départ" & "arrivée").