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 }\text{??}\mathrm{?}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{?}\text{pour?tous}\text{?}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{??}\text{dist}(B)=\mathrm{\infty },\text{??}\text{dist}(C)=\mathrm{\infty },\text{??}\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{??}\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{??}\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

Optimisations et complexité temporelle

Comparaison des complexités temporelles de l'algorithme de Dijkstra avec différentes implémentations de files d'attente prioritaires?:

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!