Dijkstra-Algorithmus

Eine weitere Heuristik: Dijkstra

Der Dijkstra-Algorithmus ist ein zentraler Algorithmus der Informatik und insbesondere der Graphentheorie. Entwickelt von dem niederländischen Informatiker Edsger W. Dijkstra, dient er dazu, den kürzesten Weg zwischen zwei Knoten in einem gewichteten gerichteten Graphen zu finden.

Zweck des Algorithmus

Der Hauptzweck des Dijkstra-Algorithmus besteht darin, den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen zu finden. Der „kürzeste Weg" bezieht sich auf die Summe der Kantengewichte entlang des Pfades zwischen den Knoten – das Ziel ist der Pfad mit der minimalen Gesamtgewichtung.

Schritt für Schritt

Die grundlegenden Schritte des Dijkstra-Algorithmus:

1. Startpunkt festlegen Wir beginnen mit einer ausgewählten Startstadt, die wir als „Startpunkt s" bezeichnen.
2. Entfernungen notieren Wir notieren die Entfernungen von „Startpunkt s" zu allen benachbarten Knoten, einschließlich „Knoten v". Diese Entfernungen sind die Längen der Straßen oder Verbindungen zwischen diesen Orten.
3. Nächsten Schritt auswählen Wir wählen den nächsten Schritt, indem wir den kürzesten Weg zu einem benachbarten Knoten nehmen. Dieser benachbarte Knoten kann „Knoten v" oder ein anderer Knoten sein, je nachdem, welcher den kürzesten Weg hat.
4. Entfernungen aktualisieren Wir aktualisieren die Entfernungen zu den Knoten, die wir bereits besucht haben, basierend auf dem gerade gewählten Weg. Wenn es einen kürzeren Weg zu einem Knoten gibt, aktualisieren wir die Entfernung zu diesem Knoten.
5. Besuchten Knoten markieren Wir markieren den Knoten, den wir gerade besucht haben, als „besucht", damit wir nicht zurückkehren.
6. Wiederholen Wir wiederholen die Schritte 3 bis 5, bis wir unser Ziel erreichen (zum Beispiel „Knoten v") oder alle Knoten besucht haben.
7. Fertig Am Ende haben wir den kürzesten Weg von „Startpunkt s" zu „Knoten v" gefunden.

Vertiefung

Für ein ausführliches Verständnis mit Beispielen steht dir ein PDF-Dokument zur Verfügung: