Djikstra Algorithmus

Eine weitere Heuristik ist der Dijkstra - Algorithmus

Der Dijkstra-Algorithmus ist ein Algorithmus in der Informatik und insbesondere im Bereich der Graphentheorie. Er wurde von dem niederländischen Informatiker W. Dijkstra entwickelt und dient dazu, den kürzesten Weg zwischen zwei Knoten in einem gewichteten gerichteten Graphen zu finden. Soweit so gut!

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, wobei das Ziel darin besteht, den Pfad mit der minimalen Gesamtgewichtung zu ermitteln.

Startpunkt festlegen: Wir beginnen mit einer ausgewählten Startstadt, die wir als "Startpunkt s" bezeichnen.
Notieren der Entfernungen:
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.
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.
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 Sie die Entfernung zu diesem Knoten.
Markieren des besuchten Knotens: Wir markieren den Knoten, den wir gerade besucht haben, als "besucht", damit wir nicht zurückkehren.
Wiederholen: Wir wiederholen die Schritte 3 bis 5, bis wir unser Ziel erreichen (zum Beispiel "Knoten v") oder alle Knoten besucht haben.