Dijkstras Algorithmus für kürzeste Wege - Eine detaillierte und visuelle Einführung

Herzlich willkommen! Wenn Sie schon immer den Algorithmus von Dijkstra lernen und verstehen wollten, dann ist dieser Artikel genau das Richtige für Sie. Sie werden sehen, wie es hinter den Kulissen funktioniert, mit einer schrittweisen grafischen Erklärung.

Du wirst es lernen:

  • Grundlegende Grafikkonzepte (eine kurze Übersicht).
  • Wofür der Dijkstra-Algorithmus verwendet wird.
  • Wie es hinter den Kulissen funktioniert, anhand eines schrittweisen Beispiels.

Lass uns anfangen. ✨

🔹 Einführung in Grafiken

Beginnen wir mit einer kurzen Einführung in Diagramme.

Grundlegendes Konzept

Diagramme sind Datenstrukturen, die zur Darstellung von "Verbindungen" zwischen Elementpaaren verwendet werden.

  • Diese Elemente werden als Knoten bezeichnet . Sie repräsentieren reale Objekte, Personen oder Entitäten.
  • Die Verbindungen zwischen Knoten werden Kanten genannt .

Dies ist eine grafische Darstellung eines Diagramms:

Knoten werden durch farbige Kreise dargestellt, und Kanten werden durch Linien dargestellt, die diese Kreise verbinden.

💡 Tipp: Zwei Knoten sind verbunden, wenn sich zwischen ihnen eine Kante befindet.

Anwendungen

Diagramme sind direkt auf reale Szenarien anwendbar. Zum Beispiel könnten wir Diagramme verwenden, um ein Transportnetz zu modellieren, in dem Knoten Einrichtungen darstellen, die Produkte senden oder empfangen, und Kanten Straßen oder Wege darstellen, die sie verbinden (siehe unten).

Arten von Graphen

Grafiken können sein:

  • Ungerichtet: Wenn Sie für jedes Paar verbundener Knoten in beide Richtungen von einem Knoten zum anderen wechseln können.
  • Richtung: Wenn Sie für jedes Paar verbundener Knoten nur in einer bestimmten Richtung von einem Knoten zum anderen wechseln können. Wir verwenden Pfeile anstelle einfacher Linien, um gerichtete Kanten darzustellen.

💡 Tipp: In diesem Artikel arbeiten wir mit ungerichteten Diagrammen.

Gewichtete Graphen

Ein Gewichtsdiagramm ist ein Diagramm, dessen Kanten ein "Gewicht" oder "Kosten" haben. Das Gewicht einer Kante kann Entfernung, Zeit oder alles darstellen, was die "Verbindung" zwischen dem Knotenpaar modelliert, das sie verbindet.

In der gewichteten Grafik unten sehen Sie beispielsweise eine blaue Zahl neben jeder Kante. Diese Zahl wird verwendet, um das Gewicht der entsprechenden Kante darzustellen.

💡 Tipp: Diese Gewichte sind für den Dijkstra-Algorithmus unerlässlich. Sie werden gleich sehen, warum.

🔸 Einführung in den Dijkstra-Algorithmus

Nachdem Sie nun die Grundkonzepte von Graphen kennen, wollen wir uns mit diesem erstaunlichen Algorithmus befassen.

  • Zweck und Anwendungsfälle
  • Geschichte
  • Grundlagen des Algorithmus
  • Bedarf

Zweck und Anwendungsfälle

Mit dem Dijkstra-Algorithmus können Sie den kürzesten Weg zwischen Knoten in einem Diagramm finden. Insbesondere können Sie den kürzesten Pfad von einem Knoten (als "Quellknoten" bezeichnet) zu allen anderen Knoten im Diagramm finden , wodurch ein Baum mit dem kürzesten Pfad erstellt wird.

Dieser Algorithmus wird in GPS-Geräten verwendet, um den kürzesten Weg zwischen dem aktuellen Standort und dem Ziel zu finden. Es hat breite Anwendungen in der Industrie, insbesondere in Bereichen, in denen Modellierungsnetzwerke erforderlich sind.

Geschichte

Dieser Algorithmus wurde von Dr. Edsger W. Dijkstra, einem brillanten niederländischen Informatiker und Software-Ingenieur, erstellt und veröffentlicht.

1959 veröffentlichte er einen dreiseitigen Artikel mit dem Titel "Ein Hinweis zu zwei Problemen im Zusammenhang mit Grafiken", in dem er seinen neuen Algorithmus erläuterte.

Während eines Interviews im Jahr 2001 enthüllte Dr. Dijkstra, wie und warum er den Algorithmus entworfen hat:

Was ist der kürzeste Weg von Rotterdam nach Groningen? Es ist der Algorithmus für den kürzesten Weg, den ich in ungefähr 20 Minuten entworfen habe. Eines Morgens war ich mit meiner jungen Verlobten in Amsterdam einkaufen, und müde setzten wir uns auf die Caféterrasse, um eine Tasse Kaffee zu trinken, und ich dachte nur darüber nach, ob ich das tun könnte, und entwarf dann den Algorithmus für den kürzesten Weg . Wie gesagt, es war eine 20-minütige Erfindung. Tatsächlich wurde es 1959, drei Jahre später, veröffentlicht. Die Veröffentlichung ist immer noch sehr schön. Einer der Gründe, warum es so schön ist, war, dass ich es ohne Bleistift und Papier entworfen habe. Ohne Bleistift und Papier sind Sie fast gezwungen, alle vermeidbaren Komplexitäten zu vermeiden. Schließlich wurde dieser Algorithmus zu meinem großen Erstaunen zu einem der Eckpfeiler meines Ruhmes. - Wie im Artikel Edsger W. zitiert.Dijkstra aus Ein Interview mit Edsger W. Dijkstra.

Unglaublich, oder? In nur 20 Minuten entwarf Dr. Dijkstra einen der bekanntesten Algorithmen in der Geschichte der Informatik.

Grundlagen des Dijkstra-Algorithmus

  • Der Dijkstra-Algorithmus beginnt im Wesentlichen an dem von Ihnen ausgewählten Knoten (dem Quellknoten) und analysiert den Graphen, um den kürzesten Pfad zwischen diesem Knoten und allen anderen Knoten im Graphen zu finden.
  • Der Algorithmus verfolgt die derzeit bekannte kürzeste Entfernung von jedem Knoten zum Quellknoten und aktualisiert diese Werte, wenn er einen kürzeren Pfad findet.
  • Sobald der Algorithmus den kürzesten Pfad zwischen dem Quellknoten und einem anderen Knoten gefunden hat, wird dieser Knoten als "besucht" markiert und dem Pfad hinzugefügt.
  • Der Vorgang wird fortgesetzt, bis alle Knoten im Diagramm zum Pfad hinzugefügt wurden. Auf diese Weise haben wir einen Pfad, der den Quellknoten mit allen anderen Knoten verbindet und dem kürzesten Pfad folgt, der möglich ist, um jeden Knoten zu erreichen.

Bedarf

Der Dijkstra-Algorithmus kann nur mit Graphen mit positiven Gewichten arbeiten. Dies liegt daran, dass während des Prozesses die Gewichte der Kanten hinzugefügt werden müssen, um den kürzesten Weg zu finden.

Wenn das Diagramm ein negatives Gewicht enthält, funktioniert der Algorithmus nicht ordnungsgemäß. Sobald ein Knoten als "besucht" markiert wurde, wird der aktuelle Pfad zu diesem Knoten als der kürzeste Pfad markiert, um diesen Knoten zu erreichen. Und negative Gewichte können dies ändern, wenn das Gesamtgewicht nach diesem Schritt verringert werden kann.

🔹 Beispiel für den Dijkstra-Algorithmus

Nachdem Sie nun mehr über diesen Algorithmus erfahren haben, sehen wir uns anhand eines schrittweisen Beispiels an, wie er hinter den Kulissen funktioniert.

Wir haben diese Grafik:

Der Algorithmus generiert den kürzesten Pfad vom Knoten 0zu allen anderen Knoten im Diagramm.

💡 Tipp: In diesem Diagramm wird davon ausgegangen, dass das Gewicht der Kanten den Abstand zwischen zwei Knoten darstellt.

Wir haben für jeden Knoten im Diagramm den kürzesten Weg von Knoten 0zu Knoten 1, von Knoten 0zu Knoten 2, von Knoten 0zu Knoten 3usw.

Anfangs haben wir diese Liste von Entfernungen (siehe die Liste unten):

  • Der Abstand vom Quellknoten zu sich selbst beträgt 0. In diesem Beispiel ist der Quellknoten ein Knoten 0, es kann sich jedoch um einen beliebigen Knoten handeln, den Sie auswählen.
  • Die Entfernung vom Quellknoten zu allen anderen Knoten wurde noch nicht bestimmt, daher verwenden wir das Unendlichkeitssymbol, um dies zunächst darzustellen.

Wir haben auch diese Liste (siehe unten), um die Knoten zu verfolgen, die noch nicht besucht wurden (Knoten, die nicht im Pfad enthalten waren):

💡 Tipp: Denken Sie daran, dass der Algorithmus abgeschlossen ist, sobald alle Knoten zum Pfad hinzugefügt wurden.

Da wir uns dafür entscheiden, am Knoten zu beginnen 0, können wir diesen Knoten als besucht markieren. Entsprechend streichen wir es von der Liste der nicht besuchten Knoten ab und fügen dem entsprechenden Knoten im Diagramm einen roten Rand hinzu:

Jetzt müssen wir den Abstand vom Knoten 0zu den benachbarten Knoten überprüfen . Wie Sie sehen können, sind dies Knoten 1und 2(siehe die roten Ränder):

💡 Tipp: Dies bedeutet nicht, dass wir die beiden benachbarten Knoten sofort zum kürzesten Pfad hinzufügen. Bevor wir diesem Pfad einen Knoten hinzufügen, müssen wir prüfen, ob wir den kürzesten Pfad gefunden haben, um ihn zu erreichen. Wir führen lediglich einen ersten Prüfungsprozess durch, um die verfügbaren Optionen zu ermitteln.

Wir müssen die Abstände von Knoten 0zu Knoten 1und Knoten 2mit den Gewichten der Kanten aktualisieren , die sie mit dem Knoten 0(dem Quellknoten) verbinden. Diese Gewichte sind 2 bzw. 6:

Nach dem Aktualisieren der Abstände der benachbarten Knoten müssen wir:

  • Wählen Sie den Knoten aus, der dem Quellknoten am nächsten liegt, basierend auf den aktuell bekannten Entfernungen.
  • Markieren Sie es als besucht.
  • Fügen Sie es dem Pfad hinzu.

Wenn wir die Liste der Entfernungen überprüfen, können wir sehen, dass der Knoten 1die kürzeste Entfernung zum Quellknoten hat (eine Entfernung von 2), also fügen wir sie dem Pfad hinzu.

Im Diagramm können wir dies mit einem roten Rand darstellen:

Wir markieren es mit einem roten Quadrat in der Liste, um anzuzeigen, dass es "besucht" wurde und dass wir den kürzesten Weg zu diesem Knoten gefunden haben:

Wir streichen es von der Liste der nicht besuchten Knoten ab:

Jetzt müssen wir die neuen benachbarten Knoten analysieren, um den kürzesten Weg zu finden, um sie zu erreichen. Wir werden nur die Knoten analysieren, die an die Knoten angrenzen, die bereits Teil des kürzesten Pfades sind (der mit roten Rändern markierte Pfad).

Knoten 3und Knoten 2grenzen beide an Knoten, die sich bereits im Pfad befinden, da sie direkt mit Knoten 0bzw. Knoten verbunden 1sind, wie Sie unten sehen können. Dies sind die Knoten, die wir im nächsten Schritt analysieren werden.

Da die Entfernung von Quellknoten zu Knoten bereits 2in unserer Liste vermerkt ist, müssen wir die Entfernung diesmal nicht aktualisieren. Wir müssen nur die Entfernung vom Quellknoten zum neuen benachbarten Knoten (Knoten 3) aktualisieren :

Dieser Abstand beträgt 7 . Mal sehen warum.

Um den Abstand vom Quellknoten zu einem anderen Knoten (in diesem Fall Knoten 3) zu ermitteln, addieren wir die Gewichte aller Kanten, die den kürzesten Weg zum Erreichen dieses Knotens bilden:

  • Für Knoten 3: Der Gesamtabstand beträgt 7, da wir die Gewichte der Kanten addieren, die den Pfad bilden 0 -> 1 -> 3(2 für die Kante 0 -> 1und 5 für die Kante 1 -> 3).

Nachdem wir den Abstand zu den benachbarten Knoten haben, müssen wir auswählen, welcher Knoten dem Pfad hinzugefügt werden soll. Wir müssen den nicht besuchten Knoten mit der kürzesten (derzeit bekannten) Entfernung zum Quellknoten auswählen .

Aus der Liste der Entfernungen können wir sofort erkennen, dass dies ein Knoten 2mit der Entfernung 6 ist :

Wir fügen es dem Pfad grafisch mit einem roten Rand um den Knoten und einem roten Rand hinzu:

Wir markieren es auch als besucht, indem wir ein kleines rotes Quadrat in die Liste der Entfernungen einfügen und es von der Liste der nicht besuchten Knoten streichen:

Jetzt müssen wir den Vorgang wiederholen, um den kürzesten Weg vom Quellknoten zum neuen benachbarten Knoten, dem Knoten, zu finden 3.

Sie können sehen, dass wir zwei mögliche Wege haben 0 -> 1 -> 3oder 0 -> 2 -> 3. Mal sehen, wie wir entscheiden können, welcher der kürzeste Weg ist.

Der Knoten hat 3bereits eine Entfernung in der Liste, die zuvor aufgezeichnet wurde ( 7, siehe Liste unten). Dieser Abstand war das Ergebnis eines vorherigen Schritts, bei dem wir die Gewichte 5 und 2 der beiden Kanten addierten, die wir überqueren mussten, um dem Pfad zu folgen 0 -> 1 -> 3.

Aber jetzt haben wir eine andere Alternative. Wenn wir dem Weg folgen wählen 0 -> 2 -> 3, müssten wir zwei Kanten folgen 0 -> 2und 2 -> 3mit Gewichten 6 und 8 ,beziehungsweise,Dies entspricht einer Gesamtentfernung von 14 .

Die erste (vorhandene) Entfernung ist eindeutig kürzer (7 vs. 14), daher behalten wir den ursprünglichen Pfad bei 0 -> 1 -> 3. Wir aktualisieren die Entfernung nur, wenn der neue Pfad kürzer ist.

Daher fügen wir diesen Knoten mit der ersten Alternative zum Pfad hinzu : 0 -> 1 -> 3.

Wir markieren diesen Knoten als besucht und streichen ihn aus der Liste der nicht besuchten Knoten ab:

Jetzt wiederholen wir den Vorgang noch einmal.

Wir müssen die neuen benachbarten Knoten überprüfen, die wir bisher nicht besucht haben. Diesmal sind diese Knoten Knoten 4und Knoten, 5da sie an den Knoten angrenzen 3.

Wir aktualisieren die Abstände dieser Knoten zum Quellknoten und versuchen immer, wenn möglich einen kürzeren Pfad zu finden:

  • Für Knoten 4: Der Abstand zum Pfad   beträgt 170 -> 1 -> 3 -> 4 .
  • Für Knoten 5: Der Abstand zum Pfad beträgt 220 -> 1 -> 3 -> 5 .

💡 Tipp: Beachten Sie, dass wir nur den kürzesten Weg (rot markiert) verlängern können. Wir können keine Pfade berücksichtigen, die uns durch Kanten führen, die nicht zum kürzesten Pfad hinzugefügt wurden (z. B. können wir keinen Pfad bilden, der durch die Kante führt 2 -> 3).

Wir müssen auswählen, welcher nicht besuchte Knoten jetzt als besucht markiert wird. In diesem Fall handelt es sich um einen Knoten, 4da er die kürzeste Entfernung in der Liste der Entfernungen aufweist. Wir fügen es grafisch in das Diagramm ein:

Wir markieren es auch als "besucht", indem wir der Liste ein kleines rotes Quadrat hinzufügen:

Und wir streichen es von der Liste der nicht besuchten Knoten ab:

Und wir wiederholen den Vorgang noch einmal. Wir überprüfen die benachbarten Knoten: Knoten 5und Knoten 6. Wir müssen jeden möglichen Pfad analysieren, dem wir folgen können, um sie von Knoten aus zu erreichen, die bereits als besucht markiert und dem Pfad hinzugefügt wurden.

Für Knoten 5:

  • Die erste Möglichkeit besteht darin, dem Pfad zu folgen 0 -> 1 -> 3 -> 5, der einen Abstand von 22 vom Quellknoten hat (2 + 5 + 15). Diese Entfernung wurde bereits in einem vorherigen Schritt in der Liste der Entfernungen aufgezeichnet.
  • Die zweite Möglichkeit wäre, dem Pfad zu folgen 0 -> 1 -> 3 -> 4 -> 5, der einen Abstand von 23 vom Quellknoten hat (2 + 5 + 10 + 6).

Der erste Pfad ist eindeutig kürzer, daher wählen wir ihn für den Knoten 5.

Für Knoten 6:

  • Der verfügbare Pfad ist 0 -> 1 -> 3 -> 4 -> 6, der einen Abstand von 19 vom Quellknoten hat (2 + 5 + 10 + 2).

Wir markieren den Knoten mit der kürzesten (derzeit bekannten) Entfernung als besucht. In diesem Fall Knoten 6.

Und wir streichen es von der Liste der nicht besuchten Knoten ab:

Jetzt haben wir diesen Pfad (rot markiert):

Nur ein Knoten wurde noch nicht besucht, Knoten 5. Mal sehen, wie wir es in den Pfad aufnehmen können.

Es gibt drei verschiedene Pfade, über die wir den Knoten 5von den Knoten erreichen können, die dem Pfad hinzugefügt wurden:

  • Option 1:0 -> 1 -> 3 -> 5 mit einem Abstand von 22 (2 + 5 + 15).
  • Option 2:0 -> 1 -> 3 -> 4 -> 5 mit einem Abstand von 23 (2 + 5 + 10 + 6).
  • Option 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 mit einem Abstand von 25 (2 + 5 + 10 + 2 + 6).

Wir wählen den kürzesten Weg: 0 -> 1 -> 3 -> 5mit einer Entfernung von 22 .

Wir markieren den Knoten als besucht und streichen ihn aus der Liste der nicht besuchten Knoten ab:

Und voilà! Wir haben das Endergebnis mit dem kürzesten Weg vom Knoten 0zu jedem Knoten im Diagramm.

Im Diagramm markieren die roten Linien die Kanten, die zum kürzesten Pfad gehören. Sie müssen diesen Kanten folgen, um dem kürzesten Weg zu folgen, um einen bestimmten Knoten im Diagramm ab Knoten zu erreichen 0.

Wenn Sie beispielsweise den Knoten 6vom Knoten aus erreichen möchten 0, müssen Sie nur den roten Rändern folgen, und Sie folgen 0 -> 1 -> 3 -> 4 - > 6automatisch dem kürzesten Pfad .

🔸 Zusammenfassend

  • Diagramme werden verwendet, um Verbindungen zwischen Objekten, Personen oder Entitäten zu modellieren. Sie haben zwei Hauptelemente: Knoten und Kanten. Knoten repräsentieren Objekte und Kanten repräsentieren die Verbindungen zwischen diesen Objekten.
  • Der Dijkstra-Algorithmus findet den kürzesten Weg zwischen einem bestimmten Knoten (der als "Quellknoten" bezeichnet wird) und allen anderen Knoten in einem Diagramm.
  • Dieser Algorithmus verwendet die Gewichte der Kanten, um den Pfad zu finden, der den Gesamtabstand (Gewicht) zwischen dem Quellknoten und allen anderen Knoten minimiert.

Ich hoffe wirklich, dass Ihnen mein Artikel gefallen hat und Sie ihn hilfreich fanden. Jetzt wissen Sie, wie der Dijkstra-Algorithmus hinter den Kulissen funktioniert. Folgen Sie mir auf Twitter @EstefaniaCassN und sehen Sie sich meine Online-Kurse an.