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

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.