


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

Des questions et des solutions fréquemment posées pour l'impression de billets thermiques frontaux pour le développement frontal, l'impression de billets est une exigence commune. Cependant, de nombreux développeurs mettent en œuvre ...

JavaScript est la pierre angulaire du développement Web moderne, et ses principales fonctions incluent la programmation axée sur les événements, la génération de contenu dynamique et la programmation asynchrone. 1) La programmation axée sur les événements permet aux pages Web de changer dynamiquement en fonction des opérations utilisateur. 2) La génération de contenu dynamique permet d'ajuster le contenu de la page en fonction des conditions. 3) La programmation asynchrone garantit que l'interface utilisateur n'est pas bloquée. JavaScript est largement utilisé dans l'interaction Web, les applications à une page et le développement côté serveur, améliorant considérablement la flexibilité de l'expérience utilisateur et du développement multiplateforme.

Il n'y a pas de salaire absolu pour les développeurs Python et JavaScript, selon les compétences et les besoins de l'industrie. 1. Python peut être davantage payé en science des données et en apprentissage automatique. 2. JavaScript a une grande demande dans le développement frontal et complet, et son salaire est également considérable. 3. Les facteurs d'influence comprennent l'expérience, la localisation géographique, la taille de l'entreprise et les compétences spécifiques.

La discussion sur la réalisation des effets de défilement de parallaxe et d'animation des éléments dans cet article explorera comment réaliser le site officiel de Shiseido (https://www.shiseido.co.jp/sb/wonderland/) ...

Apprendre JavaScript n'est pas difficile, mais c'est difficile. 1) Comprendre les concepts de base tels que les variables, les types de données, les fonctions, etc. 2) Master la programmation asynchrone et les implémenter via des boucles d'événements. 3) Utilisez les opérations DOM et promettez de gérer les demandes asynchrones. 4) Évitez les erreurs courantes et utilisez des techniques de débogage. 5) Optimiser les performances et suivre les meilleures pratiques.

Les dernières tendances de JavaScript incluent la montée en puissance de TypeScript, la popularité des frameworks et bibliothèques modernes et l'application de WebAssembly. Les prospects futurs couvrent des systèmes de type plus puissants, le développement du JavaScript côté serveur, l'expansion de l'intelligence artificielle et de l'apprentissage automatique, et le potentiel de l'informatique IoT et Edge.

Comment fusionner les éléments du tableau avec le même ID dans un seul objet en JavaScript? Lors du traitement des données, nous rencontrons souvent la nécessité d'avoir le même ID ...

Explorez la mise en œuvre de la fonction de glisser et de réglage du panneau de type VScode dans le frontal. Dans le développement frontal, comment implémenter un VScode comme ...
