Informatique · Algorithmes

Laboratoire des algorithmes sur graphes pondérés

Un même graphe, trois questions : quel est le plus court chemin ? Comment relier tous les sommets avec le poids total minimal ?

Lire l’article sur les trois algorithmes

Dijkstra fixe à chaque étape le sommet non visité dont la distance provisoire est la plus petite. Les poids doivent être non négatifs ; ici ils vont de 1 à 20.

Graphe prêt. Cliquez sur Démarrer ou Étape suivante.

Étape0 / 0

Arêtes choisies0

Distance à la cible—

Arêtes rejetées0

Arête non choisie Arête choisie Arête examinée Chemin vers la cible

Que voit-on ?

Dijkstra résout un problème de chemins. Prim et Kruskal cherchent un arbre couvrant de poids minimum : leurs arêtes peuvent différer, mais le poids total minimum est le même. La disposition suit des positions géométriques ; les poids sont aléatoires et ne représentent pas les distances à l’écran.