Problème — Le plus court trajet dans un réseau de métro

Les graphes · niveau 1 (application)

Énoncé

Problème — Le plus court trajet dans un réseau de métro.

Un réseau de métro relie des stations. On le modélise par un graphe non orienté metro (listes d'adjacence). Écrire une fonction trajet(metro, depart, arrivee) qui affiche le plus court trajet (en nombre de stations) et indique le nombre de changements minimal de lignes, en supposant un réseau non pondéré (toutes les liaisons comptent pour 1).

Corrigé

Le réseau étant non pondéré, le plus court trajet en nombre de stations s'obtient par un BFS mémorisant les prédécesseurs, comme pour le plus court chemin en nombre d'arêtes vu plus haut. On réutilise cette logique et on renvoie la liste des stations traversées.


from collections import deque

def trajet(metro, depart, arrivee):
    if depart == arrivee:
        return [depart]
    predecesseur = {depart: None}
    file = deque([depart])
    while file:
        station = file.popleft()
        for suivante in metro[station]:
            if suivante not in predecesseur:
                predecesseur[suivante] = station
                if suivante == arrivee:
                    chemin = [arrivee]
                    while predecesseur[chemin[-1]] is not None:
                        chemin.append(predecesseur[chemin[-1]])
                    chemin.reverse()
                    return chemin
                file.append(suivante)
    return None

metro = {
    "Chatelet":   ["Louvre", "Gare", "Bastille"],
    "Louvre":     ["Chatelet", "Concorde"],
    "Concorde":   ["Louvre", "Etoile"],
    "Etoile":     ["Concorde"],
    "Gare":       ["Chatelet"],
    "Bastille":   ["Chatelet", "Nation"],
    "Nation":     ["Bastille"],
}
print(trajet(metro, "Etoile", "Nation"))
# ['Etoile', 'Concorde', 'Louvre', 'Chatelet', 'Bastille', 'Nation']

Le BFS garantit le trajet de longueur minimale en nombre de stations. La complexité est $O (n + m)$ . Pour modéliser des durées différentes entre stations ou pénaliser les changements de ligne, il faudrait passer à un graphe pondéré et employer l'algorithme de Dijkstra, généralisation pondérée du BFS.