


Comprendre l'algorithme de Dijkstra : de la théorie à la mise en œuvre
L'algorithme de Dijkstra est un algorithme de recherche de chemin classique utilisé en théorie des graphes pour trouver le chemin le plus court entre un nœud source et tous les autres nœuds d'un graphique. Dans cet article, nous explorerons l'algorithme, sa preuve d'exactitude et fournirons une implémentation en JavaScript.
Qu'est-ce que l'algorithme de Dijkstra ?
L'algorithme de Dijkstra est un algorithme glouton conçu pour trouver les chemins les plus courts à partir d'un seul nœud source dans un graphe pondéré avec des poids de bord non négatifs. Il a été proposé par Edsger W. Dijkstra en 1956 et reste l'un des algorithmes les plus utilisés en informatique.
Entrée et sortie
- Entrée : Un graphique G=(V,E) , où V est l'ensemble des sommets, E est l'ensemble des arêtes et un nœud source s∈V .
- Sortie : Les distances de chemin les plus courtes depuis s à tous les autres nœuds de V .
Concepts de base
- Relaxation : Le processus de mise à jour de la distance connue la plus courte jusqu'à un nœud.
- File d'attente prioritaire : Récupère efficacement le nœud avec la plus petite distance provisoire.
- Approche gourmande : Traite les nœuds par ordre non décroissant de leurs distances les plus courtes.
L'algorithme
-
Initialiser les distances :
dist(s)=0,dist(v)=∞∀v=s Utilisez une file d'attente prioritaire pour stocker les nœuds en fonction de leurs distances.
Extraire à plusieurs reprises le nœud avec la plus petite distance et détendre ses voisins.
Détente - Explication mathématique
- Initialisation : dist(s)=0,dist(v)=∞pour un llv=s
où (s) est le nœud source, et (v) représente n'importe quel autre nœud.
-
Étape de relaxation : pour chaque bord
(u,v)
avec du poids
w(u,v)
:
Si
dist(v)>dist (tu) w(u,v)
, mise à jour:
dist(v)=dist(u) w(u,v),prev(v)=u
Pourquoi ça marche : La relaxation garantit que nous trouvons toujours le chemin le plus court vers un nœud en mettant progressivement à jour la distance lorsqu'un chemin plus court est trouvé.
File d'attente prioritaire - Explication mathématique
-
Opération de file d'attente :
- La file d'attente prioritaire retire toujours le nœud de la file d'attente
(u)
avec la plus petite distance provisoire :
u=argv∈Q mindist(v)
- Pourquoi ça marche : En traitant le nœud avec le plus petit (dist(v)) , nous garantissons le chemin le plus court de la source à (u) .
- La file d'attente prioritaire retire toujours le nœud de la file d'attente
(u)
avec la plus petite distance provisoire :
Preuve d'exactitude
Nous prouvons l'exactitude de l'algorithme de Dijkstra en utilisant une forte induction.
Qu'est-ce que l'induction forte ?
L'induction forte est une variante de l'induction mathématique où, pour prouver une affirmation (P(n)) , nous supposons la vérité de (P(1),P(2),…,P(k)) prouver ( P(k 1)) . Cela diffère de l'induction régulière, qui suppose uniquement (P(k)) prouver ( P(k 1)) . Explorez-le plus en détail dans mon autre article.
Exactitude de l'algorithme de Dijkstra (preuve inductive)
Cas de base :
Le nœud source (s) est initialisé avec dist(s)=0 , ce qui est exact.Hypothèse inductive :
Supposons que tous les nœuds traités jusqu'à présent ont les distances de chemin les plus courtes correctes.Étape inductive :
Le prochain nœud (u) est retiré de la file d'attente prioritaire. Depuis dist(u) est la plus petite distance restante, et tous les nœuds précédents ont des distances correctes, dist(u) est également correct.
Implémentation JavaScript
Prérequis (file d'attente prioritaire) :
// Simplified Queue using Sorting // Use Binary Heap (good) // or Binomial Heap (better) or Pairing Heap (best) class PriorityQueue { constructor() { this.queue = []; } enqueue(node, priority) { this.queue.push({ node, priority }); this.queue.sort((a, b) => a.priority - b.priority); } dequeue() { return this.queue.shift(); } isEmpty() { return this.queue.length === 0; } }
Voici une implémentation JavaScript de l'algorithme de Dijkstra utilisant une file d'attente prioritaire :
function dijkstra(graph, start) { const distances = {}; // hold the shortest distance from the start node to all other nodes const previous = {}; // Stores the previous node for each node in the shortest path (used to reconstruct the path later). const pq = new PriorityQueue(); // Used to efficiently retrieve the node with the smallest tentative distance. // Initialize distances and previous for (let node in graph) { distances[node] = Infinity; // Start with infinite distances previous[node] = null; // No previous nodes at the start } distances[start] = 0; // Distance to the start node is 0 pq.enqueue(start, 0); while (!pq.isEmpty()) { const { node } = pq.dequeue(); // Get the node with the smallest tentative distance for (let neighbor in graph[node]) { const distance = graph[node][neighbor]; // The edge weight const newDist = distances[node] + distance; // Relaxation Step if (newDist < distances[neighbor]) { distances[neighbor] = newDist; // Update the shortest distance to the neighbor previous[neighbor] = node; // Update the previous node pq.enqueue(neighbor, newDist); // Enqueue the neighbor with the updated distance } } } return { distances, previous }; } // Example usage const graph = { A: { B: 1, C: 4 }, B: { A: 1, C: 2, D: 5 }, C: { A: 4, B: 2, D: 1 }, D: { B: 5, C: 1 } }; const result = dijkstra(graph, 'A'); // start node 'A' console.log(result);
Reconstruire le chemin
// Simplified Queue using Sorting // Use Binary Heap (good) // or Binomial Heap (better) or Pairing Heap (best) class PriorityQueue { constructor() { this.queue = []; } enqueue(node, priority) { this.queue.push({ node, priority }); this.queue.sort((a, b) => a.priority - b.priority); } dequeue() { return this.queue.shift(); } isEmpty() { return this.queue.length === 0; } }
Exemple de procédure pas à pas
Représentation graphique
- Nœuds : A,B,C,D
-
Bords :
- A→B=(1),A →C=(4)
- B→C=(2),B →D=(5)
- C→D=(1)
Exécution étape par étape
-
Initialiser les distances :
dist(A)=0,dist(B)= ∞,dist(C)=∞,dist(D)=∞ -
Processus A :
- Détendez les bords :
A→B,A→C.
dist(B)=1,dist(C)=4
- Détendez les bords :
A→B,A→C.
-
Processus B :
- Détendez les bords :
B→C,B→D.
dist(C)=3,dist(D)=6
- Détendez les bords :
B→C,B→D.
-
Processus C :
- Bord détente :
C→D.
dist(D)=4
- Bord détente :
C→D.
-
Processus D :
- Aucune autre mise à jour.
Distances finales et chemin
Optimisations et complexité temporelle
Comparaison des complexités temporelles de l'algorithme de Dijkstra avec différentes implémentations de files d'attente prioritaires :
Priority Queue Type | Insert (M) | Extract Min | Decrease Key | Overall Time Complexity |
---|---|---|---|---|
Simple Array | O(1) | O(V) | O(V) | O(V^2) |
Binary Heap | O(log V) | O(log V) | O(log V) | O((V E) log V) |
Binomial Heap | O(log V) | O(log V) | O(log V) | O((V E) log V) |
Fibonacci Heap | O(1) | O(log V) | O(1) | O(V log V E) |
Pairing Heap | O(1) | O(log V) | O(log V) | O(V log V E) (practical) |
Points clés :
-
Tableau simple :
- Inefficace pour les grands graphiques en raison de la recherche linéaire de l'extrait-min.
-
Tas binaire :
- Standard et couramment utilisé en raison de son équilibre entre simplicité et efficacité.
-
Tas binomial :
- Des garanties théoriques un peu meilleures mais plus complexes à mettre en œuvre.
-
Tas de Fibonacci :
- Meilleures performances théoriques avec ( O(1) ) touche de diminution amortie, mais plus difficile à mettre en œuvre.
-
Tas d'appariement :
- Simple et performant proche du tas de Fibonacci en pratique.
Conclusion
L'algorithme de Dijkstra est une méthode puissante et efficace pour trouver les chemins les plus courts dans des graphiques avec des poids non négatifs. Bien qu'il présente des limites (par exemple, il ne peut pas gérer les poids de bord négatifs), il est largement utilisé dans les applications de mise en réseau, de routage et autres.
- La relaxation garantit les distances les plus courtes en mettant à jour les chemins de manière itérative.
- File d'attente prioritaire garantit que nous traitons toujours le nœud le plus proche, en maintenant l'exactitude.
- L'exactitude est prouvée par induction : une fois la distance d'un nœud finalisée, il est garanti qu'il s'agit du chemin le plus court.
Voici quelques ressources détaillées où vous pouvez explorer l'algorithme de Dijkstra ainsi que des preuves et des exemples rigoureux :
- Algorithme de Dijkstra PDF
- Algorithmes du chemin le plus court sur SlideShare
De plus, Wikipédia offre un excellent aperçu du sujet.
Citations :
[1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf
N'hésitez pas à partager vos réflexions ou améliorations dans les commentaires !
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds











Python convient plus aux débutants, avec une courbe d'apprentissage en douceur et une syntaxe concise; JavaScript convient au développement frontal, avec une courbe d'apprentissage abrupte et une syntaxe flexible. 1. La syntaxe Python est intuitive et adaptée à la science des données et au développement back-end. 2. JavaScript est flexible et largement utilisé dans la programmation frontale et côté serveur.

Le passage de C / C à JavaScript nécessite de s'adapter à la frappe dynamique, à la collecte des ordures et à la programmation asynchrone. 1) C / C est un langage dactylographié statiquement qui nécessite une gestion manuelle de la mémoire, tandis que JavaScript est dynamiquement typé et que la collecte des déchets est automatiquement traitée. 2) C / C doit être compilé en code machine, tandis que JavaScript est une langue interprétée. 3) JavaScript introduit des concepts tels que les fermetures, les chaînes de prototypes et la promesse, ce qui améliore la flexibilité et les capacités de programmation asynchrones.

Les principales utilisations de JavaScript dans le développement Web incluent l'interaction client, la vérification du formulaire et la communication asynchrone. 1) Mise à jour du contenu dynamique et interaction utilisateur via les opérations DOM; 2) La vérification du client est effectuée avant que l'utilisateur ne soumette les données pour améliorer l'expérience utilisateur; 3) La communication de rafraîchissement avec le serveur est réalisée via la technologie AJAX.

L'application de JavaScript dans le monde réel comprend un développement frontal et back-end. 1) Afficher les applications frontales en créant une application de liste TODO, impliquant les opérations DOM et le traitement des événements. 2) Construisez RestulAPI via Node.js et Express pour démontrer les applications back-end.

Comprendre le fonctionnement du moteur JavaScript en interne est important pour les développeurs car il aide à écrire du code plus efficace et à comprendre les goulots d'étranglement des performances et les stratégies d'optimisation. 1) Le flux de travail du moteur comprend trois étapes: analyse, compilation et exécution; 2) Pendant le processus d'exécution, le moteur effectuera une optimisation dynamique, comme le cache en ligne et les classes cachées; 3) Les meilleures pratiques comprennent l'évitement des variables globales, l'optimisation des boucles, l'utilisation de const et de locations et d'éviter une utilisation excessive des fermetures.

Python et JavaScript ont leurs propres avantages et inconvénients en termes de communauté, de bibliothèques et de ressources. 1) La communauté Python est amicale et adaptée aux débutants, mais les ressources de développement frontal ne sont pas aussi riches que JavaScript. 2) Python est puissant dans les bibliothèques de science des données et d'apprentissage automatique, tandis que JavaScript est meilleur dans les bibliothèques et les cadres de développement frontaux. 3) Les deux ont des ressources d'apprentissage riches, mais Python convient pour commencer par des documents officiels, tandis que JavaScript est meilleur avec MDNWEBDOCS. Le choix doit être basé sur les besoins du projet et les intérêts personnels.

Les choix de Python et JavaScript dans les environnements de développement sont importants. 1) L'environnement de développement de Python comprend Pycharm, Jupyternotebook et Anaconda, qui conviennent à la science des données et au prototypage rapide. 2) L'environnement de développement de JavaScript comprend Node.js, VScode et WebPack, qui conviennent au développement frontal et back-end. Le choix des bons outils en fonction des besoins du projet peut améliorer l'efficacité du développement et le taux de réussite du projet.

C et C jouent un rôle essentiel dans le moteur JavaScript, principalement utilisé pour implémenter des interprètes et des compilateurs JIT. 1) C est utilisé pour analyser le code source JavaScript et générer une arborescence de syntaxe abstraite. 2) C est responsable de la génération et de l'exécution de bytecode. 3) C met en œuvre le compilateur JIT, optimise et compile le code de point chaud à l'exécution et améliore considérablement l'efficacité d'exécution de JavaScript.
