suchen
HeimWeb-Frontendjs-TutorialDen Dijkstra-Algorithmus verstehen: Von der Theorie zur Umsetzung

Understanding Dijkstra

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) G=(V,E) , Wo VV V ist die Menge der Eckpunkte, EE E ist die Menge der Kanten und ein Quellknoten sVs in V s∈V .
  • Ausgabe: Die kürzesten Pfadentfernungen von ss s an alle anderen Knoten in VV 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:

    dist(s )=0,dist(v)=  vs text{dist}(s) = 0, text{dist}(v) = infty ; quad forall v neq 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: dist(s)=0,dist(v )=für alle vstext{dist}(s) = 0, text{dist}(v) = infty , text{for all} , v neq s dist(s)=0,dist(v)=für a llv=s

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

  • Entspannungsschritt: für jede Kante (u,v) (u, v) (u,v) mit Gewicht w(u,v )w(u, v) w(u,v) : Wenn dist(v)>dist(u) w(u,v)Text{ dist}(v) > text{dist}(u) w(u, v) dist(v)>dist (u) w(u,v) , aktualisieren:
    dist(v) =dist(u) w(u,v),prev(v)=utext{dist}(v ) = text{dist}(u) w(u, v), quad 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 ) (u) mit dem kleinsten vorläufigen Abstand:
      u=argmin vQdist( v)u = arg min_{v in Q} text{dist}(v) u=argv∈Q mindist(v)
    • Warum es funktioniert: Durch die Verarbeitung des Knotens mit dem kleinsten (dist(v) )( text{dist}(v) ) (dist(v)) Wir garantieren den kürzesten Weg von der Quelle zur (u)( 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) ) (P(n)) , wir gehen von der Wahrheit aus (P( 1),P(2),,P(k))( P(1), P(2), Punkte, P(k) ) (P(1),P(2),…,P(k)) zu beweisen (P(k 1))( P(k 1) ) ( P(k 1)) . Dies unterscheidet sich von der regulären Induktion, bei der nur angenommen wird (P(k) )( P(k) ) (P(k)) zu beweisen (P(k 1))( P(k 1) ) ( P(k 1)) . Erfahren Sie mehr darüber in meinem anderen Beitrag.

Korrektheit des Dijkstra-Algorithmus (induktiver Beweis)

  1. Basisfall:

    Der Quellknoten (s)( s) (s) wird mit initialisiert dist(s)= 0text{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 ) (u) wird aus der Prioritätswarteschlange entfernt. Seit dist(u)text{dist} (u) dist(u) ist der kleinste verbleibende Abstand und alle vorherigen Knoten haben korrekte Abstände, dist(u)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 


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 ,DA, B, C, D A,B,C,D
  • Kanten:
    • AB=( 1),AC=(4)A zu B = (1), A zu C = (4) A→B=(1),A →C=(4)
    • BC=( 2),BD=(5)B zu C = (2), B zu D = (5) B→C=(2),B →D=(5)
    • CD=( 1)C bis D = (1) C→D=(1)

Schritt-für-Schritt-Ausführung

  1. Distanzen initialisieren:

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

    • Kanten entspannen: AB,AC.A nach B, A nach C. A→B,A→C.
      dist(B)= 1,  dist(C)=4 text{dist}(B) = 1, ; text{dist}(C) = 4 Abstand(B)=1,Abstand(C)=4
  3. Prozess B:

    • Kanten entspannen: BC,BD.B nach C, B nach D. B→C,B→D.
      dist(C)= 3,  dist(D)=6 text{dist}(C) = 3, ; text{dist}(D) = 6 dist(C)=3,dist(D)=6
  4. Prozess C:

    • Entspannungskante: CD.C bis D. C→D.
      dist(D)= 4text{dist}(D) = 4 dist(D)=4
  5. Prozess D:

    • Keine weiteren Updates.

Endgültige Entfernungen und Pfad

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

ABC D A nach B nach C nach D A→B→C→D

Optimierungen und Zeitkomplexität

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

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)

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!

Stellungnahme
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Ersetzen Sie Stringzeichen in JavaScriptErsetzen Sie Stringzeichen in JavaScriptMar 11, 2025 am 12:07 AM

Detaillierte Erläuterung der Methode für JavaScript -Zeichenfolge und FAQ In diesem Artikel werden zwei Möglichkeiten untersucht, wie String -Zeichen in JavaScript ersetzt werden: Interner JavaScript -Code und interne HTML für Webseiten. Ersetzen Sie die Zeichenfolge im JavaScript -Code Die direkteste Möglichkeit ist die Verwendung der Ersatz () -Methode: str = str.replace ("find", "ersetzen"); Diese Methode ersetzt nur die erste Übereinstimmung. Um alle Übereinstimmungen zu ersetzen, verwenden Sie einen regulären Ausdruck und fügen Sie das globale Flag G hinzu:: STR = Str.Replace (/fi

Erstellen Sie Ihre eigenen AJAX -WebanwendungenErstellen Sie Ihre eigenen AJAX -WebanwendungenMar 09, 2025 am 12:11 AM

Hier sind Sie also bereit, alles über dieses Ding namens Ajax zu lernen. Aber was genau ist das? Der Begriff AJAX bezieht sich auf eine lose Gruppierung von Technologien, mit denen dynamische, interaktive Webinhalte erstellt werden. Der Begriff Ajax, ursprünglich von Jesse J geprägt

Wie erstelle ich meine eigenen JavaScript -Bibliotheken?Wie erstelle ich meine eigenen JavaScript -Bibliotheken?Mar 18, 2025 pm 03:12 PM

In Artikel werden JavaScript -Bibliotheken erstellt, veröffentlicht und aufrechterhalten und konzentriert sich auf Planung, Entwicklung, Testen, Dokumentation und Werbestrategien.

Wie optimiere ich den JavaScript -Code für die Leistung im Browser?Wie optimiere ich den JavaScript -Code für die Leistung im Browser?Mar 18, 2025 pm 03:14 PM

In dem Artikel werden Strategien zur Optimierung der JavaScript -Leistung in Browsern erörtert, wobei der Schwerpunkt auf die Reduzierung der Ausführungszeit und die Minimierung der Auswirkungen auf die Lastgeschwindigkeit der Seite wird.

Wie debugge ich den JavaScript -Code effektiv mithilfe von Browser -Entwickler -Tools?Wie debugge ich den JavaScript -Code effektiv mithilfe von Browser -Entwickler -Tools?Mar 18, 2025 pm 03:16 PM

In dem Artikel werden effektives JavaScript -Debuggen mithilfe von Browser -Entwickler -Tools, der Schwerpunkt auf dem Festlegen von Haltepunkten, der Konsole und der Analyse der Leistung erörtert.

JQuery MatrixeffekteJQuery MatrixeffekteMar 10, 2025 am 12:52 AM

Bringen Sie Matrix -Filmeffekte auf Ihre Seite! Dies ist ein cooles JQuery -Plugin, das auf dem berühmten Film "The Matrix" basiert. Das Plugin simuliert die klassischen grünen Charakter-Effekte im Film und wählen Sie einfach ein Bild aus, und das Plugin verwandelt es in ein mit numerischer Zeichen gefüllte Bild im Matrix-Stil. Komm und probiere es aus, es ist sehr interessant! Wie es funktioniert Das Plugin lädt das Bild auf die Leinwand und liest die Pixel- und Farbwerte: Data = ctx.getImagedata (x, y, setting.grainize, setting.grainesize) .data Das Plugin liest geschickt den rechteckigen Bereich des Bildes und berechnet JQuery, um die durchschnittliche Farbe jedes Bereichs zu berechnen. Dann verwenden Sie

So bauen Sie einen einfachen JQuery SliderSo bauen Sie einen einfachen JQuery SliderMar 11, 2025 am 12:19 AM

In diesem Artikel werden Sie mit der JQuery -Bibliothek ein einfaches Bildkarousel erstellen. Wir werden die BXSLIDER -Bibliothek verwenden, die auf JQuery basiert und viele Konfigurationsoptionen zum Einrichten des Karussells bietet. Heutzutage ist Picture Carousel zu einem Muss auf der Website geworden - ein Bild ist besser als tausend Wörter! Nachdem Sie sich entschieden haben, das Bild -Karussell zu verwenden, ist die nächste Frage, wie Sie es erstellen. Zunächst müssen Sie hochwertige, hochauflösende Bilder sammeln. Als nächstes müssen Sie ein Bildkarousel mit HTML und einem JavaScript -Code erstellen. Es gibt viele Bibliotheken im Web, die Ihnen helfen können, Karussell auf unterschiedliche Weise zu erstellen. Wir werden die Open -Source -BXSLIDER -Bibliothek verwenden. Die BXSLIDER -Bibliothek unterstützt reaktionsschnelles Design, sodass das mit dieser Bibliothek gebaute Karussell an alle angepasst werden kann

So laden und herunterladen Sie CSV -Dateien mit Angular hoch und laden Sie sie herunterSo laden und herunterladen Sie CSV -Dateien mit Angular hoch und laden Sie sie herunterMar 10, 2025 am 01:01 AM

Datensätze sind äußerst wichtig für den Aufbau von API -Modellen und verschiedenen Geschäftsprozessen. Aus diesem Grund ist das Import und Exportieren von CSV eine häufig benötigte Funktionalität. In diesem Tutorial lernen Sie, wie Sie eine CSV-Datei in einem Angular herunterladen und importieren.

See all articles

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heiße Werkzeuge

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

MinGW – Minimalistisches GNU für Windows

MinGW – Minimalistisches GNU für Windows

Dieses Projekt wird derzeit auf osdn.net/projects/mingw migriert. Sie können uns dort weiterhin folgen. MinGW: Eine native Windows-Portierung der GNU Compiler Collection (GCC), frei verteilbare Importbibliotheken und Header-Dateien zum Erstellen nativer Windows-Anwendungen, einschließlich Erweiterungen der MSVC-Laufzeit zur Unterstützung der C99-Funktionalität. Die gesamte MinGW-Software kann auf 64-Bit-Windows-Plattformen ausgeführt werden.

Herunterladen der Mac-Version des Atom-Editors

Herunterladen der Mac-Version des Atom-Editors

Der beliebteste Open-Source-Editor

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

mPDF

mPDF

mPDF ist eine PHP-Bibliothek, die PDF-Dateien aus UTF-8-codiertem HTML generieren kann. Der ursprüngliche Autor, Ian Back, hat mPDF geschrieben, um PDF-Dateien „on the fly“ von seiner Website auszugeben und verschiedene Sprachen zu verarbeiten. Es ist langsamer und erzeugt bei der Verwendung von Unicode-Schriftarten größere Dateien als Originalskripte wie HTML2FPDF, unterstützt aber CSS-Stile usw. und verfügt über viele Verbesserungen. Unterstützt fast alle Sprachen, einschließlich RTL (Arabisch und Hebräisch) und CJK (Chinesisch, Japanisch und Koreanisch). Unterstützt verschachtelte Elemente auf Blockebene (wie P, DIV),