C'est très volontiers que je t'aide à comprendre Dijkstra. J'expliquerais très brièvement les principes puis si tu ne comprends pas, il faut que tu dises un peu plus clairement où ça coince. D'ailleurs tu as déjà fait une petite recherche avec Google? Il y a sûrement plein de pages qui parlent de cet algorithme, c'est un classique!

L'idée c'est qu'on a un graphe avec des poids sur les arêtes. Tu peux t'imaginer que c'est un plan de ville et que les poids des arêtes c'est la distance (en temps ou en kilomètres) pour un trajet donné. Tu vas d'un point de la carte précis à un (ou plusieurs) autre(s) et tu aimerais connaître la longueur du chemin le plus court (et le chemin aussi de préférence).

On va assigner un nombre à chaque sommet i, qui correspondra à la distance du point de départ (0) au sommet en question (i). Au début on pose (on part au kilomètre 0) et pour les autres sommets (on ne connaît pas encore de plus court chemin). On marque le sommet 0.

Ensuite on regarde tous les sommets voisins de 0. Si la longueur du trajet est plus petit que , c'est qu'on vient de trouver un plus court chemin de 0 à i. (Pour l'instant c'est évident.) On note et il faut encore noter que le sommet précédant i dans ce plus court chemin est 0 (pour pouvoir retrouver le plus court chemin à la fin).

Parmi tous les voisins de 0, on choisi le plus proche que j'appelle 1. On le marque (on a trouvé un plus court chemin de 0 à 1). Là on recommence en cherchant tous ses voisins. Si on change le chemin le plus court de 0 à i car on a trouvé un chemin plus court en passant par 1. Ensuite on recommence en prennant le sommet non marqué ayant le plus petit .

Le seul souci que tu peux avoir avec cet algo c'est si jamais on est en train d'étudier les voisins de k (marqué) et qu'on trouve un sommet i déjà marqué avec . Ceci veut dire qu'il existe une boucle de longueur négative, mais tu étudieras ce cas de préférence après avoir compris comment fonctionne l'algorithme quand "tout va bien".

L'idée à retenir c'est qu'on construit le plus court chemin petit à petit en regardant les chemins "via" un autre sommet pour lequel on connaît déjà le plus court chemin. J'espère que j'ai pu t'aider un peu.

Isis