http://membres.multimania.fr/baekoasiswww.baekoasis.i8.comAlgorithme de Dijkstra est un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres.
Numérotons les sommets du graphe G = (V, E) de 1 à n. Supposons que l'on s'intéresse aux chemins partant du sommet 1. On construit un vecteur l = (l(1); l(2); ...; l(n)) ayant n composantes tel que l(j) soit égal à la longueur du plus court chemin allant de 1 au sommet j.
On initialise ce vecteur à c1,j, c'est-à-dire à la première ligne de la matrice des coûts du graphe, définie comme indiqué ci-dessous :
0 si i= j
Cij = ∞ si i≠ j et (i , j) E
d(i , j) si i≠ j et (i , j) E
où d(i,j) est le poids (la longueur) de l'arc (i, j). Les cij doivent être strictement positifs.
On construit un autre vecteur p pour mémoriser le chemin pour aller du sommet 1 au sommet voulu. La valeur p(i) donne le sommet qui précède i dans le chemin.
On considère ensuite deux ensembles de sommets, S initialisé à {1} et T initialisé à {2, 3, ..., n}. ہ chaque pas de l'algorithme, on ajoute à S un sommet jusqu'à ce que S = V de telle sorte que le vecteur l donne à chaque étape le coût minimal des chemins de 1 aux sommets de S.
Description de l'algorithme de Dijkstra
On suppose ici que le sommet de départ (qui sera la racine de l'arborescence) est le sommet 1. Notons qu'on peut toujours renuméroter les sommets pour que ce soit le cas.
Initialisations
l(j) = c1,j et p(j) = NIL, pour 1 <= j <= n
Pour 2 <= j <= n faire
Si c1,j < ∞ alors p(j) = 1.
S = {1} ; T = {2, 3, ..., n}.
Itérations
Tant que T n'est pas vide faire
Choisir i dans T tel que l(i) est minimum
Retirer i de T et l'ajouter à S
Pour chaque successeur j de i, avec j dans T, faire
Si l(j) > l(i) + d(i, j) alors
l(j) = l(i) + d(i, j)
p(j) = i
Ecrire un programme qui implémente l’algorithme de Dijkstra.