Aller au contenu
Théorie des graphes · L1

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.

Voir toutes les leçons de Théorie des graphes

Signaler une erreur dans cette leçon

Toutes les leçons de Théorie des graphes

Pose ta question à Karamö