02.09.2019
Ein gewichteter, ungerichteter, planarer und verbundener Graph

Graph Algorithmen

Auf meiner Seite zu Graphensuche zeigte ich bereits einige einfache Graph Algorithmen, meistens über Suche in Graphen. Auf dieser Seite zeige ich einige weitere Algorithmen zu Graphen. Anders als auf dieser erstgenannten Seite, betrachten wir hier gewichtete Graphen. In einem gewichteten Graphen haben die Kanten zwischen den Knoten verschiedenen Gewichte, diese werden oben als die Dicke der Linien zwischen den Kreisen angezeigt. Die Gewichte können unterschiedliche Bedeutungen haben, abhängig vom konkreten Algorithmus.

Wir fangen an mit dem minimalen Spannbaum, bei dem die Kantengewichte die Kosten repräsentieren die beim hinzufügen der Kante zum Baum entstehen. Später präsentieren wir Algorithmen um den kürzesten Pfad in einem Graphen zu finden, dort repräsentiert das Gewicht die Länge zwischen zwei Knoten. Einfachheitshalber wählen wir die Kantengewichte zwischen 1 und 4. Diese können dann direkt in eine Dicke einer Linie übersetzt werden.


Selber Graph mit einem minimalen Spannbaum

Minimale Spannbäume

Ein Spannbaum ist eine Untermenge von Kanten eines verbundenen Graphen der alle Knoten verbindet aber keine Zyklen enthält. Ein verbundener Graph ist ein Graph ohne getrennte Unterteile die einander nicht erreichen können. Alle auf dieser Seite verwendeten Graphen sind verbunden. Ein minimaler Spannbaum (MSB) ist ein Spannbaum der in Bezug auf die Kantengewichte minimal ist, also im Sinne der Summe aller Gewichte. Oben stellen die grünen Kanten einen minimalen Spannbaum dar, der von Kruskals Algorithmus gefunden wurde. Wenn Sie genau hinsehen, sieht man das alle Knoten vom MSB erreicht werden. Die nächsten beiden Abschnitte stellen Algorithmen vor mit denen MSBs gefunden werden können.


Bereit zum startenKruskals Algorithmus läuftMinimaler Spannbaum gefunden

slowerplaypausefaster

Kruskals Algorithmus

Kruskals Algorithmus funktioniert folgendermaßen: am Anfang sind alle Knoten in einem eigenen separaten Baum. Alle Bäume zusammen ergeben einen Wald. Der Algorithmus betrachtet dann jede Kante, in aufsteigender Reihenfolge der Gewichte, und fügt eine Kante nur dann hinzu wenn sie zwei bisher unverbundene Bäume verbindet. Jeder Schritt verbindet also zwei Bäume zu einem, und reduziert so die Anzahl der Bäume um eins. Wenn der gesammte Wald nur noch aus einem Baum besteht, ist der minimale Spannbaum gefunden worden. Diese Strategie ist also von der sogenannten ‘greedy’ (engl. gierig) Sorte, findet aber eine global optimale Lösung für das Problem.


Bereit zum startenPrims Algorithmus läuftMinimaler Spannbaum gefunden

slowerplaypausefaster

Prims Algorithmus

Prims Algorithmus nutzt eine andere ‘greedy’ Strategie als Kruskals Algorithmus. Es fängt mit einem zufälligen Knoten an, und erweitert einen einzelnen Baum, Kante für Kante, bis er zu einem MSB wird. Der Knackpunkt ist wie die nächste Kante zum wachsen ausgewählt wird: aus der Liste all derer Kanten die zwischen dem aktuellen Baum und dem Rest des Graphen überbrücken, wird eine mit geringstem Gewicht ausgewählt. Bei gleichen Gewichten kann zufällig gewählt werden. Man beachte, dass Prims Algorithmus und Kruskals Algorithmus dasselbe geringste Gesammtgewicht feststellen (wie nach dem Durchlauf unter der Grafik angegeben), aber sie verwenden nicht notwendigerweise dieselben Kanten in ihren MSB (obwohl das oft der Fall ist).


Bereit zum startenDijkstras Algorithmus läuftSuche fertig

slowerplaypausefaster

Dijkstras Algorithmus

Dijkstras Algorithmus berechnet das sogenannte ‘single-source shortest paths’ Problem: für jeden Knoten wollen wir wissen, wie lange der kürzeste Pfad zu ihm durch den Graphen von einem vorgegebenen Startpunkt ist. Die Kantengewichte von vorhin stellen jetzt Distanzen zwischen den Knoten dar. Dickere Linien sind jetzt größere Abstände im Graphen. Der geometrische Abstand auf der Darstellungsebene ist hier nicht relevant, nur der durch die Kanten gegebenen Entfernungen. Die dann berechneten Distanzen werden als Zahlen in den Knoten dargestellt. Der grün gefüllte Knoten ist der Startknoten und hat eine Entfernung von null zu sich selbst.

Der Algorithmus kann grob as gewichtete Breitensuche charakterisiert werden. Um die nächste zu durchlaufende Kante auszuwählen, untersucht der Algorithmus alle Kanten zwischen den bereits erforschten Knoten und den anderen, sortiert aufsteigend nach Distanz vom Quellknoten. In der Darstellung oben kann man sehen, wie die Distanz des neuen Knotens sich oft nur um eins vom zuletzt hinzugefügten unterscheidet, und niemals geringer als zuvor ausfällt. Dies ist eine ähnliche Strategie wie bei Prims Algorithmus, und in der Tat machen die ausgewählten Kanten hier auch einen Spannbaum aus, nur im Allgemeinen keinen minimalen.


Ein gewichteter, gerichteter Graph mit negativen Kantenlängen

Negative Kantenlängen

Eine bisher nicht erwähnte Annahme über Dijkstras Algorithmus ist, dass alle Kantenlängen positiv oder gleich null sein müssen, damit der Algorithmus funktioniert. Wenn wir also ein Straßennetz modellieren macht das auch Sinn, da es keine negativen Fahrtzeiten gibt. Aber andere Anwendungen erfordern vielleicht negative Kantenlängen. In diesem Fall können wir uns nicht mehr auf den einfachen Dijkstras Algorithmus verlassen um die kürzesten Abstände zu ermitteln. Im Beispiel oben sind negative Kanten in rot dargestellt, die Dicke der Linien zeigt jetzt den Absolutwert der Länge an, eine dicke rote Linie ist also recht negativ im Wert. Wir haben jetzt einen gerichteten Graphen gewählt, bei dem die Kanten eine Richtung haben, weil Pfade durch ungerichtete Graphen mit negativen Kanten nicht wohldefiniert sind.


Bereit zum startenBellman-Ford Algorithmus läuftSuche fertigNegative Zyklen festgestellt

slowerplaypausefaster

Der Bellman-Ford Algorithmus

Der Bellman-Ford Algorithmus kann kürzeste Pfade auch in einem Graphen mit negativen Kantenlängen finden. Dies funktioniert aber nur, wenn es keine negativen Zyklen im Graphen gibt. Dies sind Zyklen bei denen die Pfadlänge um den Zyklus herum eine negative Summe ergibt. Wenn es solche Zyklen gibt, kann ein Pfad beliebig negativ werden, einfach indem er immer weiter um den negativen Zyklus herum führt. Wenn dies der Fall ist, muss der Algorithmus abbrechen und das Vorhandensein eines negativen Zyklus anzeigen. Im obigen Panel arbeiten wir immer mit einem Graphen der keine negativen Zyklen enthält. Der gegenteilige Fall wird im nächsten Panel gezeigt.

Die Anfangsbedingung des Algorithmus ist das alle Knoten außer des Startknotens (grün) eine Distanz unendlich (∞) haben. Dann gibt es eine Schleife über alle Knoten, bei denen neue, kürzere Pfade von diesem Knoten zum nächsten erwogen werden und die Entfernung des Knotens aktualisiert wird (kleine grüne Zahl im Knoten). Nach dem Ende eines Durchlaufs wird die aktuelle Entfernung jedes Knotens dann mit dieser Zahl aktualisiert. Anfangs ändert sich nicht viel, da die meisten neuen Entfernungen noch unendlich sind. Nach einer Weile, breiten sich kürzere, nicht-unendliche Distanzen vom Startknoten aus. An dem Punkt an dem sich die Distanzen nicht mehr ändern, obwohl alle Knoten betrachtet worden sind, ist der Algorithmus stabil geworden und er gibt die errechneten Distanzen als Ergebnis zurück. Manche Knoten bleiben bei der Entfernung unendlich, falls es keinen Pfad vom Startknoten zu ihnen gibt.


Bereit zum startenBellman-Ford Algorithmus läuftSuche fertigNegative Zyklen festgestellt

slowerplaypausefaster

Negative Zyklen

Es gibt zwei mögliche Anzeichen für einen negativen Zyklus: erstens, nachdem über alle Knoten so oft iteriert wurde wie es insgesamt Knoten im Graphen gibt, wird der Graph immer noch nicht stabil, d.h. Distanzen ändern sich noch, dann gibt es mindestens einen negativen Zyklus. Eine hinreichende aber nicht notwendige Bedingung, ist dass der Startknoten einen negativen Wert annimmt. Diese Fälle werden im Panel hierüber gezeigt, mit einem Graphen der negative Zyklen enthält. Ich habe die Anzeige ein bisschen beschleunigt, denn es kann eine Weile dauern bis negative Zyklen gefunden sind.


Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken. Insbesondere gibt es mehr zu Graphensuche.

Quellen (englischsprachig)