Edsger Dijkstra était un mathématicien Néerlandais né le 11 mai 1930. Il est notamment connu 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 de trouver le plus court chemin entre les 2 sommets d’un graphe.
Au départ on considère que les distances de chaque sommet du graphe sont infinies excepter pour le sommet de départ dont la distance est initialisée à nulle. Puis on choisit à chaque itération le sommet voisins avec la distance la plus courte et on met à jour la distance des voisins de ce sommet et on répète cette 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 choisit Sélestat comme point de départ
Etape 2: On choisit Souffelweyersheim
Etape 3: On choisit Niederschaeffolsheim
Etape 4: On choisit Marckolsheim
Etape 5: On choisit Oberkutzenhausen
Etape 6: On choisit Strasbourg
Remarque : Si la distance aurait été de 35Km par exemple entre Marckolsheim et Oberkutzenhausen. Alors l’algorithme aurait choisis de retourner sur Niederschaeffolsheim pour aller directement à Strasbourg.
Graphes et Algorithmes 