Aller au contenu
Retour aux projetsjulyanOS
Projet C++ / QtTerminé
Dépôt GitHub

Planificateur d'Itinéraires & Carte Interactive

Une application GUI moderne développée en C++17 et Qt pour interroger, calculer et visualiser les trajets optimaux entre villes françaises grâce à l'algorithme de Floyd-Warshall.

Période
Mars 2026
Cadre
Projet scolaire
Équipe
Solo
Rôle
Conception et développement
Lecture
environ 4 min
  • Floyd-Warshall précalculé au chargement : O(n³)
  • Distance entre deux villes ensuite en O(1)
Capture d'écran de l'application GPS en C++ Qt
~/stack.json
"Langage & Standard":
C++17
"Framework GUI":
Qt 5 / Qt 6 (Widgets)
"Algorithmique":
Floyd-Warshall (Graphes)
"API Extérieure":
OpenWeatherMap REST API
Itinéraires · France

Contexte

Pas de service web, pas de clé API cachée dans un fichier de config : le calcul d'itinéraire tourne entièrement en local, en C++, sur une matrice de distances pré-calculée au démarrage. Interroger n'importe quel trajet entre deux villes devient une simple lecture - pas un nouveau calcul à chaque clic.

C++17Qt WidgetsQGraphicsViewQNetworkAccessManagerParsing CSVJSON REST
~/gps/data
  • villes.csv - Coordonnées GPS & population
  • temps.csv - Matrice des durées de trajet

Algorithme : Floyd-Warshall

Plutôt que d'exécuter un algorithme de Dijkstra à chaque nouvelle recherche de chemin (qui recalculerait les chemins à partir d'un seul sommet source), ce projet utilise l'algorithme de Floyd-Warshall pré-calculé au chargement des données.

  • Temps de réponse instantané (O(1)) : La matrice prochain permet de reconstituer immédiatement n'importe quel itinéraire entre deux villes sans re-parcourir le graphe.
  • Adapté aux comparateurs multi-villes : Permet de générer instantanément les matrices comparatives entre toutes les villes sélectionnées.
Triple boucle de Floyd-Warshall et matrice prochainfloydwarshall.cpp, lignes 28 à 46Voir sur GitHub
for(int k = 0; k < n; k++) { //pour chaque ville intermédiaire possible
    for(int i = 0; i < n; i++) { //pour chaque ville de départ
        for(int j = 0; j < n; j++) { //pour chaque ville d'arrivée
            //On vérifie que les segments (i->k) et (k->j) sont valides (pas INF)
            if (W[i][k] != INF && W[k][j] != INF) {

                // Si le passage par 'k' réduit la distance totale entre i et j
                if (W[i][k] + W[k][j] < W[i][j]) {
                    W[i][j] = W[i][k] + W[k][j]; // On met à jour la distance minimale

                    // INSPIRATION DU CODE :
                    // Pour aller de i à j via k, le prochain pas est le même
                    // que celui pour aller de i vers k.
                    prochain[i][j] = prochain[i][k];
                }
            }
        }
    }
}

Architecture

  1. villes.csv, temps.csvcoordonnées, populations, durées
  2. Parseurs CSVchargés au démarrage
  3. Graphematrice d'adjacence
  4. Floyd-Warshallpré-calcul unique au chargement
  5. Itinéraireslecture de la matrice prochain
  1. API OpenWeatherMapREST, JSON
  2. QNetworkAccessManagerappels asynchrones
  3. MainWindowcarte QGraphicsView, météo par étape
Schéma illustratif, construit à partir des composants décrits sur cette page.

Fonctionnalités

Calcul d'Itinéraire Multi-étapes

Recherche du chemin le plus rapide entre deux villes avec possibilité d'ajouter des étapes intermédiaires personnalisables et calcul dynamique du temps cumulé.

Carte Vectorielle & Level of Detail (LOD)

Rendu interactif via QGraphicsView avec projection GPS adaptative, tracé en courbes de Bézier, zoom au curseur et affichage progressif des villes selon le niveau de zoom.

Animation de Trajet Pas à Pas

Simulation visuelle du déplacement d'un véhicule le long du tracé calculé avec suivi dynamique.

Météo en Temps Réel (API OpenWeatherMap)

Appels HTTP asynchrones (QNetworkAccessManager) pour récupérer les conditions météorologiques (température, vent, humidité) au départ, à l'arrivée et sur chaque étape.

Comparateur de Distances & Export

Tableau croisé des temps de parcours entre une sélection de villes, bascule en mode sombre et exportation d'image de la carte (.png / .jpg).

Défis et solutions

1. Rendu Graphique & Projection GPS

La projection GPS → pixels, c'est le genre de détail qu'on croit trivial jusqu'à devoir le garder fluide au zoom. QGraphicsView aide, mais la logique de conversion elle-même reste entièrement maison.

2. Requêtes Asynchrones sans Gel de l'UI

Utilisation des signaux/slots de Qt et de QNetworkAccessManager pour effectuer les appels REST vers l'API OpenWeatherMap de façon asynchrone sans bloquer l'interface graphique.

Ce que j'ai appris

C++ Avancé & Qt Framework

Maîtrise de l'architecture événementielle (Signals & Slots), de la gestion de la mémoire, de la manipulation des widgets complexes et de la séparation entre la vue (IHM) et la logique métier.

Théorie des Graphes

Implémentation concrète de graphes via des matrices d'adjacence, manipulation de l'algorithme de Floyd-Warshall et reconstruction dynamique de plus courts chemins.

Intégration d'API REST & JSON

Consommation de services Web externe, parsing de flux JSON via QJsonDocument et gestion robuste des erreurs réseau et d'accès API.

Parsing & Structuration

Création de parsers CSV personnalisés et fiables pour charger dynamiquement les données géographiques et temporelles au démarrage.

Ce que je ferais différemment

Une matrice dimensionnée par les données

La matrice prochain est un tableau statique de 100 x 100 : le graphe ne peut pas dépasser 100 villes. Une structure dynamique (std::vector) dimensionnée au chargement du CSV lèverait cette limite sans changer l'algorithme.