Der Dijkstra-Algorithmus ist ein klassischer Pfadfindungsalgorithmus, der in der Graphentheorie verwendet wird, um den kürzesten Pfad von einem Quellknoten zu allen anderen Knoten in einem Diagramm zu finden. In diesem Artikel untersuchen wir den Algorithmus, seinen Korrektheitsnachweis und stellen eine Implementierung in JavaScript bereit.

Was ist Dijkstras Algorithmus?

Dijkstras Algorithmus ist ein Greedy-Algorithmus, der darauf ausgelegt ist, die kürzesten Pfade von einem einzelnen Quellknoten in einem gewichteten Diagramm mit nicht negativen Kantengewichten zu finden. Er wurde 1956 von Edsger W. Dijkstra vorgeschlagen und ist nach wie vor einer der am weitesten verbreiteten Algorithmen in der Informatik.

Eingabe und Ausgabe

• Eingabe: Ein Diagramm $G=(V,E)$G=(V,E) , Wo $V$V ist die Menge der Eckpunkte, $E$E ist die Menge der Kanten und ein Quellknoten $s\in V$s∈V .
• Ausgabe: Die kürzesten Pfadentfernungen von $s$s an alle anderen Knoten in $V$V .

Kernkonzepte

1. Entspannung: Der Prozess der Aktualisierung der kürzesten bekannten Entfernung zu einem Knoten.
2. Priorit?tswarteschlange: Ruft effizient den Knoten mit der kleinsten vorl?ufigen Entfernung ab.
3. Gieriger Ansatz: Verarbeitet Knoten in nicht abnehmender Reihenfolge ihrer kürzesten Entfernungen.

Der Algorithmus

1. Distanzen initialisieren:
   

   $$\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\text{??}\mathrm{?}v\mathrm{\ne }s$$dist(s)=0,dist(v)=∞?v=s

2. Verwenden Sie eine Priorit?tswarteschlange, um Knoten basierend auf ihrer Entfernung zu speichern.

3. Entfernen Sie wiederholt den Knoten mit dem kleinsten Abstand und entspannen Sie seine Nachbarn.

Entspannung – Mathematische Erkl?rung

• Initialisierung: $\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\text{?}\text{für?alle}\text{?}v\mathrm{\ne }s$dist(s)=0,dist(v)=∞für?a llv=s

wo $(s)$(s) ist der Quellknoten und $(v)$(v) repr?sentiert jeden anderen Knoten.

• Entspannungsschritt: für jede Kante $(u,v)$(u,v) mit Gewicht $w(u,v)$w(u,v) : Wenn $\text{dist}(v)>\text{dist}(u)w(u,v)$dist(v)>dist (u) w(u,v) , aktualisieren:
  $$\text{dist}(v)=\text{dist}(u)w(u,v),\text{prev}(v)=u$$dist(v)=dist(u) w(u,v),prev(v)=u

Warum es funktioniert: Durch die Entspannung wird sichergestellt, dass wir immer den kürzesten Weg zu einem Knoten finden, indem die Entfernung schrittweise aktualisiert wird, wenn ein kürzerer Weg gefunden wird.

Priorit?tswarteschlange – Mathematische Erkl?rung

• Warteschlangenbetrieb:

  • Die Priorit?tswarteschlange entfernt den Knoten immer aus der Warteschlange $(u)$(u) mit dem kleinsten vorl?ufigen Abstand:
    $$u=\arg ?\underset{v\in Q}{\min ?}\text{dist}(v)$$u=argv∈Q min?dist(v)
  • Warum es funktioniert: Durch die Verarbeitung des Knotens mit dem kleinsten $(\text{dist}(v))$(dist(v)) Wir garantieren den kürzesten Weg von der Quelle zur $(u)$(u) .

Beweis der Korrektheit

Wir beweisen die Korrektheit des Dijkstra-Algorithmus mithilfe von starker Induktion.

Was ist starke Induktion?

Starke Induktion ist eine Variante der mathematischen Induktion, bei der es darum geht, eine Aussage zu beweisen $(P(n))$(P(n)) , wir gehen von der Wahrheit aus $(P(1),P(2),\dots ,P(k))$(P(1),P(2),…,P(k)) zu beweisen $(P(k1))$( P(k 1)) . Dies unterscheidet sich von der regul?ren Induktion, bei der nur angenommen wird $(P(k))$(P(k)) zu beweisen $(P(k1))$( P(k 1)) . Erfahren Sie mehr darüber in meinem anderen Beitrag.

Korrektheit des Dijkstra-Algorithmus (induktiver Beweis)

1. Basisfall:
   
   Der Quellknoten $(s)$(s) wird mit initialisiert $\text{dist}(s)=0$dist(s)=0 , was richtig ist.

2. Induktive Hypothese:
   
   Gehen Sie davon aus, dass alle bisher verarbeiteten Knoten die richtigen kürzesten Pfadabst?nde haben.

3. Induktiver Schritt:
   
   Der n?chste Knoten $(u)$(u) wird aus der Priorit?tswarteschlange entfernt. Seit $\text{dist}(u)$dist(u) ist der kleinste verbleibende Abstand und alle vorherigen Knoten haben korrekte Abst?nde, $\text{dist}(u)$dist(u) ist auch richtig.

JavaScript-Implementierung

Voraussetzungen (Priorit?tswarteschlange):

// 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;
  }
}

Hier ist eine JavaScript-Implementierung des Dijkstra-Algorithmus unter Verwendung einer Priorit?tswarteschlange:

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);

Pfad rekonstruieren

// 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;
  }
}

Beispiel-Komplettl?sung

Diagrammdarstellung

• Knoten: $A,B,C,D$A,B,C,D
• Kanten:
  • $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)

Schritt-für-Schritt-Ausführung

1. Distanzen initialisieren:
   

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

2. Prozess A:

   • Kanten entspannen: $A\to B,A\to C\mathrm{.}$A→B,A→C.
     $$\text{dist}(B)=1,\text{??}\text{dist}(C)=4$$Abstand(B)=1,Abstand(C)=4

3. Prozess B:

   • Kanten entspannen: $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. Prozess C:

   • Entspannungskante: $C\to D\mathrm{.}$C→D.
     $$\text{dist}(D)=4$$dist(D)=4

5. Prozess D:

   • Keine weiteren Updates.

Endgültige Entfernungen und Pfad

Optimierungen und Zeitkomplexit?t

Vergleich der zeitlichen Komplexit?t des Dijkstra-Algorithmus mit verschiedenen Implementierungen von Priorit?tswarteschlangen:

Kernpunkte:

1. Einfaches Array:
   • Ineffizient für gro?e Diagramme aufgrund der linearen Suche nach Extraktmin.
2. Bin?rer Heap:
   • Standard und h?ufig verwendet aufgrund seines Gleichgewichts zwischen Einfachheit und Effizienz.
3. Binomialhaufen:
   • Etwas bessere theoretische Garantien, aber komplexer in der Umsetzung.
4. Fibonacci-Haufen:
   • Beste theoretische Leistung mit ( O(1) ) amortisierter Verkleinerungstaste, aber schwieriger zu implementieren.
5. Pairing Heap:
   • Einfach und funktioniert in der Praxis ?hnlich wie der Fibonacci-Heap.

Abschluss

Der Dijkstra-Algorithmus ist eine leistungsstarke und effiziente Methode zum Finden kürzester Pfade in Diagrammen mit nicht negativen Gewichten. Obwohl es Einschr?nkungen gibt (z. B. kann es keine negativen Kantengewichte verarbeiten), wird es h?ufig in Netzwerken, Routing und anderen Anwendungen verwendet.

• Entspannung sorgt für kürzeste Distanzen durch iterative Aktualisierung von Pfaden.
• Priorit?tswarteschlange garantiert, dass wir immer den n?chstgelegenen Knoten verarbeiten und die Korrektheit wahren.
• Korrektheit wird durch Induktion bewiesen: Sobald die Entfernung eines Knotens endgültig festgelegt ist, handelt es sich garantiert um den kürzesten Weg.

Hier finden Sie einige detaillierte Ressourcen, in denen Sie den Dijkstra-Algorithmus zusammen mit strengen Beweisen und Beispielen erkunden k?nnen:

• Dijkstras Algorithmus PDF
• Kürzeste-Pfad-Algorithmen auf SlideShare

Au?erdem bietet Wikipedia einen tollen überblick zum Thema.

Zitate:
[1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf

Teilen Sie Ihre Gedanken oder Verbesserungen gerne in den Kommentaren mit!

Das obige ist der detaillierte Inhalt vonDen Dijkstra-Algorithmus verstehen: Von der Theorie zur Umsetzung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!