MetMat
← Retour aux méthodes

Comment implémenter l'algorithme de Dijkstra pour les plus courts chemins ?

En maintenant un tableau des distances, en sélectionnant à chaque étape le sommet non visité de distance minimale, puis en relâchant ses voisins

L'objectif

Calculer, dans un graphe pondéré à poids positifs, la distance minimale du sommet source ss à chacun des autres sommets.

Le principe

À chaque étape, on sélectionne parmi les sommets non visités celui dont la distance provisoire est minimale (ce choix est correct car les poids sont positifs), on le marque visité, puis on relâche ses voisins en posant dist[v]=min⁡(dist[v],  dist[u]+w(u,v))\mathrm{dist}[v]=\min(\mathrm{dist}[v],\;\mathrm{dist}[u]+w(u,v)) pour chaque voisin vv non visité.

La méthode
  1. 1
    J'initialise dist à +∞+\infty partout sauf dist[s] = 0, et un ensemble visites vide ; je choisis une représentation du graphe (dictionnaire {u: [(v, poids), ...]} ou matrice d'adjacence pondérée).
    Voir
  2. 2
    Tant qu'il reste un sommet non visité de distance finie, je sélectionne le sommet uu non visité minimisant dist[u], je l'ajoute à visites, puis pour chaque voisin vv de uu non visité je relâche : dist[v] = min(dist[v], dist[u] + w(u,v)).
  3. 3
    Quand tous les sommets accessibles sont visités, je renvoie le tableau dist : dist[t] est la distance minimale de ss à tt (ou +∞+\infty si tt n'est pas accessible).

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.