Edsger Dijkstra était un mathématicien Néerlandais né le 11 mai 1930. Il est notamment pour avoir reçu en 1972 le prix de Turing pour ses contributions en algorithmique.
En 1959 il crée notamment un algorithme capable de résoudre le problème du plus court chemin: l’algorithme de Dijkstra. Cet algorithme peut être utilisé dans un graphe orienté ou non dont les arrêtes sont munies de poids afin trouver le plus court chemin entre les 2 sommets d’un graphe.
Au départ on considère que les distances de chaque sommets du graphe sont infinie excepter pour le sommet de départ dont la distance est initialisée à nulle. Puis on choisis à chaque itération le sommet voisins avec la distances la plus courte et on met à jour la distance des voisins de ce sommet et on répète cet itération jusqu’à avoir atteint le sommet souhaité.
Exemple: Nous cherchons le chemin le plus court pour aller de Sélestat à Strasbourg
Étape 1: On choisi Sélestat comme point de départ
Etape 2: On choisi Souffelweyersheim
Etape 3: On choisi Niederschaeffolsheim
Etape 4: On choisi Marckolsheim
Etape 5: On choisi Oberkutzenhausen
Etape 6: On choisi Strasbourg
Remarque: Si la distance aurait était de 35Km par exemple entre Marckolsheim et Oberkutzenhausen. Alors l’algorithme aurait choisis de retourner sur Niederschaeffolsheim pour aller directement sur Strasbourg.
Graphes et Algorithmes 