Chapitre 20 : Les graphes pondérés.
Introduction :
Un graphe pondéré est un graphe dans lequel chaque arête (ou arc) est associée à une valeur numérique appelée poids.
Les graphes pondérés sont utilisés lorsque les relations entre sommets n’ont pas toutes la même importance, par exemple pour modéliser des trajets routiers ou des réseaux de transport.
1. Graphes pondérés:
Un graphe orienté ou non orienté peut être pondéré.
Cette pondération peut représenter des valeurs réelles telles que:
- une distance entre deux points
- un temps mis pour un trajet
- le nombre de fois où deux personnes ont échangé sur un réseau social
- ...
Pour représenter un graphe pondéré en Python, on peut utiliser un dictionnaire d’adjacence où :
- les clés sont les sommets,
- les valeurs sont des dictionnaires associant chaque voisin à un poids.
class GrapheNonOrientePondere:
def __init__(self):
self.aretes = {}
def ajouter_sommet(self, sommet):
if sommet not in self.aretes:
self.aretes[sommet] = {}
def ajouter_arete(self, sommet1, sommet2, poids):
self.ajouter_sommet(sommet1)
self.ajouter_sommet(sommet2)
self.aretes[sommet1][sommet2] = poids
self.aretes[sommet2][sommet1] = poidsIci, une arête entre deux sommets est associée à un poids. Comme le poids est ajouté dans les deux sens, le graphe est non orienté pondéré.
Exemple de structure obtenue :
{
'A': {'B': 5, 'C': 2},
'B': {'A': 5},
'C': {'A': 2}
}2. Exercice : Graphe non oriente pondere
Dans un fichier , importer le fichier structures.py puis copier/coller les lignes de commandes
suivantes permettant d'implémenter le graphe suivant en tant qu'objet GrapheNonOrientePondere.
-
Écrire les méthodes suivantes :
distance(self, sommet1, sommet2) -> float(unintest accepté)sommets_adjacents(self, sommet1: str, sommet2: str) -> bool
-
Écrire la méthode
longueur_chaine(self, liste)dont les caractéristiques sont les suivantes:listecorrespond à une liste de string correspondant aux sommets.- elle renvoie un tuple formé d'un booléen puis d'un integer :
- elle renvoie
(False,0)si un sommet de la liste n'existe pas. - elle renvoie
(False,1)si la chaine correspondante à la liste n'existe pas. - elle renvoie
(True,x)avecxcorrespondant à la longueur de la chaine sinon.
- elle renvoie
class GrapheNonOrientePondere:
def __init__(self) -> None:
self.aretes = {}
def ajouter_sommet(self, sommet: str) -> None:
if sommet not in self.aretes:
self.aretes[sommet] = {}
def ajouter_arete(self, sommet1: str, sommet2: str, poids: float) -> None:
self.ajouter_sommet(sommet1)
self.ajouter_sommet(sommet2)
self.aretes[sommet1][sommet2] = poids
self.aretes[sommet2][sommet1] = poids
def sommets_adjacents(self, sommet1: str, sommet2: str) -> bool:
"""
Renvoie True si sommet1 et sommet2 sont adjacents (il existe une arête entre eux).
Contraintes :
- Si sommet1 n existe pas, renvoyer False.
- L arête peut être lue dans les deux sens, mais le graphe stocke deja les deux sens.
"""
...
def distance(self, sommet1: str, sommet2: str) -> float:
"""
Renvoie la distance (poids) de l arête sommet1 -- sommet2.
Retour :
- le poids (float ou int accepte) si l arête existe.
Contraintes :
- Si un sommet n existe pas, renvoyer -1.
- Si l arête n existe pas, renvoyer -1.
"""
...
def longueur_chaine(self, liste: list) -> tuple:
"""
Calcule la longueur d une chaine décrite par une liste de sommets.
Parametre :
- liste : liste de str correspondant aux sommets, par exemple ["A","B","C"].
Retour :
- (False, 0) si au moins un sommet de la liste n existe pas dans le graphe.
- (False, 1) si la chaine correspondante n existe pas (au moins une arête manquante).
- (True, x) si toutes les arêtes existent, avec x la somme des poids.
Exemple :
- si A--B vaut 3 et B--C vaut 7, alors ["A","B","C"] renvoie (True, 10).
"""
assert type(liste) == list, "liste doit être une liste"
assert len(liste) > 0, "une chaine doit avoir au minimum 1 sommet"
...
# Construction du graphe
graphe1 = GrapheNonOrientePondere()
sommets = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "S", "Q", "R", "P"]
for s in sommets:
graphe1.ajouter_sommet(s)
graphe1.ajouter_arete("A", "B", 3)
graphe1.ajouter_arete("B", "C", 7)
graphe1.ajouter_arete("C", "D", 6)
graphe1.ajouter_arete("D", "E", 2)
graphe1.ajouter_arete("E", "F", 8)
graphe1.ajouter_arete("F", "G", 4)
graphe1.ajouter_arete("G", "H", 5)
graphe1.ajouter_arete("H", "I", 9)
graphe1.ajouter_arete("I", "J", 1)
graphe1.ajouter_arete("J", "K", 7)
graphe1.ajouter_arete("K", "L", 3)
graphe1.ajouter_arete("L", "M", 5)
graphe1.ajouter_arete("M", "N", 6)
graphe1.ajouter_arete("N", "O", 4)
graphe1.ajouter_arete("O", "S", 8)
graphe1.ajouter_arete("Q", "S", 8)
graphe1.ajouter_arete("C", "E", 8)
graphe1.ajouter_arete("A", "F", 10)
graphe1.ajouter_arete("E", "I", 6)
graphe1.ajouter_arete("D", "K", 2)
graphe1.ajouter_arete("H", "N", 9)
graphe1.ajouter_arete("M", "Q", 2)
graphe1.ajouter_arete("J", "R", 3)
graphe1.ajouter_arete("K", "R", 4)
graphe1.ajouter_arete("L", "R", 2)
graphe1.ajouter_arete("R", "M", 2)
graphe1.ajouter_arete("R", "N", 4)
graphe1.ajouter_arete("B", "E", 3)
graphe1.ajouter_arete("H", "P", 4)
graphe1.ajouter_arete("P", "N", 2)
# Prints de visualisation
print("Adjacents A-B :", graphe1.sommets_adjacents("A", "B"))
print("Adjacents A-C :", graphe1.sommets_adjacents("A", "C"))
print("Distance A-B :", graphe1.distance("A", "B"))
print("Distance B-E :", graphe1.distance("B", "E"))
print("Longueur A-B-C :", graphe1.longueur_chaine(["A", "B", "C"]))
print("Longueur A-C :", graphe1.longueur_chaine(["A", "C"]))
print("Longueur X-A :", graphe1.longueur_chaine(["X", "A"]))
print("Longueur A-B-C-D-K-R-N-O-S-Q :", graphe1.longueur_chaine(["A", "B", "C", "D", "K", "R", "N", "O", "S", "Q"]))
Tests :
Affichage :
Console:
>>>
3. Exercice : Reseau a sens unique et couts
On modélise un réseau de trajets à sens unique (graphe orienté pondéré).
Chaque arc X -> Y possède un poids (un coût). Attention : X -> Y n implique pas que Y -> X existe.
Compléter les méthodes de la classe pour analyser ce réseau :
- calculer le coût total des arcs sortants et entrants d un sommet,
- trouver le successeur le moins cher d un sommet,
- trouver le sommet le plus "actif" (celui qui a le plus d arcs sortants),
- extraire tous les arcs dont le coût est inférieur ou égal à un seuil.
Exemples de résultats attendus (sur le réseau fourni dans l éditeur) :
cout_sortant_total("A") = 13
cout_entrant_total("E") = 11
successeur_le_moins_cher("E") = "D"
hub_sortant() = "E"
arcs_cout_max(2) contient ("I","J",1) et ("D","K",2)class GrapheOrientePondere:
def __init__(self) -> None:
"""
Initialise un graphe orienté pondéré.
Représentation :
- self.arcs : dict[str, dict[str, float]]
* self.arcs[u] est un dictionnaire {v: poids} pour tous les arcs u -> v.
Exemple :
- self.arcs["A"]["B"] = 3 signifie A -> B de coût 3.
"""
self.arcs: dict = {}
def ajouter_sommet(self, sommet: str) -> None:
"""
Ajoute un sommet au graphe s il n existe pas déjà.
"""
if sommet not in self.arcs:
self.arcs[sommet] = {}
def ajouter_arc(self, source: str, destination: str, poids: float) -> None:
"""
Ajoute l arc orienté source -> destination avec un poids.
Remarques :
- Les sommets sont créés automatiquement s ils n existent pas.
- Si l arc existe déjà, son poids est remplacé.
"""
self.ajouter_sommet(source)
self.ajouter_sommet(destination)
self.arcs[source][destination] = poids
def cout_sortant_total(self, sommet: str) -> float:
"""
Calcule la somme des poids des arcs sortants de sommet.
Retour :
- somme des poids (float ou int accepté) des arcs sommet -> voisin
- si le sommet n existe pas, renvoyer 0
"""
...
def cout_entrant_total(self, sommet: str) -> float:
"""
Calcule la somme des poids des arcs entrants vers sommet.
Retour :
- somme des poids (float ou int accepté) de tous les arcs u -> sommet
- si le sommet n existe pas, renvoyer 0
Indice :
- parcourir tous les sommets u du graphe et regarder si sommet est dans self.arcs[u]
"""
...
def successeur_le_moins_cher(self, sommet: str):
"""
Renvoie le successeur le moins cher de sommet.
Retour :
- un string (nom du successeur) si sommet a au moins un arc sortant
- None si le sommet n existe pas ou s il n a aucun arc sortant
Regle en cas d egalite sur le cout minimum :
- renvoyer le successeur dont le nom est le plus petit (ordre lexicographique)
Indice :
On pourra utiliser float("inf") a l initialisation
"""
...
def hub_sortant(self):
"""
Renvoie le sommet qui a le plus grand nombre d arcs sortants.
Retour :
- un string (nom du sommet)
- None si le graphe est vide
Regle en cas d egalite :
- renvoyer le sommet dont le nom est le plus petit (ordre lexicographique)
"""
...
def arcs_cout_max(self, seuil: float) -> list:
"""
Retourne la liste des arcs (source, destination, poids) dont le poids est <= seuil.
Retour :
- list[tuple[str, str, float]] (ordre quelconque)
Contraintes :
- ne pas renvoyer de doublons
- si le graphe est vide, renvoyer une liste vide
"""
...
# Construction du reseau
reseau = GrapheOrientePondere()
reseau.ajouter_arc("A", "B", 3)
reseau.ajouter_arc("B", "C", 7)
reseau.ajouter_arc("C", "D", 6)
reseau.ajouter_arc("D", "E", 2)
reseau.ajouter_arc("E", "F", 8)
reseau.ajouter_arc("F", "G", 4)
reseau.ajouter_arc("G", "H", 5)
reseau.ajouter_arc("H", "I", 9)
reseau.ajouter_arc("I", "J", 1)
reseau.ajouter_arc("J", "K", 7)
reseau.ajouter_arc("K", "L", 3)
reseau.ajouter_arc("L", "M", 5)
reseau.ajouter_arc("M", "N", 6)
reseau.ajouter_arc("N", "O", 4)
reseau.ajouter_arc("O", "S", 8)
reseau.ajouter_arc("Q", "S", 8)
reseau.ajouter_arc("E", "C", 8)
reseau.ajouter_arc("A", "F", 10)
reseau.ajouter_arc("E", "I", 6)
reseau.ajouter_arc("I", "E", 6)
reseau.ajouter_arc("D", "K", 2)
reseau.ajouter_arc("H", "N", 9)
reseau.ajouter_arc("M", "Q", 2)
reseau.ajouter_arc("J", "R", 3)
reseau.ajouter_arc("K", "R", 4)
reseau.ajouter_arc("L", "R", 2)
reseau.ajouter_arc("R", "M", 2)
reseau.ajouter_arc("R", "N", 4)
reseau.ajouter_arc("B", "E", 3)
reseau.ajouter_arc("H", "P", 4)
reseau.ajouter_arc("P", "N", 2)
reseau.ajouter_arc("E", "D", 3)
# Prints de visualisation
sommet_teste = "A"
print(f"Cout sortant total {sommet_teste} :", reseau.cout_sortant_total(sommet_teste))
print(f"Cout entrant total {sommet_teste} :", reseau.cout_entrant_total(sommet_teste))
print(f"Successeur le moins cher de {sommet_teste} :", reseau.successeur_le_moins_cher(sommet_teste))
print("Hub sortant :", reseau.hub_sortant())
seuil = 2
print(f"Arcs de cout <= {seuil} :")
for tup in sorted(reseau.arcs_cout_max(seuil)):
print(" ",tup)
Tests :
Affichage :
Console:
>>>
4. Exercice :
On considère la carte routière ci-dessous :
- Copier/coller la classe
GrapheNonOrientePonderecomplète de l'exercice 16. -
Compléter la ligne
trajet_nice_marseille = ...afin qu'elle contienne le tuple renvoyé par la méthodelongueur_chainepour le trajet Nice -> Cannes -> Le Luc -> Brignoles -> Aix-en-Provence -> Marseille -
Écrire la fonction
temps_mis(graphe, chaine: list) -> strqui prend en paramètre un graphe et une listechainede strings correpondants à des villes.Elle retournera un string exprimant le temps mis en heures et en minutes ou un string indiquant que le chemin n'existe pas comme ci-dessous.
Exemple:
>>> temps_mis(graphe, ["Nice","Cannes","Le Luc"]) "1h22min" >>> temps_mis(graphe, ["Nice","Paris","Brest"]) "La chaine Nice - Paris - Brest n'existe pas."
class GrapheNonOrientePondere:
def __init__(self) -> None:
self.aretes = {}
def ajouter_sommet(self, sommet: str) -> None:
if sommet not in self.aretes:
self.aretes[sommet] = {}
def ajouter_arete(self, sommet1: str, sommet2: str, poids: float) -> None:
self.ajouter_sommet(sommet1)
self.ajouter_sommet(sommet2)
self.aretes[sommet1][sommet2] = poids
self.aretes[sommet2][sommet1] = poids
def sommets_adjacents(self, sommet1: str, sommet2: str) -> bool:
"""
Renvoie True si sommet1 et sommet2 sont adjacents (il existe une arête entre eux).
Contraintes :
- Si sommet1 n existe pas, renvoyer False.
- L arête peut être lue dans les deux sens, mais le graphe stocke deja les deux sens.
"""
...
def distance(self, sommet1: str, sommet2: str) -> float:
"""
Renvoie la distance (poids) de l arête sommet1 -- sommet2.
Retour :
- le poids (float ou int accepte) si l arête existe.
Contraintes :
- Si un sommet n existe pas, renvoyer -1.
- Si l arête n existe pas, renvoyer -1.
"""
...
def longueur_chaine(self, liste: list) -> tuple:
"""
Calcule la longueur d une chaine décrite par une liste de sommets.
Parametre :
- liste : liste de str correspondant aux sommets, par exemple ["A","B","C"].
Retour :
- (False, 0) si au moins un sommet de la liste n existe pas dans le graphe.
- (False, 1) si la chaine correspondante n existe pas (au moins une arête manquante).
- (True, x) si toutes les arêtes existent, avec x la somme des poids.
Exemple :
- si A--B vaut 3 et B--C vaut 7, alors ["A","B","C"] renvoie (True, 10).
"""
assert type(liste) == list, "liste doit être une liste"
assert len(liste) > 0, "une chaine doit avoir au minimum 1 sommet"
...
routes = GrapheNonOrientePondere()
routes.ajouter_arete("Cannes","Nice",27)
routes.ajouter_arete("Nice","Menton",34)
routes.ajouter_arete("Grasse","Cannes",32)
routes.ajouter_arete("Le Luc","Cannes",55)
routes.ajouter_arete("Toulon","Le Luc",62)
routes.ajouter_arete("Brignoles","Le Luc",37)
routes.ajouter_arete("Aix-en-Provence","Brignoles",35)
routes.ajouter_arete("Aubagne","Toulon",35)
routes.ajouter_arete("Marseille","Aubagne",23)
routes.ajouter_arete("Marseille","Aix-en-Provence",28)
routes.ajouter_arete("Aix-en-Provence","Aubagne",28)
routes.ajouter_arete("Salon-de-Provence","Aix-en-Provence",25)
routes.ajouter_arete("Arles","Salon-de-Provence",30)
routes.ajouter_arete("Avignon","Salon-de-Provence",45)
routes.ajouter_arete("Nîmes","Arles",27)
routes.ajouter_arete("Nîmes","Orange",41)
routes.ajouter_arete("Avignon","Orange",30)
routes.ajouter_arete("Montpellier","Nîmes",47)
routes.ajouter_arete("Montélimar","Orange",40)
routes.ajouter_arete("Montélimar","Valence",43)
routes.ajouter_arete("Les Mées","Gap",52)
routes.ajouter_arete("Manosque","Les Mées",22)
routes.ajouter_arete("Aix-en-Provence","Manosque",52)
routes.ajouter_arete("Grenoble","Gap",113)
routes.ajouter_arete("Béziers","Montpellier",61)
routes.ajouter_arete("Givors","Valence",61)
routes.ajouter_arete("Givors","Lyon",28)
routes.ajouter_arete("Saint-Étienne","Givors",38)
routes.ajouter_arete("Clermont-Ferrand","Saint-Étienne",103)
routes.ajouter_arete("Béziers","Clermont-l'Hérault",51)
routes.ajouter_arete("Clermont-l'Hérault","Montpellier",41)
routes.ajouter_arete("Clermont-Ferrand","Clermont-l'Hérault",209)
routes.ajouter_arete("Narbonne","Béziers",30)
routes.ajouter_arete("Carcassonne","Narbonne",43)
routes.ajouter_arete("Perpignan","Narbonne",45)
routes.ajouter_arete("Toulouse","Carcassonne",68)
routes.ajouter_arete("Tarbes","Toulouse",107)
routes.ajouter_arete("Pau","Tarbes",36)
routes.ajouter_arete("Biarritz","Pau",86)
routes.ajouter_arete("Biarritz","Bordeaux",133)
routes.ajouter_arete("Bordeaux","Brive-la-Gaillarde",137)
routes.ajouter_arete("Brive-la-Gaillarde","Clermont-Ferrand",126)
routes.ajouter_arete("Limoges","Brive-la-Gaillarde",64)
routes.ajouter_arete("Montluçon","Clermont-Ferrand",79)
routes.ajouter_arete("Angoulême","Limoges",86)
routes.ajouter_arete("Saintes","Angoulême",70)
routes.ajouter_arete("Saintes","Bordeaux",83)
routes.ajouter_arete("Angoulême","Limalonges",46)
routes.ajouter_arete("Limalonges","Poitiers",46)
routes.ajouter_arete("La Rochelle","Saintes",55)
routes.ajouter_arete("La Rochelle","Niort",52)
routes.ajouter_arete("Saintes","Niort",56)
routes.ajouter_arete("Niort","Poitiers",62)
routes.ajouter_arete("Niort","Limalonges",64)
routes.ajouter_arete("Montauban","Toulouse",44)
routes.ajouter_arete("Montauban","Brive-la-Gaillarde",98)
routes.ajouter_arete("Poitiers","Tours",78)
routes.ajouter_arete("La Roche-sur-Yon","Niort",69)
routes.ajouter_arete("Nantes","La Roche-sur-Yon",57)
routes.ajouter_arete("La Roche-sur-Yon","Cholet",54)
routes.ajouter_arete("Cholet","Parthenay",55)
routes.ajouter_arete("Parthenay","Poitiers",60)
routes.ajouter_arete("Nantes","Angers",66)
routes.ajouter_arete("Cholet","Angers",46)
routes.ajouter_arete("Angers","Saumur",38)
routes.ajouter_arete("Saumur","Tours",45)
routes.ajouter_arete("Parthenay","Saumur",95)
routes.ajouter_arete("Saint-Nazaire","Nantes",57)
routes.ajouter_arete("La Roche-Bernard","Saint-Nazaire",46)
routes.ajouter_arete("Savenay","Nantes",37)
routes.ajouter_arete("Saint-Nazaire","Savenay",25)
routes.ajouter_arete("Pontchâteau","Savenay",13)
routes.ajouter_arete("La Roche-Bernard","Pontchâteau",17)
routes.ajouter_arete("Vannes","La Roche-Bernard",38)
routes.ajouter_arete("Vannes","Redon",57)
routes.ajouter_arete("Redon","Rennes",57)
routes.ajouter_arete("La Roche-Bernard","Redon",34)
routes.ajouter_arete("Lorient","Vannes",47)
routes.ajouter_arete("Quimper","Lorient",50)
routes.ajouter_arete("Quimper","Châteaulin",22)
routes.ajouter_arete("Brest","Châteaulin",38)
routes.ajouter_arete("Châteaulin","Carhaix-Plouguer",33)
routes.ajouter_arete("Carhaix-Plouguer","Lorient",67)
routes.ajouter_arete("Brest","Morlaix",47)
routes.ajouter_arete("Morlaix","Saint-Brieuc",70)
routes.ajouter_arete("Saint-Brieuc","Loudéac",43)
routes.ajouter_arete("Saint-Brieuc","Rennes",77)
routes.ajouter_arete("Carhaix-Plouguer","Loudéac",66)
routes.ajouter_arete("Pontivy","Loudéac",22)
routes.ajouter_arete("Pontivy","Vannes",46)
routes.ajouter_arete("Lorient","Pontivy",47)
routes.ajouter_arete("Rennes","Angers",103)
routes.ajouter_arete("Rennes","Laval",66)
routes.ajouter_arete("Laval","Le Mans",56)
routes.ajouter_arete("Angers","Le Mans",66)
routes.ajouter_arete("Le Mans","Tours",72)
routes.ajouter_arete("Saint-Brieuc","Saint-Malo",64)
routes.ajouter_arete("Saint-Malo","Avranches",49)
routes.ajouter_arete("Rennes","Avranches",62)
routes.ajouter_arete("Laval","Mayenne",26)
routes.ajouter_arete("Mayenne","Alençon",63)
routes.ajouter_arete("Alençon","Le Mans",42)
routes.ajouter_arete("Avranches","Caen",68)
routes.ajouter_arete("Saint-Malo","Rennes",51)
routes.ajouter_arete("Rennes","Fougères",42)
routes.ajouter_arete("Fougères","Mayenne",60)
routes.ajouter_arete("Avranches","Fougères",26)
routes.ajouter_arete("Caen","Alençon",77)
routes.ajouter_arete("Caen","Le Havre",64)
routes.ajouter_arete("Le Havre","Rouen",60)
routes.ajouter_arete("Caen","Rouen",85)
routes.ajouter_arete("Rouen","Evreux",45)
routes.ajouter_arete("Evreux","Dreux",36)
routes.ajouter_arete("Dreux","Chartres",42)
routes.ajouter_arete("Caen","Evreux",99)
routes.ajouter_arete("Alençon","Dreux",97)
routes.ajouter_arete("Le Mans","Chartres",80)
routes.ajouter_arete("Saint-Arnoult-en-Yvelines","Paris",60)
routes.ajouter_arete("Chartres","Saint-Arnoult-en-Yvelines",34)
routes.ajouter_arete("Orléans","Saint-Arnoult-en-Yvelines",66)
routes.ajouter_arete("Dreux","Paris",74)
routes.ajouter_arete("Evreux","Paris",88)
routes.ajouter_arete("Vierzon","Bourges",23)
routes.ajouter_arete("Châteauroux","Bourges",60)
routes.ajouter_arete("Châteauroux","Vierzon",40)
routes.ajouter_arete("Orléans","Vierzon",58)
routes.ajouter_arete("Blois","Chémery",38)
routes.ajouter_arete("Tours","Chémery",57)
routes.ajouter_arete("Chémery","Châteauroux",67)
routes.ajouter_arete("Chémery","Vierzon",37)
routes.ajouter_arete("Tours","Blois",42)
routes.ajouter_arete("Blois","Orléans",42)
routes.ajouter_arete("Poitiers","Le Dognon",106)
routes.ajouter_arete("Limoges","Le Dognon",33)
routes.ajouter_arete("Le Dognon","Montluçon",75)
routes.ajouter_arete("Le Dognon","Châteauroux",55)
routes.ajouter_arete("Bourges","Montluçon",66)
routes.ajouter_arete("Rouen","Neufchâtel-en-Bray",60)
routes.ajouter_arete("Neufchâtel-en-Bray","Amiens",45)
routes.ajouter_arete("Neufchâtel-en-Bray","Abbeville",63)
routes.ajouter_arete("Le Havre","Neufchâtel-en-Bray",90)
routes.ajouter_arete("Beauvais","Paris",73)
routes.ajouter_arete("Beauvais","Amiens",44)
routes.ajouter_arete("Abbeville","Amiens",35)
routes.ajouter_arete("Berck","Abbeville",22)
routes.ajouter_arete("Boulogne-sur-Mer","Berck",25)
routes.ajouter_arete("Boulogne-sur-Mer","Calais",26)
routes.ajouter_arete("Calais","Dunkerque",35)
routes.ajouter_arete("Dunkerque","Lille",56)
routes.ajouter_arete("Lille","Valenciennes",42)
routes.ajouter_arete("Saint-Quentin","Valenciennes",58)
routes.ajouter_arete("Amiens","Saint-Quentin",61)
routes.ajouter_arete("Hénin-Beaumont","Douai",10)
routes.ajouter_arete("Lens","Hénin-Beaumont",14)
routes.ajouter_arete("Arras","Hénin-Beaumont",25)
routes.ajouter_arete("Hénin-Beaumont","Lille",27)
routes.ajouter_arete("Douai","Valenciennes",34)
routes.ajouter_arete("Amiens","Arras",74)
routes.ajouter_arete("Berck","Arras",75)
routes.ajouter_arete("Arras","Lens",14)
routes.ajouter_arete("Boulogne-sur-Mer","Lens",80)
routes.ajouter_arete("Beauvais","Compiègne",49)
routes.ajouter_arete("Compiègne","Saint-Quentin",60)
routes.ajouter_arete("Paris","Compiègne",72)
routes.ajouter_arete("Compiègne","Soissons",41)
routes.ajouter_arete("Soissons","Reims",56)
routes.ajouter_arete("Paris","Soissons",91)
routes.ajouter_arete("Soissons","Laon",31)
routes.ajouter_arete("Paris","Sens",92)
routes.ajouter_arete("Valenciennes","Maubeuge",32)
routes.ajouter_arete("La Capelle","Maubeuge",43)
routes.ajouter_arete("La Capelle","Charleville-Mézières",64)
routes.ajouter_arete("Saint-Quentin","La Capelle",57)
routes.ajouter_arete("Laon","La Capelle",58)
routes.ajouter_arete("Reims","Charleville-Mézières",61)
routes.ajouter_arete("Laon","Reims",43)
routes.ajouter_arete("Saint-Quentin","Laon",37)
routes.ajouter_arete("Reims","Châlons-en-Champagne",35)
routes.ajouter_arete("Châlons-en-Champagne","Vitry-le-François",27)
routes.ajouter_arete("Vitry-le-François","Saint-Dizier",27)
routes.ajouter_arete("Sommesous","Vitry-le-François",30)
routes.ajouter_arete("Paris","Sommesous",132)
routes.ajouter_arete("Sommesous","Châlons-en-Champagne",28)
routes.ajouter_arete("Troyes","Sommesous",46)
routes.ajouter_arete("Châlons-en-Champagne","Metz",101)
routes.ajouter_arete("Saint-Dizier","Chaumont",63)
routes.ajouter_arete("Saint-Dizier","Nancy",80)
routes.ajouter_arete("Sens","Troyes",50)
routes.ajouter_arete("Metz","Nancy",53)
routes.ajouter_arete("Colmar","Strasbourg",72)
routes.ajouter_arete("Mulhouse","Colmar",47)
routes.ajouter_arete("Nancy","Colmar",140)
routes.ajouter_arete("Nancy","Épinal",53)
routes.ajouter_arete("Épinal","Mulhouse",103)
routes.ajouter_arete("Vesoul","Épinal",70)
routes.ajouter_arete("Besançon","Vesoul",50)
routes.ajouter_arete("Vesoul","Belfort & Montbéliard",54)
routes.ajouter_arete("Belfort & Montbéliard","Mulhouse",36)
routes.ajouter_arete("Besançon","Belfort & Montbéliard",69)
routes.ajouter_arete("Chaumont","Vesoul",107)
routes.ajouter_arete("Dole","Besançon",47)
routes.ajouter_arete("Dijon","Dole",39)
routes.ajouter_arete("Beaune","Dijon",36)
routes.ajouter_arete("Beaune","Dole",44)
routes.ajouter_arete("Dijon","Chaumont",75)
routes.ajouter_arete("Auxerre","Pouilly-en-Auxois",116)
routes.ajouter_arete("Pouilly-en-Auxois","Dijon",55)
routes.ajouter_arete("Pouilly-en-Auxois","Beaune",29)
routes.ajouter_arete("Troyes","Chaumont",72)
routes.ajouter_arete("Sens","Auxerre",54)
routes.ajouter_arete("Montargis","Sens",51)
routes.ajouter_arete("Orléans","Montargis",59)
routes.ajouter_arete("Montargis","La Charité-sur-Loire",68)
routes.ajouter_arete("Bourges","La Charité-sur-Loire",62)
routes.ajouter_arete("La Charité-sur-Loire","Nevers",22)
routes.ajouter_arete("Nevers","Moulins",55)
routes.ajouter_arete("Montluçon","Moulins",55)
routes.ajouter_arete("Moulins","Lyon",143)
routes.ajouter_arete("Moulins","Paray-le-Monial",43)
routes.ajouter_arete("Paray-le-Monial","Mâcon",57)
routes.ajouter_arete("Paray-le-Monial","Chalon-sur-Saône",53)
routes.ajouter_arete("Mâcon","Chalon-sur-Saône",40)
routes.ajouter_arete("Chalon-sur-Saône","Beaune",29)
routes.ajouter_arete("Mâcon","Lyon",50)
routes.ajouter_arete("Mâcon","Bourg-en-Bresse",30)
routes.ajouter_arete("Bourg-en-Bresse","Besançon",112)
routes.ajouter_arete("Bourg-en-Bresse","Dole",74)
routes.ajouter_arete("Bourg-en-Bresse","Pont-d'Ain",23)
routes.ajouter_arete("Lyon","Pont-d'Ain",49)
routes.ajouter_arete("Pont-d'Ain","Annecy",84)
routes.ajouter_arete("Annecy","Albertville",56)
routes.ajouter_arete("Montmélian","Albertville",24)
routes.ajouter_arete("Chambéry","Montmélian",20)
routes.ajouter_arete("Chambéry","Aix-les-Bains",21)
routes.ajouter_arete("Aix-les-Bains","Annecy",28)
routes.ajouter_arete("Grenoble","Montmélian",34)
routes.ajouter_arete("Bourgoin-Jallieu","Chambéry",41)
routes.ajouter_arete("Bourgoin-Jallieu","Grenoble",43)
routes.ajouter_arete("Lyon","Bourgoin-Jallieu",40)
routes.ajouter_arete("Valence","Grenoble",65)
routes.ajouter_arete("Agen","Toulouse",75)
routes.ajouter_arete("Langon","Agen",57)
routes.ajouter_arete("Bordeaux","Langon",54)
routes.ajouter_arete("Mont-de-Marsan","Langon",55)
routes.ajouter_arete("Mont-de-Marsan","Pau",74)
routes.ajouter_arete("Biarritz","Mont-de-Marsan",97)
routes.ajouter_arete("Manosque","Brignoles",60)
routes.ajouter_arete("Les Mées","Digne-les-Bains",26)
routes.ajouter_arete("Châteauredon","Digne-les-Bains",12)
routes.ajouter_arete("Châteauredon","Barrême",19)
routes.ajouter_arete("Barrême","Saint-André-les-Alpes",13)
routes.ajouter_arete("Castellane","Saint-Julien-du-Verdon",16)
routes.ajouter_arete("Saint-André-les-Alpes","Saint-Julien-du-Verdon",7)
routes.ajouter_arete("Saint-Julien-du-Verdon","Puget-Théniers",36)
routes.ajouter_arete("Puget-Théniers","Villars-sur-Var",17)
routes.ajouter_arete("Villars-sur-Var","Saint-Martin-du-Var",18)
routes.ajouter_arete("Saint-Martin-du-Var","Carros",6)
routes.ajouter_arete("Nice","Carros",9)
routes.ajouter_arete("Castellane","Grasse",61)
trajet_nice_marseille = ...
def temps_mis(graphe, chaine: list) -> str:
"""
Calcule le temps de trajet correspondant a une chaine de villes.
Parametres :
- graphe : un objet de type GrapheNonOrientePondere
- chaine : list[str] liste de villes, par exemple ["Nice","Cannes","Le Luc"]
Retour :
- si le chemin est valide, renvoyer un string au format "HhMmin" (ex: "1h22min")
- sinon : renvoyer un string indiquant que le chemin n existe pas :
"La chaine Ville1 - Ville2 - ... - VilleN n'existe pas."
"""
...
# --- Zone d essais / visualisation ---
essai1 = ["Nice", "Cannes", "Le Luc"]
print(f"Chaine test 1 : {essai1}")
print(f"longueur_chaine -> {routes.longueur_chaine(essai1)}")
print(f"temps_mis -> {temps_mis(routes, essai1)}")
print()
essai2 = ["Nice", "Cannes", "Le Luc", "Brignoles", "Aix-en-Provence", "Marseille"]
print(f"Chaine test 2 : {essai2}")
print(f"longueur_chaine -> {routes.longueur_chaine(essai2)}")
print(f"temps_mis -> {temps_mis(routes, essai2)}")
print()
essai3 = ["Nice", "Paris", "Brest"]
print(f"Chaine test 3 : {essai3}")
print(f"longueur_chaine -> {routes.longueur_chaine(essai3)}")
print(f"temps_mis -> {temps_mis(routes, essai3)}")
print()
# --- Tres longue route pour visualiser (tu peux la modifier) ---
tres_longue_route = [
"Nice", "Cannes", "Le Luc", "Brignoles", "Aix-en-Provence", "Salon-de-Provence",
"Avignon", "Orange", "Montélimar", "Valence", "Givors", "Lyon",
"Pont-d'Ain", "Annecy", "Aix-les-Bains", "Chambéry", "Montmélian",
"Grenoble", "Valence", "Montélimar", "Orange", "Nîmes", "Montpellier",
"Béziers", "Narbonne", "Carcassonne", "Toulouse", "Montauban",
"Brive-la-Gaillarde", "Limoges", "Le Dognon", "Châteauroux", "Bourges",
"La Charité-sur-Loire", "Nevers", "Moulins", "Paray-le-Monial",
"Mâcon", "Lyon", "Bourgoin-Jallieu", "Grenoble", "Gap", "Les Mées",
"Digne-les-Bains", "Châteauredon", "Barrême", "Saint-André-les-Alpes",
"Saint-Julien-du-Verdon", "Puget-Théniers", "Villars-sur-Var",
"Saint-Martin-du-Var", "Carros", "Nice", "Menton"
]
print(f"Tres longue route : {tres_longue_route}")
print(f"longueur_chaine -> {routes.longueur_chaine(tres_longue_route)}")
print(f"temps_mis -> {temps_mis(routes, tres_longue_route)}")
Tests :
# TestsAffichage :
Console:
>>>
5. Exercice type bac:
A faire dans le cahier.
Nous avons représenté sous la forme d’un graphe les liens entre cinq différents sites Web :
La valeur de chaque arête représente le nombre de citations (de liens hypertextes) d’un site vers un autre. Ainsi, le site site4 contient 6 liens hypertextes qui renvoient vers le site site5.
Les sites sont représentés par des objets de la classe Site dont le code est
partiellement donné ci-dessous. La complétion de la méthode calcul_popularite fera
l’objet d’une question ultérieure.
class Site:
def __init__(self, nom):
self.nom = nom
self.predecesseurs = []
self.successeurs = []
self.popularite = 0
self.couleur = 'blanche'
def calcul_popularite(self):
pass # sera complété plus tardLe graphe précédent peut alors être représenté ainsi :
# Description du graphe
s1, s2, s3, s4, s5 = Site('site1'), Site('site2'), Site('site3'), Site('site4'), Site('site5')
s1.successeurs = [(s3,3), (s4,1), (s5,3)]
s2.successeurs = [(s1,4), (s3,5), (s4,2)]
s3.successeurs = [(s5, 3)]
s4.successeurs = [(s1,2), (s5,6)]
s5.successeurs = [(s3,4)]
s1.predecesseurs = [(s2,4), (s4,2)]
s2.predecesseurs = []
s3.predecesseurs = [(s1,3), (s2,5), (s5,4)]
s4.predecesseurs = ...
s5.predecesseurs = ...- Sur votre cahier, expliquer la ligne
s2.predecesseurs = []. - Compléter les deux dernières lignes.
- Sur votre cahier, expliquer le contenu
s2.successeurs[1][1].
Pour mesurer la pertinence d’un site, on commence par lui attribuer un nombre appelé valeur de popularité qui correspond au nombre de fois qu’il est cité dans les autres sites, c’est-à-dire le nombre de liens hypertextes qui renvoient sur lui. Par exemple, la valeur de popularité du site site4 est 3.
- Quelle est la valeur de la popularité du site 1 ?
- Compléter le code de la méthode
calcul_popularitede la classeSitequi affecte à l’attributpopularitela valeur de popularité correspondante et renvoie cet attribut.
Afin de calculer cette valeur de popularité pour chacun des sites, nous allons faire un
parcours dans le graphe de façon à exécuter la méthode calcul_popularite pour
chacun des objets.
Voici le code de la fonction qui permet le parcours du graphe :
def parcours_graphe(sommet_depart):
parcours = []
sommet_depart.couleur = 'noire'
liste_s = []
liste_s.append(sommet_depart)
while len(liste_s) != 0:
site = liste_s.pop(0)
site.calcul_popularite()
parcours.append(site)
for successeur in site.successeurs:
if successeur[0].couleur == 'blanche':
successeur[0].couleur = 'noire'
liste_s.append( successeur[0] )
return parcoursDans ce parcours, les sites non encore traités sont de couleur 'blanche' (valeur par
défaut à la création de l’objet) et ceux qui sont traités de couleur 'noire'.
-
Dans ce parcours, on manipule la liste Python nommée
liste_suniquement à l’aide d’appels de la formeliste_s.append(sommet)etliste_s.pop(0).Donner la structure de données correspondant à ces manipulations.
- Donner le nom de ce parcours de graphe en justifiant.
-
La fonction
parcours_grapherenvoie une listeparcours. Indiquer la valeur renvoyée par l’appel de fonctionparcours_graphe(s1)
On cherche maintenant le site le plus populaire, celui dont la valeur de popularité est la plus grande.
Voici le code de la fonction qui renvoie le site le plus populaire, elle prend comme
argument une liste non vide contenant des instances de la classe Site.
def le_plus_populaire(liste_sites):
max_popularite = 0
site_le_plus_populaire=liste_sites[0]
for site in liste_sites:
if site.popularite > max_popularite:
...
...
return site_le_plus_populaire- Compléter la fonction ci-dessus.
- Expliquer ce que renvoie
le_plus_populaire(parcours_graphe(s1)).nom - On envisage d’utiliser l’ensemble des fonctions proposées ci-dessus pour rechercher le site le plus populaire parmi un très grand nombre de sites (quelques milliers de sites). Expliquer si ce code est adapté à une telle quantité de sites à traiter. Justifier votre réponse.
6. Algorithme de Dijkstra:
L'algorithme de Dijkstra est une méthode utilisée pour trouver le chemin le plus court entre un noeud source et tous les autres noeuds dans un graphe pondéré, c'est-à-dire un graphe où les arêtes ont des poids. Cet algorithme est largement utilisé dans des domaines tels que la planification de trajets, la conception de réseaux et la gestion de projets.
Exemple :
Prenons un exemple simple pour illustrer le fonctionnement de l'algorithme de Dijkstra. Imaginons le graphe suivant :
Si nous utilisons Dijkstra à partir du noeud source A, nous trouverons les distances minimales vers tous les autres noeuds : A(0), B(2), C(5), D(1), E(6). L'algorithme commence par le noeud source A, explore les voisins B et D, puis continue à minimiser les distances aux autres noeuds.
Applications :
- La recherche du chemin le plus court dans les réseaux routiers.
- La planification de trajets dans la logistique et les transports.
- La conception de réseaux de télécommunication.
- La gestion de projets pour identifier les chemins critiques.
7. Exercice:
A faire dans le cahier.
On considère le graphe ci-dessous :
Déterminer à l'aide d'un papier et d'un stylo le plus court chemin entre A et S.
8. Implémentation de l'algorithme de Dijkstra
L'implémentation de l'algorithme de Dijkstra nécessite généralement l'utilisation de structures de données telles qu'une file de priorité ou un tas binaire pour maintenir les noeuds non visités avec les distances minimales. Vous pouvez le coder en utilisant votre langage de programmation préféré. Voici un exemple en pseudo-code :
dijkstra(graphe, noeud_de_départ,noeud_arrivee):
Initialiser une table de distances avec des distances infinies pour tous les noeuds.
Initialiser une table des noeuds visités en mettant Faux à tous les noeuds.
Initialiser une table des prédécesseurs vide pour l ensemble des noeuds
Mettre la distance du noeud_de_départ à 0.
Mettre le noeud actuel comme étant le noeud de départ.
Mettre le noeud de départ comme étant visité
Tant que le noeud_arrivee n est pas visité:
Pour chaque voisin non visité du noeud actuel:
Calculer la distance temporaire à partir du noeud_de_départ
Si cette distance temporaire est plus courte que la distance enregistrée dans la table, mettre à jour la distance et le prédecesseur de ce noeud
Sélectionner le noeud non visité avec la plus petite distance.
Marquer ce noeud comme visité.
Mettre ce noeud comme noeud actuel
Retourner la table des prédécesseurs.9. Exercice : Dijkstra sur un graphe non orienté pondéré
On modélise des routes entre des villes avec un graphe non orienté pondéré.
Chaque ville est un sommet. Une route entre deux villes est une arête. Le poids (un entier) correspond à un temps en minutes.
La méthode dijkstra(self, noeud_depart, noeud_arrivee) qui retourne la table des prédécesseurs.
Compléter la méthode chemin_le_plus_court(self, noeud_depart, noeud_arrivee) qui reconstruit le chemin grâce à la table des prédécesseurs.
Exemple :
chemin = routes.chemin_le_plus_court("Nice","Marseille")
# chemin commence par "Nice" et se termine par "Marseille"class GrapheNonOrientePondere:
def __init__(self) -> None:
"""
Graphe non orienté pondéré.
Representation :
- self.aretes : dict[str, dict[str, int]]
* self.aretes[A][B] = poids de A--B
* comme le graphe est non orienté, on stocke aussi self.aretes[B][A]
"""
self.aretes: dict = {}
def ajouter_sommet(self, sommet: str) -> None:
if sommet not in self.aretes:
self.aretes[sommet] = {}
def ajouter_arete(self, sommet1: str, sommet2: str, poids: int) -> None:
self.ajouter_sommet(sommet1)
self.ajouter_sommet(sommet2)
self.aretes[sommet1][sommet2] = poids
self.aretes[sommet2][sommet1] = poids
def distance(self, sommet1: str, sommet2: str) -> int:
"""
Renvoie le poids de sommet1--sommet2, ou -1 si absent.
"""
if sommet1 not in self.aretes:
return -1
if sommet2 not in self.aretes[sommet1]:
return -1
return self.aretes[sommet1][sommet2]
def poids_chaine(self, chaine: list) -> int:
"""
Somme des poids sur une chaine de sommets.
Retourne -1 si la chaine n existe pas.
"""
if type(chaine) != list or len(chaine) == 0:
return -1
if len(chaine) == 1:
if chaine[0] in self.aretes:
return 0
return -1
total = 0
for i in range(len(chaine) - 1):
a = chaine[i]
b = chaine[i + 1]
d = self.distance(a, b)
if d == -1:
return -1
total += d
return total
# --- Methodes COMPLETES (a copier dans la classe puis tu enleveras des morceaux) ---
def dijkstra(self, noeud_depart: str, noeud_arrivee: str) -> dict:
"""
Dijkstra : renvoie la table des predecesseurs.
Algorithme :
1) distances = inf partout, sauf depart = 0
2) visites = False partout
3) predecesseurs = None partout
4) courant = depart
5) Tant que arrivee n est pas visitee :
- pour chaque voisin non visite de courant :
distance_temp = distances[courant] + poids(courant, voisin)
si distance_temp < distances[voisin] :
distances[voisin] = distance_temp
predecesseurs[voisin] = courant
- choisir le sommet non visite avec la plus petite distance
- le mettre dans courant
6) retourner predecesseurs
"""
if noeud_depart not in self.aretes or noeud_arrivee not in self.aretes:
return {}
distances = {s: float("inf") for s in self.aretes}
visites = {s: False for s in self.aretes}
predecesseurs = {s: None for s in self.aretes}
distances[noeud_depart] = 0
courant = noeud_depart
while not visites[noeud_arrivee]:
# 1) Marquer courant visite
visites[courant] = True
# 2) Explorer les voisins non visites
for voisin in sorted(self.aretes[courant].keys()):
if not visites[voisin]:
d_temp = distances[courant] + self.aretes[courant][voisin]
if d_temp < distances[voisin]:
distances[voisin] = d_temp
predecesseurs[voisin] = courant
# 3) Choisir le prochain sommet non visite le plus proche
prochain = None
meilleur = float("inf")
for s in sorted(self.aretes.keys()):
if (not visites[s]) and distances[s] < meilleur:
meilleur = distances[s]
prochain = s
# 4) Si plus rien d atteignable, on s arrete
if prochain is None or meilleur == float("inf"):
break
courant = prochain
return predecesseurs
def chemin_le_plus_court(self, noeud_depart: str, noeud_arrivee: str) -> list:
"""
Renvoie un plus court chemin sous forme de liste de sommets,
en utilisant la table des predecesseurs renvoyee par dijkstra.
Retour :
- list[str] : chemin [depart, ..., arrivee]
- [] si aucun chemin n existe ou si un sommet n existe pas
"""
...
# -----------------------
# Graphe routes (extrait long, suffisamment grand pour tester Dijkstra)
# -----------------------
routes = GrapheNonOrientePondere()
routes.ajouter_arete("Cannes","Nice",27)
routes.ajouter_arete("Nice","Menton",34)
routes.ajouter_arete("Grasse","Cannes",32)
routes.ajouter_arete("Le Luc","Cannes",55)
routes.ajouter_arete("Toulon","Le Luc",62)
routes.ajouter_arete("Brignoles","Le Luc",37)
routes.ajouter_arete("Aix-en-Provence","Brignoles",35)
routes.ajouter_arete("Aubagne","Toulon",35)
routes.ajouter_arete("Marseille","Aubagne",23)
routes.ajouter_arete("Marseille","Aix-en-Provence",28)
routes.ajouter_arete("Aix-en-Provence","Aubagne",28)
routes.ajouter_arete("Salon-de-Provence","Aix-en-Provence",25)
routes.ajouter_arete("Arles","Salon-de-Provence",30)
routes.ajouter_arete("Avignon","Salon-de-Provence",45)
routes.ajouter_arete("Nîmes","Arles",27)
routes.ajouter_arete("Nîmes","Orange",41)
routes.ajouter_arete("Avignon","Orange",30)
routes.ajouter_arete("Montpellier","Nîmes",47)
routes.ajouter_arete("Montélimar","Orange",40)
routes.ajouter_arete("Montélimar","Valence",43)
routes.ajouter_arete("Les Mées","Gap",52)
routes.ajouter_arete("Manosque","Les Mées",22)
routes.ajouter_arete("Aix-en-Provence","Manosque",52)
routes.ajouter_arete("Grenoble","Gap",113)
routes.ajouter_arete("Béziers","Montpellier",61)
routes.ajouter_arete("Givors","Valence",61)
routes.ajouter_arete("Givors","Lyon",28)
routes.ajouter_arete("Saint-Étienne","Givors",38)
routes.ajouter_arete("Clermont-Ferrand","Saint-Étienne",103)
routes.ajouter_arete("Béziers","Clermont-l'Hérault",51)
routes.ajouter_arete("Clermont-l'Hérault","Montpellier",41)
routes.ajouter_arete("Clermont-Ferrand","Clermont-l'Hérault",209)
routes.ajouter_arete("Narbonne","Béziers",30)
routes.ajouter_arete("Carcassonne","Narbonne",43)
routes.ajouter_arete("Perpignan","Narbonne",45)
routes.ajouter_arete("Toulouse","Carcassonne",68)
routes.ajouter_arete("Tarbes","Toulouse",107)
routes.ajouter_arete("Pau","Tarbes",36)
routes.ajouter_arete("Biarritz","Pau",86)
routes.ajouter_arete("Biarritz","Bordeaux",133)
routes.ajouter_arete("Bordeaux","Brive-la-Gaillarde",137)
routes.ajouter_arete("Brive-la-Gaillarde","Clermont-Ferrand",126)
routes.ajouter_arete("Limoges","Brive-la-Gaillarde",64)
routes.ajouter_arete("Montluçon","Clermont-Ferrand",79)
routes.ajouter_arete("Angoulême","Limoges",86)
routes.ajouter_arete("Saintes","Angoulême",70)
routes.ajouter_arete("Saintes","Bordeaux",83)
routes.ajouter_arete("Angoulême","Limalonges",46)
routes.ajouter_arete("Limalonges","Poitiers",46)
routes.ajouter_arete("La Rochelle","Saintes",55)
routes.ajouter_arete("La Rochelle","Niort",52)
routes.ajouter_arete("Saintes","Niort",56)
routes.ajouter_arete("Niort","Poitiers",62)
routes.ajouter_arete("Niort","Limalonges",64)
routes.ajouter_arete("Montauban","Toulouse",44)
routes.ajouter_arete("Montauban","Brive-la-Gaillarde",98)
routes.ajouter_arete("Poitiers","Tours",78)
routes.ajouter_arete("La Roche-sur-Yon","Niort",69)
routes.ajouter_arete("Nantes","La Roche-sur-Yon",57)
routes.ajouter_arete("La Roche-sur-Yon","Cholet",54)
routes.ajouter_arete("Cholet","Parthenay",55)
routes.ajouter_arete("Parthenay","Poitiers",60)
routes.ajouter_arete("Nantes","Angers",66)
routes.ajouter_arete("Cholet","Angers",46)
routes.ajouter_arete("Angers","Saumur",38)
routes.ajouter_arete("Saumur","Tours",45)
routes.ajouter_arete("Parthenay","Saumur",95)
routes.ajouter_arete("Saint-Nazaire","Nantes",57)
routes.ajouter_arete("La Roche-Bernard","Saint-Nazaire",46)
routes.ajouter_arete("Savenay","Nantes",37)
routes.ajouter_arete("Saint-Nazaire","Savenay",25)
routes.ajouter_arete("Pontchâteau","Savenay",13)
routes.ajouter_arete("La Roche-Bernard","Pontchâteau",17)
routes.ajouter_arete("Vannes","La Roche-Bernard",38)
routes.ajouter_arete("Vannes","Redon",57)
routes.ajouter_arete("Redon","Rennes",57)
routes.ajouter_arete("La Roche-Bernard","Redon",34)
routes.ajouter_arete("Lorient","Vannes",47)
routes.ajouter_arete("Quimper","Lorient",50)
routes.ajouter_arete("Quimper","Châteaulin",22)
routes.ajouter_arete("Brest","Châteaulin",38)
routes.ajouter_arete("Châteaulin","Carhaix-Plouguer",33)
routes.ajouter_arete("Carhaix-Plouguer","Lorient",67)
routes.ajouter_arete("Brest","Morlaix",47)
routes.ajouter_arete("Morlaix","Saint-Brieuc",70)
routes.ajouter_arete("Saint-Brieuc","Loudéac",43)
routes.ajouter_arete("Saint-Brieuc","Rennes",77)
routes.ajouter_arete("Carhaix-Plouguer","Loudéac",66)
routes.ajouter_arete("Pontivy","Loudéac",22)
routes.ajouter_arete("Pontivy","Vannes",46)
routes.ajouter_arete("Lorient","Pontivy",47)
routes.ajouter_arete("Rennes","Angers",103)
routes.ajouter_arete("Rennes","Laval",66)
routes.ajouter_arete("Laval","Le Mans",56)
routes.ajouter_arete("Angers","Le Mans",66)
routes.ajouter_arete("Le Mans","Tours",72)
routes.ajouter_arete("Saint-Brieuc","Saint-Malo",64)
routes.ajouter_arete("Saint-Malo","Avranches",49)
routes.ajouter_arete("Rennes","Avranches",62)
routes.ajouter_arete("Laval","Mayenne",26)
routes.ajouter_arete("Mayenne","Alençon",63)
routes.ajouter_arete("Alençon","Le Mans",42)
routes.ajouter_arete("Avranches","Caen",68)
routes.ajouter_arete("Saint-Malo","Rennes",51)
routes.ajouter_arete("Rennes","Fougères",42)
routes.ajouter_arete("Fougères","Mayenne",60)
routes.ajouter_arete("Avranches","Fougères",26)
routes.ajouter_arete("Caen","Alençon",77)
routes.ajouter_arete("Caen","Le Havre",64)
routes.ajouter_arete("Le Havre","Rouen",60)
routes.ajouter_arete("Caen","Rouen",85)
routes.ajouter_arete("Rouen","Evreux",45)
routes.ajouter_arete("Evreux","Dreux",36)
routes.ajouter_arete("Dreux","Chartres",42)
routes.ajouter_arete("Caen","Evreux",99)
routes.ajouter_arete("Alençon","Dreux",97)
routes.ajouter_arete("Le Mans","Chartres",80)
routes.ajouter_arete("Saint-Arnoult-en-Yvelines","Paris",60)
routes.ajouter_arete("Chartres","Saint-Arnoult-en-Yvelines",34)
routes.ajouter_arete("Orléans","Saint-Arnoult-en-Yvelines",66)
routes.ajouter_arete("Dreux","Paris",74)
routes.ajouter_arete("Evreux","Paris",88)
routes.ajouter_arete("Vierzon","Bourges",23)
routes.ajouter_arete("Châteauroux","Bourges",60)
routes.ajouter_arete("Châteauroux","Vierzon",40)
routes.ajouter_arete("Orléans","Vierzon",58)
routes.ajouter_arete("Blois","Chémery",38)
routes.ajouter_arete("Tours","Chémery",57)
routes.ajouter_arete("Chémery","Châteauroux",67)
routes.ajouter_arete("Chémery","Vierzon",37)
routes.ajouter_arete("Tours","Blois",42)
routes.ajouter_arete("Blois","Orléans",42)
routes.ajouter_arete("Poitiers","Le Dognon",106)
routes.ajouter_arete("Limoges","Le Dognon",33)
routes.ajouter_arete("Le Dognon","Montluçon",75)
routes.ajouter_arete("Le Dognon","Châteauroux",55)
routes.ajouter_arete("Bourges","Montluçon",66)
routes.ajouter_arete("Rouen","Neufchâtel-en-Bray",60)
routes.ajouter_arete("Neufchâtel-en-Bray","Amiens",45)
routes.ajouter_arete("Neufchâtel-en-Bray","Abbeville",63)
routes.ajouter_arete("Le Havre","Neufchâtel-en-Bray",90)
routes.ajouter_arete("Beauvais","Paris",73)
routes.ajouter_arete("Beauvais","Amiens",44)
routes.ajouter_arete("Abbeville","Amiens",35)
routes.ajouter_arete("Berck","Abbeville",22)
routes.ajouter_arete("Boulogne-sur-Mer","Berck",25)
routes.ajouter_arete("Boulogne-sur-Mer","Calais",26)
routes.ajouter_arete("Calais","Dunkerque",35)
routes.ajouter_arete("Dunkerque","Lille",56)
routes.ajouter_arete("Lille","Valenciennes",42)
routes.ajouter_arete("Saint-Quentin","Valenciennes",58)
routes.ajouter_arete("Amiens","Saint-Quentin",61)
routes.ajouter_arete("Hénin-Beaumont","Douai",10)
routes.ajouter_arete("Lens","Hénin-Beaumont",14)
routes.ajouter_arete("Arras","Hénin-Beaumont",25)
routes.ajouter_arete("Hénin-Beaumont","Lille",27)
routes.ajouter_arete("Douai","Valenciennes",34)
routes.ajouter_arete("Amiens","Arras",74)
routes.ajouter_arete("Berck","Arras",75)
routes.ajouter_arete("Arras","Lens",14)
routes.ajouter_arete("Boulogne-sur-Mer","Lens",80)
routes.ajouter_arete("Beauvais","Compiègne",49)
routes.ajouter_arete("Compiègne","Saint-Quentin",60)
routes.ajouter_arete("Paris","Compiègne",72)
routes.ajouter_arete("Compiègne","Soissons",41)
routes.ajouter_arete("Soissons","Reims",56)
routes.ajouter_arete("Paris","Soissons",91)
routes.ajouter_arete("Soissons","Laon",31)
routes.ajouter_arete("Paris","Sens",92)
routes.ajouter_arete("Valenciennes","Maubeuge",32)
routes.ajouter_arete("La Capelle","Maubeuge",43)
routes.ajouter_arete("La Capelle","Charleville-Mézières",64)
routes.ajouter_arete("Saint-Quentin","La Capelle",57)
routes.ajouter_arete("Laon","La Capelle",58)
routes.ajouter_arete("Reims","Charleville-Mézières",61)
routes.ajouter_arete("Laon","Reims",43)
routes.ajouter_arete("Saint-Quentin","Laon",37)
routes.ajouter_arete("Reims","Châlons-en-Champagne",35)
routes.ajouter_arete("Châlons-en-Champagne","Vitry-le-François",27)
routes.ajouter_arete("Vitry-le-François","Saint-Dizier",27)
routes.ajouter_arete("Sommesous","Vitry-le-François",30)
routes.ajouter_arete("Paris","Sommesous",132)
routes.ajouter_arete("Sommesous","Châlons-en-Champagne",28)
routes.ajouter_arete("Troyes","Sommesous",46)
routes.ajouter_arete("Châlons-en-Champagne","Metz",101)
routes.ajouter_arete("Saint-Dizier","Chaumont",63)
routes.ajouter_arete("Saint-Dizier","Nancy",80)
routes.ajouter_arete("Sens","Troyes",50)
routes.ajouter_arete("Metz","Nancy",53)
routes.ajouter_arete("Colmar","Strasbourg",72)
routes.ajouter_arete("Mulhouse","Colmar",47)
routes.ajouter_arete("Nancy","Colmar",140)
routes.ajouter_arete("Nancy","Épinal",53)
routes.ajouter_arete("Épinal","Mulhouse",103)
routes.ajouter_arete("Vesoul","Épinal",70)
routes.ajouter_arete("Besançon","Vesoul",50)
routes.ajouter_arete("Vesoul","Belfort & Montbéliard",54)
routes.ajouter_arete("Belfort & Montbéliard","Mulhouse",36)
routes.ajouter_arete("Besançon","Belfort & Montbéliard",69)
routes.ajouter_arete("Chaumont","Vesoul",107)
routes.ajouter_arete("Dole","Besançon",47)
routes.ajouter_arete("Dijon","Dole",39)
routes.ajouter_arete("Beaune","Dijon",36)
routes.ajouter_arete("Beaune","Dole",44)
routes.ajouter_arete("Dijon","Chaumont",75)
routes.ajouter_arete("Auxerre","Pouilly-en-Auxois",116)
routes.ajouter_arete("Pouilly-en-Auxois","Dijon",55)
routes.ajouter_arete("Pouilly-en-Auxois","Beaune",29)
routes.ajouter_arete("Troyes","Chaumont",72)
routes.ajouter_arete("Sens","Auxerre",54)
routes.ajouter_arete("Montargis","Sens",51)
routes.ajouter_arete("Orléans","Montargis",59)
routes.ajouter_arete("Montargis","La Charité-sur-Loire",68)
routes.ajouter_arete("Bourges","La Charité-sur-Loire",62)
routes.ajouter_arete("La Charité-sur-Loire","Nevers",22)
routes.ajouter_arete("Nevers","Moulins",55)
routes.ajouter_arete("Montluçon","Moulins",55)
routes.ajouter_arete("Moulins","Lyon",143)
routes.ajouter_arete("Moulins","Paray-le-Monial",43)
routes.ajouter_arete("Paray-le-Monial","Mâcon",57)
routes.ajouter_arete("Paray-le-Monial","Chalon-sur-Saône",53)
routes.ajouter_arete("Mâcon","Chalon-sur-Saône",40)
routes.ajouter_arete("Chalon-sur-Saône","Beaune",29)
routes.ajouter_arete("Mâcon","Lyon",50)
routes.ajouter_arete("Mâcon","Bourg-en-Bresse",30)
routes.ajouter_arete("Bourg-en-Bresse","Besançon",112)
routes.ajouter_arete("Bourg-en-Bresse","Dole",74)
routes.ajouter_arete("Bourg-en-Bresse","Pont-d'Ain",23)
routes.ajouter_arete("Lyon","Pont-d'Ain",49)
routes.ajouter_arete("Pont-d'Ain","Annecy",84)
routes.ajouter_arete("Annecy","Albertville",56)
routes.ajouter_arete("Montmélian","Albertville",24)
routes.ajouter_arete("Chambéry","Montmélian",20)
routes.ajouter_arete("Chambéry","Aix-les-Bains",21)
routes.ajouter_arete("Aix-les-Bains","Annecy",28)
routes.ajouter_arete("Grenoble","Montmélian",34)
routes.ajouter_arete("Bourgoin-Jallieu","Chambéry",41)
routes.ajouter_arete("Bourgoin-Jallieu","Grenoble",43)
routes.ajouter_arete("Lyon","Bourgoin-Jallieu",40)
routes.ajouter_arete("Valence","Grenoble",65)
routes.ajouter_arete("Agen","Toulouse",75)
routes.ajouter_arete("Langon","Agen",57)
routes.ajouter_arete("Bordeaux","Langon",54)
routes.ajouter_arete("Mont-de-Marsan","Langon",55)
routes.ajouter_arete("Mont-de-Marsan","Pau",74)
routes.ajouter_arete("Biarritz","Mont-de-Marsan",97)
routes.ajouter_arete("Manosque","Brignoles",60)
routes.ajouter_arete("Les Mées","Digne-les-Bains",26)
routes.ajouter_arete("Châteauredon","Digne-les-Bains",12)
routes.ajouter_arete("Châteauredon","Barrême",19)
routes.ajouter_arete("Barrême","Saint-André-les-Alpes",13)
routes.ajouter_arete("Castellane","Saint-Julien-du-Verdon",16)
routes.ajouter_arete("Saint-André-les-Alpes","Saint-Julien-du-Verdon",7)
routes.ajouter_arete("Saint-Julien-du-Verdon","Puget-Théniers",36)
routes.ajouter_arete("Puget-Théniers","Villars-sur-Var",17)
routes.ajouter_arete("Villars-sur-Var","Saint-Martin-du-Var",18)
routes.ajouter_arete("Saint-Martin-du-Var","Carros",6)
routes.ajouter_arete("Nice","Carros",9)
routes.ajouter_arete("Castellane","Grasse",61)
# Prints de visualisation
print("Nb sommets :", len(routes.aretes))
print("Exemple trajet Nice -> Marseille :", routes.chemin_le_plus_court("Nice","Marseille"))
print("Poids trajet Nice -> Marseille :", routes.poids_chaine(routes.chemin_le_plus_court("Nice","Marseille")))
print("Exemple trajet Nice -> Paris :", routes.chemin_le_plus_court("Nice","Paris"))
print("Poids trajet Nice -> Paris :", routes.poids_chaine(routes.chemin_le_plus_court("Nice","Paris")))
Tests :
Affichage :
Console:
>>>