informatique (tronc commun des prépas scientifiques) · Chapitre 14 · Application directe du cours
Reconstruire tous les chemins
Plus courts chemins : Dijkstra et au-delà · niveau 1 (application)
É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)}")Exercices semblables
- A* contre Dijkstra, le match mesuré corrigé
- L'heuristique qui ment corrigé
- Une source vers tous, tous vers un, un vers un corrigé
- Dérouler Dijkstra corrigé
- Le détour gagnant corrigé