- Actuel
- Dans la file
- Définitif
- Chemin
Algorithme de Dijkstra
L'algorithme de Dijkstra trouve le plus court chemin d'un départ vers chaque autre nœud quand les arêtes ont des longueurs, comme les routes entre des villes. Il s'étend depuis le départ, en prenant toujours le nœud le plus proche qu'il n'a pas encore terminé. Cliquez sur un nœud pour partir de lui, choisissez une cible si vous voulez, et avancez pas à pas pour voir la file, chaque distance qui baisse quand un chemin plus court apparaît, et le plus court chemin qui se dessine. Appuyez sur Lecture pour suivre la recherche, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Cliquez sur un nœud pour en faire le départ ; basculez le clic sur Cible et cliquez sur un autre nœud pour chercher un plus court chemin jusqu'à lui. Le nombre sur chaque arête est sa longueur, le nombre sur chaque nœud sa plus courte distance jusqu'ici, et la ligne sous le graphe est la file, du plus proche au plus éloigné. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Cliquez sur un nœud pour en faire le départ. Pour chercher un chemin, basculez le clic sur Cible et cliquez sur un autre nœud.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où dans la recherche.
- Observez la file sous le graphe et la distance sur chaque nœud. Nouveau graphe crée un autre graphe à essayer.
Comment fonctionne l'algorithme de Dijkstra
Donnez au départ la distance 0 et à tous les autres nœuds l'infini, et mettez le départ dans une file. Puis répétez : prenez le nœud de la file qui a la plus petite distance, et marquez cette distance comme définitive. Pour chacun de ses voisins non définitifs, ajoutez la longueur de l'arête à la distance du nœud. Si la somme est plus courte que la distance actuelle du voisin, elle devient sa nouvelle distance, le nœud est retenu comme chemin pour y aller, et le voisin entre dans la file s'il n'y était pas. Quand la file est vide, chaque nœud accessible a sa plus courte distance.
Pourquoi le nœud le plus proche est définitif
Quand un nœud est le plus proche dans la file, tout autre chemin jusqu'à lui doit quitter la partie terminée du graphe par un nœud de la file, au moins aussi éloigné, puis ajouter des arêtes qui ne peuvent pas être négatives. Aucun autre chemin ne peut donc être plus court. C'est aussi pourquoi une cible n'est sûre que lorsqu'elle sort de la file, et non quand elle est atteinte pour la première fois, et pourquoi l'algorithme de Dijkstra échoue avec des arêtes négatives : il faut alors l'algorithme de Bellman–Ford. Quand chaque arête a la longueur 1, l'algorithme de Dijkstra fait la même chose que le parcours en largeur.
Questions fréquemment posées
Qu'est-ce que l'algorithme de Dijkstra ?
Une méthode pour trouver les plus courts chemins d'un nœud de départ vers tous les autres nœuds d'un graphe dont les arêtes ont des longueurs nulles ou positives. Il prend à chaque fois le nœud non terminé le plus proche, rend sa distance définitive et utilise ses arêtes pour raccourcir les distances de ses voisins.
Pourquoi l'algorithme de Dijkstra ne fonctionne-t-il pas avec des arêtes négatives ?
Il rend la distance d'un nœud définitive dès que ce nœud est le plus proche dans la file. Une arête négative trouvée plus tard pourrait encore ramener à ce nœud par un chemin plus court, et la distance définitive serait alors fausse. L'algorithme de Bellman–Ford gère les arêtes négatives, tant qu'il n'y a pas de cycle de total négatif.
Quelle est la différence entre Dijkstra et BFS ?
Le parcours en largeur compte les arêtes et utilise une file simple. L'algorithme de Dijkstra additionne les longueurs des arêtes et utilise une file de priorité qui donne toujours le nœud le plus proche. Si chaque arête a la longueur 1, les deux trouvent les mêmes distances.
L'algorithme de Dijkstra est-il rapide ?
Avec un tas binaire comme file de priorité, le travail croît comme (V + E) log V pour V nœuds et E arêtes. Avec un tas de Fibonacci, c'est E + V log V. L'application garde la file sous forme de liste triée, simple à montrer et suffisante pour de petits graphes.
Mon graphe est-il envoyé quelque part ?
Non. Le graphe est créé et parcouru dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur