Thème : Algorithmes de graphes et applications
❓ Problématique
Comment l'algorithme de Dijkstra, conçu pour trouver le plus court chemin dans un graphe, est-il utilisé dans les systèmes de navigation par satellite (GPS) pour optimiser nos trajets ?
🎓 Questions possibles du jury
Pourquoi l'algorithme de Dijkstra ne fonctionne-t-il pas avec des poids négatifs ?
Comment pourrait-on prendre en compte des informations de trafic en temps réel dans ce modèle ?
Prêt à t'entraîner ? Ketty joue le jury et te pose les vraies questions.
💡 Conseils
- ✓Préparez un schéma clair d'un petit graphe routier pour illustrer les étapes de l'algorithme au tableau.
- ✓Pensez à mentionner des alternatives comme A* ou des adaptations pour les très grands graphes (contraction hiérarchique).
