Imaginez que vous soyez le gérant d’un petit camping composé de 13 caravanes.
Malheureusement, tous les jours, avec votre petite fourgonette, vous devez nettoyer les allées reliant toutes ces caravanes.
Pour économiser du temps et du carburant, quel chemin devrez-vous emprunter pour ne passer qu’une seule par toutes les allées ?
A votre place, je commencerais par un faire un schéma de la situation et d’essayer de trouver le chemin le plus court qui me permettra de ne passer qu’une seule fois par toutes les allées, et d’ainsi économiser un temps précieux. C’est l’été, il fait chaud, aucune envie de traîner dehors !!
Apres une nuit blanche, ça y est, vous l’avez enfin trouvé !!
Il est 8 heures du matin, vous avez tout juste le temps de sortir, attraper vos outils pour le grand nettoyage des allées, que votre cousine vous saute au cou… Elle vient d’avoir son bac ES !!
Vous lui expliquez alors votre aventure intellectuelle nocturne, épuisante mais finalement productive… « Mais enfin, pourquoi n’as-tu pas appliqué l’algorithme de Dijkstra ?!, tu aurais trouvé ton plus court chemin en 5 minutes. »
Alors, qui est ce Dijkstra, et comment ça marche ?
Edsger (Edgar) Wybe Dijkstra (1930-2002), néerlandais, né à Rotterdam, fut, dans les années 1950, un pionnier de l’informatique. Il étudie les mathématiques et la physique à l’université de Leyde puis s’oriente vers l’informatique théorique, et les langages de programmation. Il obtient son doctorat à Amsterdam.
Enseignant et programmeur, il effectua jusqu’en 1984 beaucoup de recherches pour la compagnie informatique Burroughs Corporation, puis se consacra à la recherche au département informatique de l’université du Texas, Austin.
En 1972, Dijkstra reçoit le prix Turing pour ses travaux, récompensant la mise au point du langage ALGOL 60.
Dijkstra disparaît en 2002 d’un cancer. Il reçoit le prix PoDC à titre posthume, renommé le prix Dijkstra en son honneur.
L’algorithme de Dijkstra est créé en 1959. Cet algorithme est une méthode simple et efficace pour déterminer le chemin le plus court d’un lieu à une autre.
Il très utilisé aussi bien à des fins civils que militaires : aide à la décision, stratégie, optimisation des distances de livraisons, etc.
Dijkstra, connu aussi pour son caractère difficile et son intransigeance, est à l’origine de plusieurs aphorismes, qui résument sa vison de la science informatique. En voici quelques-uns :
Revenons à notre camping !!
Quel est le plus court chemin qui vous permettra de passer une et une seule par toutes les allées ?
Entrainez-vous d’abord sur un exemple simple ici : https://www.youtube.com/watch?v=MybdP4kice4
redisje.com 