informatique (tronc commun des prépas scientifiques) · Chapitre 14 · Exercice de TD
Le métro, correspondances comprises
Plus courts chemins : Dijkstra et au-delà · niveau 2
Énoncé
Définir un réseau simple à deux lignes se croisant en une station et modéliser le temps de correspondance.
Corrigé
On duplique la station de correspondance en deux sommets (ligne 1) et (ligne 2). On introduit un arc bidirectionnel entre et de poids égal au temps de correspondance (ex: 5 minutes) :
M = {
"A1": {"B1": 2},
"B1": {"A1": 2, "C1": 2, "B2": 5},
"C1": {"B1": 2},
"D2": {"B2": 2},
"B2": {"D2": 2, "E2": 2, "B1": 5},
"E2": {"B2": 2}
}
# trajet A1 -> E2 : A1 -> B1 (2) -> B2 (5) -> E2 (2) = 9 minutes.