Maison interface Web js tutoriel Comprendre l'algorithme de Dijkstra : de la théorie à la mise en œuvre

Comprendre l'algorithme de Dijkstra : de la théorie à la mise en œuvre

Dec 14, 2024 am 03:18 AM

Understanding Dijkstra

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)G = (V, E) G=(V,E) , où VV V est l'ensemble des sommets, EE E est l'ensemble des arêtes et un nœud source sVs en V s∈V .
  • Sortie : Les distances de chemin les plus courtes depuis ss s à tous les autres nœuds de VV V .

Concepts de base

  1. Relaxation : Le processus de mise à jour de la distance connue la plus courte jusqu'à un nœud.
  2. File d'attente prioritaire : Récupère efficacement le nœud avec la plus petite distance provisoire.
  3. Approche gourmande : Traite les nœuds par ordre non décroissant de leurs distances les plus courtes.

L'algorithme

  1. Initialiser les distances :

    dist(s )=0,dist(v)=  vs texte{dist}(s) = 0, texte{dist}(v) = infty ; quad pour tous v neq s dist(s)=0,dist(v)=∞∀v=s
  2. Utilisez une file d'attente prioritaire pour stocker les nœuds en fonction de leurs distances.

  3. 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 tous vstexte{dist}(s) = 0, texte{dist}(v) = infty, texte{pour tous}, v neq s dist(s)=0,dist(v)=pour un llv=s

(s)( s ) (s) est le nœud source, et (v)( v) (v) représente n'importe quel autre nœud.

  • Étape de relaxation : pour chaque bord (u,v) (u, v) (u,v) avec du poids w(u,v )w(u, v) w(u,v) : Si dist(v)>dist(u) w(u,v)texte{ dist}(v) > texte{dist}(u) w(u, v) dist(v)>dist (tu) w(u,v) , mise à jour:
    dist(v) =dist(u) w(u,v),prev(v)=utext{dist}(v ) = texte{dist}(u) w(u, v), quad texte{prev}(v) = u 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)(u) (u) avec la plus petite distance provisoire :
      u=argmin vQdist( v)u = arg min_{v dans Q} texte{dist}(v) u=argv∈Q mindist(v)
    • Pourquoi ça marche : En traitant le nœud avec le plus petit (dist(v) )( texte{dist}(v) ) (dist(v)) , nous garantissons le chemin le plus court de la source à (u)(u) (u) .

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) )( P(n) ) (P(n)) , nous supposons la vérité de (P( 1),P(2),,P(k))( P(1), P(2), points, P(k) ) (P(1),P(2),…,P(k)) prouver (P(k 1))( P(k 1) ) ( P(k 1)) . Cela diffère de l'induction régulière, qui suppose uniquement (P(k) )( P(k) ) (P(k)) prouver (P(k 1))( P(k 1) ) ( P(k 1)) . Explorez-le plus en détail dans mon autre article.

Exactitude de l'algorithme de Dijkstra (preuve inductive)

  1. Cas de base :

    Le nœud source (s)( s ) (s) est initialisé avec dist(s)= 0texte{dist}(s) = 0 dist(s)=0 , ce qui est exact.

  2. Hypothèse inductive :

    Supposons que tous les nœuds traités jusqu'à présent ont les distances de chemin les plus courtes correctes.

  3. Étape inductive :

    Le prochain nœud (u)(u) (u) est retiré de la file d'attente prioritaire. Depuis dist(u)texte{dist} (u) dist(u) est la plus petite distance restante, et tous les nœuds précédents ont des distances correctes, dist(u)texte{dist} (u) 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;
  }
}
Copier après la connexion
Copier après la connexion

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);
Copier après la connexion

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;
  }
}
Copier après la connexion
Copier après la connexion

Exemple de procédure pas à pas

Représentation graphique

  • Nœuds : A,B,C ,DA, B, C, D A,B,C,D
  • Bords :
    • AB=( 1),AC=(4)A à B = (1), A à C = (4) A→B=(1),A →C=(4)
    • BC=( 2),BD=(5)B à C = (2), B à D = (5) B→C=(2),B →D=(5)
    • CD=( 1)C à D = (1) C→D=(1)

Exécution étape par étape

  1. Initialiser les distances :

    dist(A)= 0 ,  dist(B)=,  dist(C)=,  dist(D)= texte{dist}(A) = 0, ; text{dist}(B) = infty, ; text{dist}(C) = infty, ; text{dist}(D) = infty dist(A)=0,dist(B)= ∞,dist(C)=∞,dist(D)=
  2. Processus A :

    • Détendez les bords : AB,AC.A à B, A à C. A→B,A→C.
      dist(B)= 1,  dist(C)=4 texte{dist}(B) = 1, ; texte{dist}(C) = 4 dist(B)=1,dist(C)=4
  3. Processus B :

    • Détendez les bords : BC,BD.B à C, B à D. B→C,B→D.
      dist(C)= 3,  dist(D)=6 texte{dist}(C) = 3, ; texte{dist}(D) = 6 dist(C)=3,dist(D)=6
  4. Processus C :

    • Bord détente : CD.C à D. C→D.
      dist(D)= 4texte{dist}(D) = 4 dist(D)=4
  5. Processus D :

    • Aucune autre mise à jour.

Distances finales et chemin

dist(A)= 0 ,  dist(B)=1,  dist(C)= 3,  dist(D)=4 texte{dist}(A) = 0, ; texte{dist}(B) = 1, ; texte{dist}(C) = 3, ; texte{dist}(D) = 4 dist(A)=0,dist(B)= 1,dist(C)=3,dist(D)=4

ABC D A à B à C à D A→B→C→D

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 :

  1. Tableau simple :
    • Inefficace pour les grands graphiques en raison de la recherche linéaire de l'extrait-min.
  2. Tas binaire :
    • Standard et couramment utilisé en raison de son équilibre entre simplicité et efficacité.
  3. Tas binomial :
    • Des garanties théoriques un peu meilleures mais plus complexes à mettre en œuvre.
  4. Tas de Fibonacci :
    • Meilleures performances théoriques avec ( O(1) ) touche de diminution amortie, mais plus difficile à mettre en œuvre.
  5. 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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

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 !

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

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

Que dois-je faire si je rencontre l'impression de code brouillé pour les reçus en papier thermique frontal? Que dois-je faire si je rencontre l'impression de code brouillé pour les reçus en papier thermique frontal? Apr 04, 2025 pm 02:42 PM

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 ...

Démystifier javascript: ce qu'il fait et pourquoi c'est important Démystifier javascript: ce qu'il fait et pourquoi c'est important Apr 09, 2025 am 12:07 AM

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.

Qui est payé plus de python ou de javascript? Qui est payé plus de python ou de javascript? Apr 04, 2025 am 12:09 AM

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.

Comment réaliser des effets de défilement de parallaxe et d'animation des éléments, comme le site officiel de Shiseido?
ou:
Comment pouvons-nous réaliser l'effet d'animation accompagné d'un défilement de page comme le site officiel de Shiseido? Comment réaliser des effets de défilement de parallaxe et d'animation des éléments, comme le site officiel de Shiseido? ou: Comment pouvons-nous réaliser l'effet d'animation accompagné d'un défilement de page comme le site officiel de Shiseido? Apr 04, 2025 pm 05:36 PM

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/) ...

JavaScript est-il difficile à apprendre? JavaScript est-il difficile à apprendre? Apr 03, 2025 am 12:20 AM

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.

L'évolution de JavaScript: tendances actuelles et perspectives d'avenir L'évolution de JavaScript: tendances actuelles et perspectives d'avenir Apr 10, 2025 am 09:33 AM

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 utilisant JavaScript? Comment fusionner les éléments du tableau avec le même ID dans un seul objet en utilisant JavaScript? Apr 04, 2025 pm 05:09 PM

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 ...

Comment implémenter la fonction de glisser-déposer et de régler la fonction de réglage similaire à VScode dans le développement frontal? Comment implémenter la fonction de glisser-déposer et de régler la fonction de réglage similaire à VScode dans le développement frontal? Apr 04, 2025 pm 02:06 PM

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 ...

See all articles