Chapitre 2 : Internet.

plus_court_chemin(graphe, "a", "p")

import math class Graphe: def __init__(self): self.adjacences = {} def _assure_sommet(self, s): if s not in self.adjacences: self.adjacences[s] = {} def ajout_arete(self, u, v, poids): self._assure_sommet(u) self._assure_sommet(v) self.adjacences[u][v] = poids self.adjacences[v][u] = poids def sommets(self): return list(self.adjacences.keys()) def sommets_adjacents(self, s): return list(self.adjacences[s].keys()) def distance_deux_sommets(self, u, v): if u == v: return 0 return self.adjacences[u][v] graphe = Graphe() # --- Arêtes du graphe --- graphe.ajout_arete("a","b",7) graphe.ajout_arete("b","c",14) graphe.ajout_arete("c","d",26) graphe.ajout_arete("d","l",14) graphe.ajout_arete("l","e",6) graphe.ajout_arete("e","f",3) graphe.ajout_arete("f","m",9) graphe.ajout_arete("a","i",33) graphe.ajout_arete("h","i",5) graphe.ajout_arete("h","o",13) graphe.ajout_arete("p","o",4) graphe.ajout_arete("i","c",23) graphe.ajout_arete("i","j",6) graphe.ajout_arete("i","p",16) graphe.ajout_arete("p","q",3) graphe.ajout_arete("p","v",9) graphe.ajout_arete("k","l",6) graphe.ajout_arete("d","e",12) graphe.ajout_arete("f","g",17) graphe.ajout_arete("j","k",19) graphe.ajout_arete("l","m",14) graphe.ajout_arete("m","n",21) graphe.ajout_arete("q","r",16) graphe.ajout_arete("s","t",22) graphe.ajout_arete("t","u",13) graphe.ajout_arete("v","w",15) graphe.ajout_arete("w","x",20) graphe.ajout_arete("x","y",9) graphe.ajout_arete("y","z",18) graphe.ajout_arete("z","aa",12) graphe.ajout_arete("aa","ab",23) graphe.ajout_arete("ac","ad",14) graphe.ajout_arete("ad","ae",10) graphe.ajout_arete("ae","af",19) graphe.ajout_arete("af","ag",24) graphe.ajout_arete("ag","ah",11) graphe.ajout_arete("a","h",20) graphe.ajout_arete("b","i",17) graphe.ajout_arete("c","j",18) graphe.ajout_arete("d","k",21) graphe.ajout_arete("g","n",16) graphe.ajout_arete("j","q",14) graphe.ajout_arete("k","r",22) graphe.ajout_arete("l","s",12) graphe.ajout_arete("m","t",17) graphe.ajout_arete("n","u",19) graphe.ajout_arete("o","v",10) graphe.ajout_arete("p","w",23) graphe.ajout_arete("q","x",12) graphe.ajout_arete("r","y",15) graphe.ajout_arete("s","z",18) graphe.ajout_arete("t","aa",9) graphe.ajout_arete("u","ab",20) graphe.ajout_arete("v","ac",16) graphe.ajout_arete("w","ad",11) graphe.ajout_arete("x","ae",24) graphe.ajout_arete("y","af",14) graphe.ajout_arete("z","ag",22) graphe.ajout_arete("aa","ah",13) def plus_court_chemin(graphe, point_depart, point_arrive): """ Retourne une chaîne "u-v-w-..." correspondant au plus court chemin. Affiche pas à pas les actions de l'algorithme. """ # Vérifications if point_depart not in graphe.adjacences or point_arrive not in graphe.adjacences: print(f"[ERREUR] Sommet absent: depart={point_depart!r} ou arrive={point_arrive!r}") return "" if point_depart == point_arrive: print(f"[INFO] Départ = Arrivée = {point_depart}. Chemin trivial.") return str(point_depart) # Initialisation dist = {s: math.inf for s in graphe.sommets()} pred = {s: None for s in graphe.sommets()} dist[point_depart] = 0 visites = set() print("=== Dijkstra (version simple sans heap) ===") print(f"Départ = {point_depart}, Arrivée = {point_arrive}") print("Distances initiales :", dist) print("===========================================") while len(visites) < len(graphe.sommets()): # choisir le sommet non visité avec la plus petite distance u = None min_dist = math.inf for s in graphe.sommets(): if s not in visites and dist[s] < min_dist: min_dist = dist[s] u = s if u is None: # plus de sommets atteignables break print(f"\n[Étape] On choisit '{u}' (distance = {dist[u]})") visites.add(u) if u == point_arrive: print("[Arrêt] Arrivée atteinte, on reconstruit le chemin.") break # mise à jour des distances des voisins for v in graphe.sommets_adjacents(u): if v in visites: print(f" - voisin '{v}' déjà visité, ignoré") continue w = graphe.adjacences[u][v] new_d = dist[u] + w print(f" - arête {u}--{v} (poids={w}), dist[{v}] actuelle={dist[v]}, nouvelle={new_d}") if new_d < dist[v]: dist[v] = new_d pred[v] = u print(f" -> amélioration: dist[{v}] = {new_d}, préd[{v}] = {u}") else: print(f" -> pas d'amélioration pour {v}") # Reconstruction du chemin if dist[point_arrive] == math.inf: print(f"\n[Aucun chemin] Impossible d'atteindre {point_arrive} depuis {point_depart}.") return "" chemin = [] cur = point_arrive while cur is not None: chemin.append(cur) cur = pred[cur] chemin.reverse() print("\n=== Résultat ===") print(f"Distance totale: {dist[point_arrive]}") print(f"Chemin: {'-'.join(chemin)}") print("================") print("-".join(chemin)) return "-".join(chemin) plus_court_chemin(graphe, "a", "p")

# Tests