Pour aller plus loin : l'algorithme de Dijkstra pour calculer un nombre de chemins

👉 Des fiches d'exercices (non visibles actuellement sur l'application) existent, elles sont disponibles depuis le site internet https://www.digischool.fr/lycee

1. L’idée générale

L’algorithme de Dijkstra sert à trouver le chemin le plus court entre un point de départ et tous les autres points d’un graphe.
Par exemple : si tu veux aller de chez toi à différents amis dans une ville, Dijkstra t’aide à savoir quel est le chemin le plus rapide pour chacun.

2. Le matériel de départ

On a :

• Un graphe avec des sommets (les points, comme des villes ou des stations) et des arêtes avec un poids (la distance ou le temps entre deux points).

• Un point de départ (par exemple ta maison).

• Une sorte de tableau où l’on note la distance connue la plus courte pour aller à chaque sommet. Au début, on met :

  • 0 pour le sommet de départ (car on est déjà dessus),

  • ∞ (infinie) pour tous les autres (on ne sait pas encore combien ça coûte).

3. Les étapes de l’algorithme

On répète plusieurs fois les actions suivantes :

1. Choisir le sommet non encore traité avec la plus petite distance connue.
   (Au début, c’est ton point de départ car sa distance est 0.)

2. Marquer ce sommet comme "traité".
   Cela veut dire qu’on a trouvé la distance la plus courte pour aller jusqu’à lui, et on ne la changera plus.

3. Mettre à jour les voisins :

   • On regarde tous les sommets directement reliés à ce sommet.

   • Pour chacun, on calcule la nouvelle distance possible en passant par lui :
     nouvelle distance = distance actuelle du sommet + poids de l’arête.

   • Si cette nouvelle distance est plus petite que la distance déjà notée pour ce voisin, on met à jour.

4. Recommencer :
   On retourne à l’étape 1, jusqu’à ce que tous les sommets soient traités ou qu’on ait trouvé ce qu’on voulait.

4. Exemple simple

Imagine un graphe avec 4 sommets : A, B, C, D.

• De A à B : 2

• De A à C : 5

• De B à C : 1

• De B à D : 4

• De C à D : 1

Départ = A

1. Tableau initial :
   A=0, B=∞, C=∞, D=∞

2. On choisit A (le plus petit = 0).

   • Voisin B : 0+2=2 → B=2

   • Voisin C : 0+5=5 → C=5
     Résultat : A=0, B=2, C=5, D=∞

3. On choisit B (distance 2).

   • Voisin C : 2+1=3 < 5 → on met C=3

   • Voisin D : 2+4=6 → D=6
     Résultat : A=0, B=2, C=3, D=6

4. On choisit C (distance 3).

   • Voisin D : 3+1=4 < 6 → on met D=4
     Résultat : A=0, B=2, C=3, D=4

5. On choisit D (distance 4). Rien à mettre à jour.

👉 Chemins les plus courts trouvés :

• A→B = 2

• A→C = 3 (en passant par B)

• A→D = 4 (en passant par C)

5. À retenir

• On part d’un tableau de distances avec ∞ partout sauf 0 au départ.

• On choisit toujours le plus petit non encore traité.

• On met à jour les voisins.

• À la fin, on connaît le chemin le plus court de départ à chaque sommet.

Voici un schéma étape par étape de l’algorithme de Dijkstra appliqué à notre petit graphe (A, B, C, D).
En rouge sous chaque sommet, tu vois la distance la plus courte connue à chaque étape :

• Étape 1 : On part de A (0). On met B=2, C=5.

• Étape 2 : On choisit B (2). On met à jour C=3, D=6.

• Étape 3 : On choisit C (3). On met à jour D=4.

• Étape 4 : On choisit D (4). Fini.

👉 On retrouve bien :

• chemin A→B = 2

• chemin A→C = 3 (via B)

• chemin A→D = 4 (via C).

Voici le graphe final :

• Les arêtes en vert correspondent aux plus courts chemins depuis A.

• On lit directement :

  • A→B = 2

  • A→C = 3 (A→B→C)

  • A→D = 4 (A→B→C→D).

Étape 1 : On part de A

• Distance connue : A = 0

• On regarde ses voisins :

  • A→B coûte 2 → B devient 2

  • A→C coûte 5 → C devient 5

Tableau :

• A = 0 (fixé ✅)

• B = 2

• C = 5

• D = ∞

Étape 2 : On prend B (le plus petit = 2)

• Distance connue : B = 2

• On regarde ses voisins :

  • B→C = 2 + 1 = 3 < 5 → C devient 3

  • B→D = 2 + 4 = 6 → D devient 6

Tableau :

• A = 0 (✅)

• B = 2 (✅)

• C = 3

• D = 6

Étape 3 : On prend C (le plus petit = 3)

• Distance connue : C = 3

• On regarde ses voisins :

  • C→D = 3 + 1 = 4 < 6 → D devient 4

Tableau :

• A = 0 (✅)

• B = 2 (✅)

• C = 3 (✅)

• D = 4

Étape 4 : On prend D (le plus petit = 4)

• Distance connue : D = 4

• Aucun voisin n’améliore les distances.

Tableau final :

• A = 0

• B = 2

• C = 3

• D = 4

Résultats : les chemins les plus courts

• A → B : direct, distance = 2

• A → C : en passant par B (A→B→C), distance = 3

• A → D : en passant par B et C (A→B→C→D), distance = 4

👉 En résumé :
Dijkstra, c’est comme une exploration où tu choisis toujours le point le plus proche non encore fixé, et tu mets à jour les distances de ses voisins.
À la fin, tu obtiens les distances minimales et les chemins optimaux.