Finden Sie mit dem Dijkstra-Algorithmus den kürzesten Weg zwischen zwei Punkten in einem Diagramm

Das Finden des kürzesten Pfades zwischen zwei Punkten in einem Diagramm ist ein häufiges Problem in Datenstrukturen, insbesondere bei der Optimierung.

Ein Graph ist eine Reihe von Knoten, die durch Kanten verbunden sind. Diagramme können gewichtet (Kanten tragen Werte) und gerichtet (Kanten haben Richtung) werden.

Einige Anwendungen hierfür sind Flugbahnoptimierung oder 6 Grad von Kevin Bacon.

Dijkstra-Algorithmus

Die häufigste Lösung für dieses Problem ist der Dijkstra-Algorithmus, der den kürzesten Pfad zwischen dem aktuellen Knoten und allen seinen Nachbarn aktualisiert.

Nach dem Aktualisieren der Entfernung aller Nachbarn bewegt es sich zu dem Knoten mit der geringsten Entfernung und wiederholt den Vorgang mit allen nicht besuchten Nachbarn. Dieser Vorgang wird fortgesetzt, bis das gesamte Diagramm besucht wurde.

Bild der Codeebenen

Schritt 0:

Unser Diagramm muss so eingerichtet werden, dass wir die erforderlichen Werte aufzeichnen können. An jeder Kante haben wir den Abstand zwischen den beiden Knoten, die sie verbinden. Auf jedem Knoten haben wir den kürzesten Abstand vom Startknoten.

Setzen wir den Wert für jeden Knoten auf positiv unendlich und setzen Sie den Wert für den Startknoten auf null.

Schritt 1:

Sehen Sie sich alle Knoten direkt neben dem Startknoten an. Die Werte, die von den Kanten getragen werden, die den Start und diese benachbarten Knoten verbinden, sind die kürzesten Abstände zu den jeweiligen Knoten.

Notieren Sie diese Entfernungen auf dem Knoten - überschreiben Sie die Unendlichkeit - und kreuzen Sie auch die Knoten an, was bedeutet, dass ihr kürzester Weg gefunden wurde.

Schritt 2:

Wählen Sie einen der Knoten aus, dessen kürzester Pfad berechnet wurde. Wir nennen dies unseren Pivot. Schauen Sie sich die angrenzenden Knoten an (wir nennen diese unsere Zielknoten) und die Abstände, die sie voneinander trennen.

Für jeden Zielknoten:

  • Wenn der Wert im Pivot plus dem Kantenwert, der ihn verbindet, kleiner als der Wert des Zielknotens ist, aktualisieren Sie seinen Wert, da ein neuer kürzerer Pfad gefunden wurde.
  • Wenn alle Routen zu diesem Zielknoten erkundet wurden, kann er durchgestrichen werden.

Schritt 3:

Wiederholen Sie Schritt 2, bis alle Knoten durchgestrichen sind. Wir haben jetzt ein Diagramm, in dem die in einem Knoten gehaltenen Werte den kürzesten Abstand zum Startknoten haben.

Mehr Informationen:

Mehr zum Dijkstra-Algorithmus

Andere Algorithmen für kürzeste Wege