TP : GPS Navigator — Itinéraires optimaux

Contexte

Vous êtes développeur chez une startup qui souhaite concurrencer Google Maps et Waze. Votre mission : implémenter le moteur de calcul d'itinéraires en utilisant l'algorithme de Dijkstra pour trouver les chemins les plus courts dans un réseau routier.

Saviez-vous que Google Maps effectue des milliards de calculs Dijkstra chaque jour ?

---

Objectifs

• Modéliser un réseau routier sous forme de graphe
• Implémenter l'algorithme de Dijkstra
• Calculer les itinéraires optimaux (distance ou temps)
• Reconstruire le chemin complet entre deux points

---

Partie 1 : Modélisation du réseau

1.1. Représentation d'un graphe

Un réseau routier peut être modélisé par un graphe pondéré : - Les sommets représentent les intersections/villes - Les arêtes représentent les routes - Les poids représentent les distances ou temps de trajet

Nous utiliserons un dictionnaire d'adjacence :

# Exemple : réseau simplifié de la Côte d'Azur
reseau = {
    "Nice": [("Monaco", 20), ("Cannes", 33), ("Grasse", 40)],
    "Monaco": [("Nice", 20), ("Menton", 10)],
    "Cannes": [("Nice", 33), ("Grasse", 17), ("Antibes", 11)],
    "Grasse": [("Nice", 40), ("Cannes", 17)],
    "Antibes": [("Cannes", 11), ("Nice", 23)],
    "Menton": [("Monaco", 10)]
}

1.2. Création du graphe

Implémenter une classe ReseauRoutier pour gérer le graphe :

class ReseauRoutier:
    """Représente un réseau routier sous forme de graphe."""

    def __init__(self):
        """Initialise un réseau vide."""
        self.graphe = {}

    def ajouter_ville(self, ville):
        """
        Ajoute une ville (sommet) au réseau.

        :param ville: (str) Nom de la ville
        """
        # À compléter
        pass

    def ajouter_route(self, ville1, ville2, distance):
        """
        Ajoute une route bidirectionnelle entre deux villes.

        :param ville1: (str) Première ville
        :param ville2: (str) Deuxième ville
        :param distance: (int) Distance en km
        """
        # À compléter
        pass

    def get_voisins(self, ville):
        """
        Retourne la liste des voisins d'une ville avec les distances.

        :param ville: (str) Nom de la ville
        :return: (list) Liste de tuples (voisin, distance)
        """
        # À compléter
        pass

    def afficher(self):
        """Affiche le réseau."""
        for ville, voisins in self.graphe.items():
            print(f"{ville} -> {voisins}")

Test :

reseau = ReseauRoutier()
reseau.ajouter_ville("Nice")
reseau.ajouter_ville("Monaco")
reseau.ajouter_route("Nice", "Monaco", 20)
reseau.afficher()
# Nice -> [('Monaco', 20)]
# Monaco -> [('Nice', 20)]

---

Partie 2 : Algorithme de Dijkstra

2.1. Principe de l'algorithme

L'algorithme de Dijkstra trouve le plus court chemin depuis une source vers tous les autres sommets :

1. Initialiser toutes les distances à l'infini, sauf la source à 0
2. Marquer tous les sommets comme non visités
3. Tant qu'il reste des sommets non visités :
4. Sélectionner le sommet non visité avec la plus petite distance
5. Pour chaque voisin, mettre à jour la distance si on trouve un chemin plus court
6. Marquer le sommet comme visité

2.2. Implémentation

def dijkstra(reseau, depart):
    """
    Algorithme de Dijkstra pour trouver les plus courts chemins.

    :param reseau: (ReseauRoutier) Le réseau routier
    :param depart: (str) Ville de départ
    :return: (dict) Distances minimales depuis le départ
    """
    # Initialisation
    distances = {ville: float('inf') for ville in reseau.graphe}
    distances[depart] = 0
    non_visites = set(reseau.graphe.keys())

    # À compléter : boucle principale de l'algorithme

    return distances

Test :

>>> dijkstra(reseau, "Nice")
{'Nice': 0, 'Monaco': 20, 'Cannes': 33, 'Grasse': 40, 'Antibes': 44, 'Menton': 30}

2.3. Sélection du minimum

Implémenter une fonction auxiliaire pour sélectionner le sommet non visité avec la plus petite distance :

def selectionner_minimum(distances, non_visites):
    """
    Sélectionne le sommet non visité avec la distance minimale.

    :param distances: (dict) Distances actuelles
    :param non_visites: (set) Ensemble des sommets non visités
    :return: (str) Le sommet avec la distance minimale
    """
    # À compléter
    pass

---

Partie 3 : Reconstruction du chemin

3.1. Mémorisation des prédécesseurs

Pour reconstruire le chemin, il faut mémoriser par quel sommet on est passé. Modifier dijkstra pour retourner aussi les prédécesseurs :

def dijkstra_avec_chemin(reseau, depart):
    """
    Dijkstra avec mémorisation des prédécesseurs.

    :return: (tuple) (distances, predecesseurs)
    """
    distances = {ville: float('inf') for ville in reseau.graphe}
    predecesseurs = {ville: None for ville in reseau.graphe}
    distances[depart] = 0
    non_visites = set(reseau.graphe.keys())

    while non_visites:
        courant = selectionner_minimum(distances, non_visites)
        non_visites.remove(courant)

        if distances[courant] == float('inf'):
            break

        for voisin, poids in reseau.get_voisins(courant):
            nouvelle_distance = distances[courant] + poids
            if nouvelle_distance < distances[voisin]:
                distances[voisin] = nouvelle_distance
                predecesseurs[voisin] = courant  # Mémoriser le prédécesseur

    return distances, predecesseurs

3.2. Reconstruction

Implémenter la fonction de reconstruction du chemin :

def reconstruire_chemin(predecesseurs, depart, arrivee):
    """
    Reconstruit le chemin du départ à l'arrivée.

    :param predecesseurs: (dict) Dictionnaire des prédécesseurs
    :param depart: (str) Ville de départ
    :param arrivee: (str) Ville d'arrivée
    :return: (list) Chemin sous forme de liste de villes
    """
    # À compléter
    pass

Test :

>>> distances, pred = dijkstra_avec_chemin(reseau, "Nice")
>>> reconstruire_chemin(pred, "Nice", "Menton")
['Nice', 'Monaco', 'Menton']

---

Partie 4 : GPS Navigator

4.1. Classe GPS

Créer une classe complète de navigation :

class GPSNavigator:
    """Système de navigation GPS."""

    def __init__(self):
        self.reseau = ReseauRoutier()

    def charger_carte(self, fichier):
        """Charge une carte depuis un fichier."""
        # Bonus : à implémenter
        pass

    def calculer_itineraire(self, depart, arrivee):
        """
        Calcule l'itinéraire optimal entre deux villes.

        :param depart: (str) Ville de départ
        :param arrivee: (str) Ville d'arrivée
        :return: (dict) Informations sur l'itinéraire
        """
        distances, predecesseurs = dijkstra_avec_chemin(self.reseau, depart)

        if distances[arrivee] == float('inf'):
            return {"erreur": "Aucun itinéraire trouvé"}

        chemin = reconstruire_chemin(predecesseurs, depart, arrivee)

        return {
            "depart": depart,
            "arrivee": arrivee,
            "distance": distances[arrivee],
            "chemin": chemin,
            "nb_etapes": len(chemin) - 1
        }

    def afficher_itineraire(self, itineraire):
        """Affiche l'itinéraire de manière lisible."""
        if "erreur" in itineraire:
            print(itineraire["erreur"])
            return

        print(f"\n{'='*50}")
        print(f"ITINÉRAIRE : {itineraire['depart']} → {itineraire['arrivee']}")
        print(f"{'='*50}")
        print(f"Distance totale : {itineraire['distance']} km")
        print(f"Nombre d'étapes : {itineraire['nb_etapes']}")
        print(f"\nChemin :")
        for i, ville in enumerate(itineraire['chemin']):
            if i < len(itineraire['chemin']) - 1:
                print(f"  {i+1}. {ville} →")
            else:
                print(f"  {i+1}. {ville} (arrivée)")
        print(f"{'='*50}\n")

4.2. Test complet

# Création du GPS
gps = GPSNavigator()

# Ajout des villes de la Côte d'Azur
villes = ["Nice", "Monaco", "Menton", "Cannes", "Antibes", "Grasse", "Vence"]
for ville in villes:
    gps.reseau.ajouter_ville(ville)

# Ajout des routes (distances en km)
routes = [
    ("Nice", "Monaco", 20),
    ("Monaco", "Menton", 10),
    ("Nice", "Cannes", 33),
    ("Nice", "Antibes", 23),
    ("Cannes", "Antibes", 11),
    ("Cannes", "Grasse", 17),
    ("Nice", "Grasse", 40),
    ("Nice", "Vence", 22),
    ("Grasse", "Vence", 15)
]
for v1, v2, dist in routes:
    gps.reseau.ajouter_route(v1, v2, dist)

# Calcul d'itinéraires
itineraire = gps.calculer_itineraire("Menton", "Grasse")
gps.afficher_itineraire(itineraire)

Sortie attendue :

==================================================
ITINÉRAIRE : Menton → Grasse
==================================================
Distance totale : 70 km
Nombre d'étapes : 3

Chemin :
  1. Menton →
  2. Monaco →
  3. Nice →
  4. Grasse (arrivée)
==================================================

---

Partie 5 : Améliorations (Bonus)

5.1. Itinéraire par temps de trajet

Modifier le système pour calculer l'itinéraire le plus rapide au lieu du plus court : - Stocker aussi la vitesse moyenne de chaque route - Calculer le temps de trajet : temps = distance / vitesse

5.2. Points d'intérêt

Ajouter la possibilité de passer par des points intermédiaires :

gps.calculer_itineraire_via("Nice", "Menton", via=["Monaco"])

5.3. Éviter certaines routes

Permettre d'éviter des routes (travaux, péages...) :

gps.calculer_itineraire("Nice", "Cannes", eviter=["autoroute"])

5.4. Visualisation

Utiliser matplotlib ou networkx pour afficher graphiquement le réseau et l'itinéraire calculé.

---

Partie 6 : Questions de synthèse

1. Quelle est la complexité temporelle de l'algorithme de Dijkstra avec notre implémentation ?

2. Comment améliorer les performances pour de très grands graphes (millions de sommets) ?

3. Pourquoi Dijkstra ne fonctionne-t-il pas avec des poids négatifs ?

4. Quel algorithme utiliseriez-vous pour trouver le chemin passant par tous les sommets exactement une fois ?

---

Barème indicatif

Partie	Points
Partie 1 : Modélisation	3
Partie 2 : Dijkstra	6
Partie 3 : Reconstruction	4
Partie 4 : GPS Navigator	5
Partie 5 : Bonus	2
Total	20

---

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.