Den Dijkstra-Algorithmus verstehen: Von der Theorie zur Umsetzung

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 }\mathrm{\forall }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{für alle}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{dist}(B)=\mathrm{\infty },\text{dist}(C)=\mathrm{\infty },\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{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{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!