Algorithme de Dijkstra
Les plus courts chemins depuis une source dans un graphe à poids positifs : tableau des distances provisoires et des prédécesseurs, choix du sommet le plus proche, mise à jour des voisins, lecture du chemin, échec avec un poids négatif et coût avec une file de priorité.
- 26 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Distance provisoire : de quoi s'agit-il ?
Voir la réponse
Longueur du meilleur chemin trouvé jusqu'ici entre la source et un sommet, valeur qui peut encore baisser tant que ce sommet n'est pas fixé.
Au départ elle vaut 0 pour la source et l'infini pour les autres sommets. Une fois le sommet fixé, elle devient sa vraie distance et ne change plus.
Dans ce graphe non orienté, A est la source. Après avoir fixé A (distance 0), quel sommet l'algorithme de Dijkstra fixe-t-il ensuite ?
```text
A - B : 4
A - C : 2
B - C : 1
B - D : 5
C - D : 8
C - E : 10
D - E : 2
D - F : 6
E - F : 3`- C, de distance provisoire 2
- B, de distance provisoire 4
- D, voisin de B et de C
- B, le premier voisin de A par ordre alphabétique
Voir la réponse
C, de distance provisoire 2
Après A, les distances provisoires sont B = 4 et C = 2 ; les autres valent l'infini. On fixe le plus petit, C. L'ordre alphabétique ne joue aucun rôle dans Dijkstra, seule compte la distance.
À chaque tour, l'algorithme de Dijkstra … le sommet non fixé dont la distance provisoire est la …, puis met à jour ses voisins.
Voir la réponse
À chaque tour, l'algorithme de Dijkstra fixe le sommet non fixé dont la distance provisoire est la plus petite, puis met à jour ses voisins.
C'est un choix glouton : on ne reviendra jamais sur ce sommet. Il est correct parce que les poids ne sont pas négatifs.
Sommet fixé : de quoi s'agit-il ?
Voir la réponse
Sommet dont la distance à la source est définitive : l'algorithme a prouvé qu'aucun autre chemin ne peut être plus court.
À chaque tour, on fixe le sommet non fixé de plus petite distance provisoire. Tout autre chemin vers lui passerait par un sommet au moins aussi loin, et les poids positifs ne le raccourcissent pas.