Leçon 4 sur 5
Le plus court chemin : Dijkstra
Je sais poser un problème de plus court chemin dans un graphe pondéré, appliquer l'algorithme de Dijkstra en tenant un tableau, reconstituer le chemin et connaître les limites de l'algorithme.
- 1 h 10
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Définir le poids d'un chemin et la distance dans un graphe pondéré (orienté ou non)
- Appliquer l'algorithme de Dijkstra pas à pas avec un tableau et des prédécesseurs
- Reconstituer un plus court chemin et l'arbre des plus courts chemins
- Expliquer pourquoi l'algorithme exige des poids positifs ou nuls
Avant de commencer : Leçons 1 à 3 de ce cours (graphes, chemins, connexité, arbres).
1Je découvre
Une société de livraison de Conakry reçoit une commande urgente de médicaments pour une pharmacie. Le livreur part de l'entrepôt et doit traverser plusieurs carrefours. Pour chaque tronçon de route, l'entreprise connaît le temps moyen de trajet aux heures de pointe, en minutes. Le chemin qui paraît le plus direct sur la carte passe par un carrefour souvent embouteillé ; un détour peut être plus rapide.
Le responsable veut une méthode systématique, programmable sur un téléphone, qui donne à coup sûr l'itinéraire le plus rapide, et même les meilleurs itinéraires depuis l'entrepôt vers tous les clients. Essayer tous les chemins possibles serait beaucoup trop long dès que le réseau grandit.
Cette méthode existe depuis la fin des années 1950 : c'est l'algorithme de Dijkstra, du nom de l'informaticien néerlandais Edsger Dijkstra. C'est le même principe que celui qu'utilisent, sous des formes améliorées, de nombreuses applications de navigation.
Comment trouver le plus court chemin d'un sommet à tous les autres dans un graphe pondéré ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.