Reconstruire tous les chemins

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

Énoncé

Écrire la fonction table_des_routes(R, source) affichant les itinéraires minimaux et les distances pour toutes les destinations accessibles.

Corrigé

def table_des_routes(R: dict, source) -> None:
    # Exécution de Dijkstra
    dist, pere = dijkstra(R, source)
    # Reconstitution des chemins
    for v in sorted(R, key=lambda x: dist[x]):
        if dist[v] == float("inf"):
            print(f"{v} : Inaccessible")
        elif v != source:
            # Remonter l'arbre des pères (Chapitre 13)
            c = [v]
            while c[-1] != source:
                c.append(pere[c[-1]])
            c.reverse()
            print(f"{v} : distance {dist[v]} via {' -> '.join(c)}")

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.