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

   $$\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\mathrm{\forall }v\mathrm{\ne }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 : $\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\text{pour tous}v\mathrm{\ne }s$dist(s)=0,dist(v)=∞pour un llv=s

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

• Étape de relaxation : pour chaque bord $(u,v)$(u,v) avec du poids $w(u,v)$w(u,v) : Si $\text{dist}(v)>\text{dist}(u)w(u,v)$dist(v)>dist (tu) w(u,v) , mise à jour:
  $$\text{dist}(v)=\text{dist}(u)w(u,v),\text{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) avec la plus petite distance provisoire :
    $$u=\arg \underset{v\in Q}{\min }\text{dist}(v)$$u=argv∈Q min​dist(v)
  • Pourquoi ça marche : En traitant le nœud avec le plus petit $(\text{dist}(v))$(dist(v)) , nous garantissons le chemin le plus court de la source à $(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)) , nous supposons la vérité de $(P(1),P(2),\dots ,P(k))$(P(1),P(2),…,P(k)) prouver $(P(k1))$( P(k 1)) . Cela diffère de l'induction régulière, qui suppose uniquement $(P(k))$(P(k)) prouver $(P(k1))$( 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) est initialisé avec $\text{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) est retiré de la file d'attente prioritaire. Depuis $\text{dist}(u)$dist(u) est la plus petite distance restante, et tous les nœuds précédents ont des distances correctes, $\text{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;
  }
}

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$A,B,C,D
• Bords :
  • $A\to B=(1),A\to C=(4)$A→B=(1),A →C=(4)
  • $B\to C=(2),B\to D=(5)$B→C=(2),B →D=(5)
  • $C\to D=(1)$C→D=(1)

Exécution étape par étape

1. Initialiser les distances :
   

   $$\text{dist}(A)=0,\text{dist}(B)=\mathrm{\infty },\text{dist}(C)=\mathrm{\infty },\text{dist}(D)=\mathrm{\infty }$$dist(A)=0,dist(B)= ∞,dist(C)=∞,dist(D)=∞

2. Processus A :

   • Détendez les bords : $A\to B,A\to C\mathrm{.}$A→B,A→C.
     $$\text{dist}(B)=1,\text{dist}(C)=4$$dist(B)=1,dist(C)=4

3. Processus B :

   • Détendez les bords : $B\to C,B\to D\mathrm{.}$B→C,B→D.
     $$\text{dist}(C)=3,\text{dist}(D)=6$$dist(C)=3,dist(D)=6

4. Processus C :

   • Bord détente : $C\to D\mathrm{.}$C→D.
     $$\text{dist}(D)=4$$dist(D)=4

5. Processus D :

   • Aucune autre mise à jour.

Distances finales et chemin

$$\text{dist}(A)=0,\text{dist}(B)=1,\text{dist}(C)=3,\text{dist}(D)=4$$dist(A)=0,dist(B)= 1,dist(C)=3,dist(D)=4

$$A\to B\to C\to 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!