Le métro, correspondances comprises

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 14 — Plus courts chemins : Dijkstra et au-delà

É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 $B$ en deux sommets $B_{1}$ (ligne 1) et $B_{2}$ (ligne 2). On introduit un arc bidirectionnel entre $B_{1}$ et $B_{2}$ 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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.