Exercice : SNCG [Spécialité NSI - Année 2026

SNCG

Introduction

Vous êtes missionés par la Société Numérique des Chemins de Graphes (SNCG) afin d'améliorer leur application « Connect - SNCG » permettant de rechercher un itinéraire en train.

Vous choisissez de modéliser le réseau ferroviaire en utilisant des graphes orientés ayant des poids sur leurs arcs.

Un sommet du graphe représente une gare ferroviaire.
Un arc du graphe représente une liaison directe entre deux gares.
Un poids sur un arc représente la durée en minutes nécessaire pour réaliser le parcours.

On suppose que tous les trains sont disponibles à n'importe quelle heure.

Question

En utilisant la classe Graphe réalisée dans l'exercice précédent, implémenter la fonctionnalité pour avoir des poids sur les arcs :

Revoir l'implémentation choisie :
- Si matrice d'adjacence, la valeur d'indices (i,j) indique le poids de l'arc reliant i à j.
- Si liste ou dictionnaire d'adjacence, la liste indiquant les connexions est désormais une liste de couples (n,p) avec n le noeud de destination et p le poids de cet arc.
Revoir les méthodes d'ajout et de suppression d'arc pour ajouter le poids en paramètre

Préparation du réseau

Afin de faciliter la visualisation des graphes, nous allons utiliser le site https://dreampuf.github.io/GraphvizOnline/.

La syntaxe est la suivante :

digraph {
  A -> B [label=42];
  A -> C [label=28];
}

digraph {
  A -> B [label=42];
  A -> C [label=28];
}

Chaque arc est représenté par une ligne indiquant le nom des deux sommets (par exemple A et B), et le poids (par exemple 42).

Les retours à la ligne et les espaces étant facultatifs, on peut rédiger également comme cela : digraph{A->B[label=42];A->C[label=28];}

Question

Rédiger la méthode __str__ de votre classe Graphe pour renvoyer le texte représentatif du graphe selon la syntaxe ci-dessus.

Pour les plus rapides : En observant le comportement du site, ouvrir directement le site web pré-rempli lors de l'appel à une fonction visualiser().

Création des lignes

Afin de consulter les durées des trains, on utilise le site web https://direkt.bahn.guru/.

On peut utiliser la barre de recherche en haut à droite pour rechercher une gare, et visualiser les temps de trajets. On suppose qu'il n'existe que les gares suivantes :

Lyon (Part-Dieu)
Bourg-en-Bresse
Bellegarde
Ambérieu
Annecy
Chambéry
Grenoble
Valence (Ville)
Roanne
St-Etienne (Châteaucreux)
Moulins
Clermont-Ferrand

Question

Créer une instance de la classe Graphe pour représenter ces gares ainsi que leurs corrections directes. On ne notera pas d'espace ou de tiret dans les noms de sommets.

Indice

ter = Graphe()
ter.ajout_sommet("Lyon")
ter.ajout_sommet("BourgEnBresse")
ter.ajout_sommet("Bellegarde")
ter.ajout_sommet("Ambérieu")
ter.ajout_sommet("Annecy")
ter.ajout_sommet("Chambéry")
ter.ajout_sommet("Grenoble")
ter.ajout_sommet("Valence")
ter.ajout_sommet("Roanne")
ter.ajout_sommet("StEtienne")
ter.ajout_sommet("Moulins")
ter.ajout_sommet("ClermontFerrand")
ter.ajout_arc("Lyon", "BourgEnBresse", 38)
ter.ajout_arc("Lyon", "Bellegarde", 86)
ter.ajout_arc("Lyon", "Ambérieu", 23)
ter.ajout_arc("Lyon", "Annecy", 108)
ter.ajout_arc("Lyon", "Chambéry", 76)
ter.ajout_arc("Lyon", "Grenoble", 82)
ter.ajout_arc("Lyon", "Valence", 67)
ter.ajout_arc("Lyon", "Roanne", 64)
ter.ajout_arc("Lyon", "StEtienne", 42)
ter.ajout_arc("Lyon", "Moulins", 125)
ter.ajout_arc("Lyon", "ClermontFerrand", 134)
ter.ajout_arc("BourgEnBresse", "Lyon", 47)
ter.ajout_arc("BourgEnBresse", "Bellegarde", 48)
ter.ajout_arc("BourgEnBresse", "Ambérieu", 18)
ter.ajout_arc("Bellegarde", "Lyon", 73)
ter.ajout_arc("Bellegarde", "BourgEnBresse", 46)
ter.ajout_arc("Bellegarde", "Ambérieu", 56)
ter.ajout_arc("Bellegarde", "Chambéry", 49)
ter.ajout_arc("Bellegarde", "Grenoble", 94)
ter.ajout_arc("Bellegarde", "Valence", 166)
ter.ajout_arc("Ambérieu", "Lyon", 24)
ter.ajout_arc("Ambérieu", "BourgEnBresse", 17)
ter.ajout_arc("Ambérieu", "Bellegarde", 61)
ter.ajout_arc("Ambérieu", "Annecy", 83)
ter.ajout_arc("Ambérieu", "Chambéry", 71)
ter.ajout_arc("Ambérieu", "StEtienne", 93)
ter.ajout_arc("Annecy", ...)
# À COMPLÉTER
ter.ajout_arc("Chambéry", "Lyon", 73)
ter.ajout_arc("Chambéry", "Bellegarde", 46)
ter.ajout_arc("Chambéry", "Ambérieu", 59)
ter.ajout_arc("Chambéry", "Annecy", 39)
ter.ajout_arc("Chambéry", "Grenoble", 41)
ter.ajout_arc("Chambéry", "Valence", 113)
ter.ajout_arc("Grenoble", "Lyon", 83)
ter.ajout_arc("Grenoble", "Bellegarde", 93)
ter.ajout_arc("Grenoble", "Annecy", 102)
ter.ajout_arc("Grenoble", "Chambéry", 41)
ter.ajout_arc("Grenoble", "Valence", 64)
ter.ajout_arc("Valence", "Lyon", 64)
ter.ajout_arc("Valence", "Bellegarde", 166)
ter.ajout_arc("Valence", "Annecy", 178)
ter.ajout_arc("Valence", "Chambéry", 114)
ter.ajout_arc("Valence", "Valence", 66)
ter.ajout_arc("Roanne", "Lyon", 63)
ter.ajout_arc("Roanne", "StEtienne", 70)
ter.ajout_arc("Roanne", "Moulins", 58)
ter.ajout_arc("Roanne", "ClermontFerrand", 76)
ter.ajout_arc("StEtienne", "Lyon", 41)
ter.ajout_arc("StEtienne", "Ambérieu", 94)
ter.ajout_arc("StEtienne", "Roanne", 69)
ter.ajout_arc("Moulins", "Lyon", 125)
ter.ajout_arc("Moulins", "Roanne", 59)
ter.ajout_arc("Moulins", "ClermontFerrand", 58)
ter.ajout_arc("ClermontFerrand", "Lyon", 134)
ter.ajout_arc("ClermontFerrand", "Roanne", 75)
ter.ajout_arc("ClermontFerrand", "Moulins", 56)

ter = Graphe()

ter.ajout_sommet("Lyon")
ter.ajout_sommet("BourgEnBresse")
ter.ajout_sommet("Bellegarde")
ter.ajout_sommet("Ambérieu")
ter.ajout_sommet("Annecy")
ter.ajout_sommet("Chambéry")
ter.ajout_sommet("Grenoble")
ter.ajout_sommet("Valence")
ter.ajout_sommet("Roanne")
ter.ajout_sommet("StEtienne")
ter.ajout_sommet("Moulins")
ter.ajout_sommet("ClermontFerrand")

ter.ajout_arc("Lyon", "BourgEnBresse", 38)
ter.ajout_arc("Lyon", "Bellegarde", 86)
ter.ajout_arc("Lyon", "Ambérieu", 23)
ter.ajout_arc("Lyon", "Annecy", 108)
ter.ajout_arc("Lyon", "Chambéry", 76)
ter.ajout_arc("Lyon", "Grenoble", 82)
ter.ajout_arc("Lyon", "Valence", 67)
ter.ajout_arc("Lyon", "Roanne", 64)
ter.ajout_arc("Lyon", "StEtienne", 42)
ter.ajout_arc("Lyon", "Moulins", 125)
ter.ajout_arc("Lyon", "ClermontFerrand", 134)

ter.ajout_arc("BourgEnBresse", "Lyon", 47)
ter.ajout_arc("BourgEnBresse", "Bellegarde", 48)
ter.ajout_arc("BourgEnBresse", "Ambérieu", 18)

ter.ajout_arc("Bellegarde", "Lyon", 73)
ter.ajout_arc("Bellegarde", "BourgEnBresse", 46)
ter.ajout_arc("Bellegarde", "Ambérieu", 56)
ter.ajout_arc("Bellegarde", "Chambéry", 49)
ter.ajout_arc("Bellegarde", "Grenoble", 94)
ter.ajout_arc("Bellegarde", "Valence", 166)

ter.ajout_arc("Ambérieu", "Lyon", 24)
ter.ajout_arc("Ambérieu", "BourgEnBresse", 17)
ter.ajout_arc("Ambérieu", "Bellegarde", 61)
ter.ajout_arc("Ambérieu", "Annecy", 83)
ter.ajout_arc("Ambérieu", "Chambéry", 71)
ter.ajout_arc("Ambérieu", "StEtienne", 93)

ter.ajout_arc("Annecy", ...)
# À COMPLÉTER

ter.ajout_arc("Chambéry", "Lyon", 73)
ter.ajout_arc("Chambéry", "Bellegarde", 46)
ter.ajout_arc("Chambéry", "Ambérieu", 59)
ter.ajout_arc("Chambéry", "Annecy", 39)
ter.ajout_arc("Chambéry", "Grenoble", 41)
ter.ajout_arc("Chambéry", "Valence", 113)

ter.ajout_arc("Grenoble", "Lyon", 83)
ter.ajout_arc("Grenoble", "Bellegarde", 93)
ter.ajout_arc("Grenoble", "Annecy", 102)
ter.ajout_arc("Grenoble", "Chambéry", 41)
ter.ajout_arc("Grenoble", "Valence", 64)

ter.ajout_arc("Valence", "Lyon", 64)
ter.ajout_arc("Valence", "Bellegarde", 166)
ter.ajout_arc("Valence", "Annecy", 178)
ter.ajout_arc("Valence", "Chambéry", 114)
ter.ajout_arc("Valence", "Valence", 66)

ter.ajout_arc("Roanne", "Lyon", 63)
ter.ajout_arc("Roanne", "StEtienne", 70)
ter.ajout_arc("Roanne", "Moulins", 58)
ter.ajout_arc("Roanne", "ClermontFerrand", 76)

ter.ajout_arc("StEtienne", "Lyon", 41)
ter.ajout_arc("StEtienne", "Ambérieu", 94)
ter.ajout_arc("StEtienne", "Roanne", 69)

ter.ajout_arc("Moulins", "Lyon", 125)
ter.ajout_arc("Moulins", "Roanne", 59)
ter.ajout_arc("Moulins", "ClermontFerrand", 58)

ter.ajout_arc("ClermontFerrand", "Lyon", 134)
ter.ajout_arc("ClermontFerrand", "Roanne", 75)
ter.ajout_arc("ClermontFerrand", "Moulins", 56)

Calcul des itinéraires

Maintenant que l'on dispose d'un réseau ferré en place, il ne reste plus qu'à lancer notre application de recherche d'itinéraires !!

Question

Implémentez une méthode visite_dijkstra, telle que :

Entrées :
- sommet : le sommet à visiter
- marques : la liste représentant les sommets déjà visité
- distances : le dictionnaire représentant les distances actuelles associées à chaque sommet
Sortie : Aucune
Effet : mets à jour les structures marques et distances, après la visite de sommet

Question

Implémentez une méthode dijkstra, telle que :

Entrées :
- sommet : le sommet depuis lequel effectuer l'algorithme de Dijkstra
Sortie : Un dictionnaire représentant la distance entre sommet et les autres

Question

Modifiez une copie de dijkstra et visite_dijkstra pour créer une fonction chemin_entre_gare qui trouve le plus court chemin entre deux gares données en paramètre d'une fonction.

Version finale

Dans la pratique, il faut compter au moins dix minutes de correspondance dans chaque gare afin d'être sûr d'avoir le temps de changer de quai.

Question

Réécrire l'algorithme précédent pour prendre en compte cette nouvelle règle.