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
Node.js Streams mit TypeScriptNode.js Streams mit TypeScriptApr 30, 2025 am 08:22 AM

Node.js zeichnet sich bei effizienten E/A aus, vor allem bei Streams. Streams verarbeiten Daten inkrementell und vermeiden Speicherüberladung-ideal für große Dateien, Netzwerkaufgaben und Echtzeitanwendungen. Die Kombination von Streams mit der TypeScript -Sicherheit erzeugt eine POWE

Python vs. JavaScript: Leistung und EffizienzüberlegungenPython vs. JavaScript: Leistung und EffizienzüberlegungenApr 30, 2025 am 12:08 AM

Die Unterschiede in der Leistung und der Effizienz zwischen Python und JavaScript spiegeln sich hauptsächlich in: 1 wider: 1) Als interpretierter Sprache läuft Python langsam, weist jedoch eine hohe Entwicklungseffizienz auf und ist für eine schnelle Prototypentwicklung geeignet. 2) JavaScript ist auf einen einzelnen Thread im Browser beschränkt, aber Multi-Threading- und Asynchronen-E/A können verwendet werden, um die Leistung in Node.js zu verbessern, und beide haben Vorteile in tatsächlichen Projekten.

Die Ursprünge von JavaScript: Erforschung seiner ImplementierungsspracheDie Ursprünge von JavaScript: Erforschung seiner ImplementierungsspracheApr 29, 2025 am 12:51 AM

JavaScript stammt aus dem Jahr 1995 und wurde von Brandon Ike erstellt und realisierte die Sprache in C. 1.C-Sprache bietet Programmierfunktionen auf hoher Leistung und Systemebene für JavaScript. 2. Die Speicherverwaltung und die Leistungsoptimierung von JavaScript basieren auf C -Sprache. 3. Die plattformübergreifende Funktion der C-Sprache hilft JavaScript, auf verschiedenen Betriebssystemen effizient zu laufen.

Hinter den Kulissen: Welche Sprache macht JavaScript?Hinter den Kulissen: Welche Sprache macht JavaScript?Apr 28, 2025 am 12:01 AM

JavaScript wird in Browsern und Node.js -Umgebungen ausgeführt und stützt sich auf die JavaScript -Engine, um Code zu analysieren und auszuführen. 1) abstrakter Syntaxbaum (AST) in der Parsenstufe erzeugen; 2) AST in die Kompilierungsphase in Bytecode oder Maschinencode umwandeln; 3) Führen Sie den kompilierten Code in der Ausführungsstufe aus.

Die Zukunft von Python und JavaScript: Trends und VorhersagenDie Zukunft von Python und JavaScript: Trends und VorhersagenApr 27, 2025 am 12:21 AM

Zu den zukünftigen Trends von Python und JavaScript gehören: 1. Python wird seine Position in den Bereichen wissenschaftlicher Computer und KI konsolidieren. JavaScript wird die Entwicklung der Web-Technologie fördern. Beide werden die Anwendungsszenarien in ihren jeweiligen Bereichen weiter erweitern und mehr Durchbrüche in der Leistung erzielen.

Python vs. JavaScript: Entwicklungsumgebungen und ToolsPython vs. JavaScript: Entwicklungsumgebungen und ToolsApr 26, 2025 am 12:09 AM

Sowohl Python als auch JavaScripts Entscheidungen in Entwicklungsumgebungen sind wichtig. 1) Die Entwicklungsumgebung von Python umfasst Pycharm, Jupyternotebook und Anaconda, die für Datenwissenschaft und schnelles Prototyping geeignet sind. 2) Die Entwicklungsumgebung von JavaScript umfasst Node.JS, VSCODE und WebPack, die für die Entwicklung von Front-End- und Back-End-Entwicklung geeignet sind. Durch die Auswahl der richtigen Tools nach den Projektbedürfnissen kann die Entwicklung der Entwicklung und die Erfolgsquote der Projekte verbessert werden.

Ist JavaScript in C geschrieben? Prüfung der BeweiseIst JavaScript in C geschrieben? Prüfung der BeweiseApr 25, 2025 am 12:15 AM

Ja, der Motorkern von JavaScript ist in C. 1) Die C -Sprache bietet eine effiziente Leistung und die zugrunde liegende Steuerung, die für die Entwicklung der JavaScript -Engine geeignet ist. 2) Die V8-Engine als Beispiel wird sein Kern in C geschrieben, wobei die Effizienz und objektorientierte Eigenschaften von C kombiniert werden.

JavaScripts Rolle: das Web interaktiv und dynamisch machenJavaScripts Rolle: das Web interaktiv und dynamisch machenApr 24, 2025 am 12:12 AM

JavaScript ist das Herzstück moderner Websites, da es die Interaktivität und Dynamik von Webseiten verbessert. 1) Es ermöglicht die Änderung von Inhalten, ohne die Seite zu aktualisieren, 2) Webseiten durch DOMAPI zu manipulieren, 3) Komplexe interaktive Effekte wie Animation und Drag & Drop, 4) die Leistung und Best Practices optimieren, um die Benutzererfahrung zu verbessern.

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

Video Face Swap

Video Face Swap

Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heiße Werkzeuge

EditPlus chinesische Crack-Version

EditPlus chinesische Crack-Version

Geringe Größe, Syntaxhervorhebung, unterstützt keine Code-Eingabeaufforderungsfunktion

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.

DVWA

DVWA

Damn Vulnerable Web App (DVWA) ist eine PHP/MySQL-Webanwendung, die sehr anfällig ist. Seine Hauptziele bestehen darin, Sicherheitsexperten dabei zu helfen, ihre Fähigkeiten und Tools in einem rechtlichen Umfeld zu testen, Webentwicklern dabei zu helfen, den Prozess der Sicherung von Webanwendungen besser zu verstehen, und Lehrern/Schülern dabei zu helfen, in einer Unterrichtsumgebung Webanwendungen zu lehren/lernen Sicherheit. Das Ziel von DVWA besteht darin, einige der häufigsten Web-Schwachstellen über eine einfache und unkomplizierte Benutzeroberfläche mit unterschiedlichen Schwierigkeitsgraden zu üben. Bitte beachten Sie, dass diese Software

MantisBT

MantisBT

Mantis ist ein einfach zu implementierendes webbasiertes Tool zur Fehlerverfolgung, das die Fehlerverfolgung von Produkten unterstützen soll. Es erfordert PHP, MySQL und einen Webserver. Schauen Sie sich unsere Demo- und Hosting-Services an.

SecLists

SecLists

SecLists ist der ultimative Begleiter für Sicherheitstester. Dabei handelt es sich um eine Sammlung verschiedener Arten von Listen, die häufig bei Sicherheitsbewertungen verwendet werden, an einem Ort. SecLists trägt dazu bei, Sicherheitstests effizienter und produktiver zu gestalten, indem es bequem alle Listen bereitstellt, die ein Sicherheitstester benötigen könnte. Zu den Listentypen gehören Benutzernamen, Passwörter, URLs, Fuzzing-Payloads, Muster für vertrauliche Daten, Web-Shells und mehr. Der Tester kann dieses Repository einfach auf einen neuen Testcomputer übertragen und hat dann Zugriff auf alle Arten von Listen, die er benötigt.