Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


31. Gewichtete Graphen



Kürzester Pfad

Das Problem des kürzesten Pfades besteht darin, in einem gewichteten Graph den zwei gegebene Knoten x und y verbindenden Pfad zu finden, der die Eigenschaft hat, daß die Summe der Gewichte aller Kanten innerhalb der Menge aller solchen Pfade minimal ist.

Auch wenn die Gewichte alle 1 betragen, ist das Problem dennoch interessant: Es lautet dann, daß der x und y verbindende Pfad zu finden ist, der eine minimale Anzahl von Kanten enthält. Außerdem haben wir bereits einen Algorithmus betrachtet, der dieses Problem löst: Breitensuche. Mittels Induktion läßt sich leicht zeigen, daß, bei einer in x beginnenden Breitensuche zuerst alle Knoten besucht werden, die von x aus über eine Kante erreicht werden können, dann alle Knoten, die von x aus über zwei Kanten erreicht werden können usw., so daß alle Knoten, die über k Kanten erreicht werden können, besucht werden, bevor irgendein Knoten angetroffen wird, der k + 1 Kanten erfordert. Wenn daher y zum erstenmal angetroffen wird, ist der kürzeste Pfad von x gefunden worden, da keine kürzeren Pfade y erreicht haben (vgl. Abbildung 29.14).

Im allgemeinen könnte der Pfad von x nach y alle Knoten berühren, so daß wir gewöhnlich das Problem des Auffindens der kürzesten Pfade betrachten, die einen gegebenen Knoten x mit allen anderen Knoten im Graph verbinden. Auch diesmal erweist es sich, daß das Problem mit dem oben angegebenen Algorithmus für die Traversierung eines Graphen mit Prioritätssuche leicht gelöst werden kann.

Wenn wir den kürzesten Pfad von x zu jedem anderen Knoten im Graph zeichnen, so erhalten wir natürlich keine Zyklen, und es liegt ein Spannbaum vor. Jeder Knoten führt zu einem anderen Spannbaum; Abbildung 31.10 zeigt als Beispiel die aus den kürzesten Pfaden bestehenden Spannbäume für die Knoten A, G und M in dem von uns betrachteten Graphen.

Abbildung 31.10
Abbildung 31.10 Spannbäume der kürzesten Pfade.

Die Lösung dieses Problems mittels Prioritätssuche ist mit der Lösung für den minimalen Spannbaum praktisch identisch: Wir erzeugen den Baum für den Knoten x, indem wir bei jedem Schritt den Knoten vom Rand hinzufügen, der x am nächsten liegt (zuvor fügten wir den Knoten hinzu, der dem Baum am nächsten liegt). Um zu ermitteln, welcher Randknoten x am nächsten liegt, verwenden wir das Feld val: Für jeden Baumknoten k ist val[k] der kürzeste Abstand (welcher aus Baumknoten bestehen muß) von diesem Knoten zu x. Wenn k dem Baum hinzugefügt wird, aktualisieren wir den Rand, indem wir die Adjazenzliste von k durchlaufen. Für jeden Knoten t in dieser Liste hat der kürzeste Abstand von t^.v über k zu x den Wert val[k] + t^.w. Daher läßt sich der Algorithmus leicht implementieren, indem man diese Größe für priority in dem Programm für die Traversierung von Graphen mit Prioritätssuche verwendet.

Abbildung 31.11
Abbildung 31.11 Anfangsschritte der Erzeugung eines Baumes der kürzesten Pfade.

Abbildung 31.11 zeigt die ersten vier Schritte bei der Erzeugung des aus den kürzesten Pfaden bestehenden Spannbaumes für Knoten A in unserem Beispiel. Zuerst besuchen wir den zu A nächstgelegenen Knoten, nämlich B. Danach haben sowohl C als auch F einen Abstand 2 von A, daher besuchen wir sie als nächste (in der Reihenfolge, in der die Prioritätswarteschlange sie zurückgibt, in diesem Falle erst C und dann F). Die Vollendung des Prozesses ist in Abbildung 31.12 dargestellt, und Abbildung 31.13 zeigt den Inhalt der Prioritätswarteschlange während der Suche.

Abbildung 31.12
Abbildung 31.12 Vollendung der Erzeugung eines Baumes der kürzesten Pfade.

Abbildung 31.13
Abbildung 31.13 Inhalt der Prioritätswarteschlange während der Erzeugung eines Baumes der kürzesten Pfade.

Als nächster Knoten kann D mit F oder mit B verbunden werden, so daß ein Pfad der Länge 3 bis A entsteht. (Der Algorithmus verbindet D mit B, da B vor F zum Baum hinzugefügt wurde; daher gehörte D bereits dem Rand an, als F zum Baum hinzugefügt wurde, und F lieferte keinen kürzeren Pfad zu A.) Anschließend werden L E M G J K I und H zum Baum hinzugefügt, entsprechend der wachsenden Reihenfolge ihres minimalen Abstands von A. Somit ist zum Beispiel H der von A am weitesten entfernte Knoten; der Pfad AFEGH hat ein Gesamtgewicht von 8. Es gibt keinen kürzeren Pfad zu H, und der kürzeste Pfad von A zu jedem anderen Knoten ist nicht länger.

Abbildung 31.14
Abbildung 31.14 Darstellung des Spannbaumes der kürzesten Pfade.

Abbildung 31.14 zeigt die endgültigen Werte der Felder dad und val für unser Beispiel. Demzufolge hat der kürzeste Pfad von A zu H ein Gesamtgewicht von 8 (das in val[8] zu finden ist, dem Eintrag für H) und verläuft von A über F und E und G zu H (was gefunden werden kann, indem man beginnend bei H den Weg im Feld dad zurückverfolgt). Beachten Sie, daß dieses Programm darauf aufbaut, daß der Eintrag in val für die Wurzel 0 ist, was wir für listpfs vereinbart hatten.

Eigenschaft 31.4 Die Prioritätssuche in lichten Graphen berechnet den Baum der kürzesten Pfade in O((E + V) log V) Schritten.

Die Korrektheit des Algorithmus kann auf ähnliche Weise bewiesen werden wie im Falle von Eigenschaft 31.1. Wenn die Prioritätswarteschlange wie in Kapitel 12 unter Benutzung von Heaps implementiert wird, kann für Prioritätssuche immer garantiert werden, daß die angegebene Schranke für die Laufzeit eingehalten wird, unabhängig davon, welche Prioritätsregel verwendet wird. w.z.b.w.

Weiter unten sehen wir, wie eine andere Implementation der Prioritätswarteschlange einen Algorithmus mit zu V2 proportionaler Laufzeit ergeben kann, der für dichte Graphen geeignet ist. Für das Problem des kürzesten Pfades läuft dies auf ein Verfahren hinaus, das mindestens auf das Jahr 1959 zurückgeht und im allgemeinen E. Dijkstra zugeschrieben wird.

Abbildung 31.15
Abbildung 31.15 Erzeugung eines umfangreichen Baumes der kürzesten Pfade.

Abbildung 31.15 zeigt einen größeren Baum der kürzesten Pfade. Wie zuvor werden in diesem Graph die Längen der Kanten als Gewichte benutzt, so daß die Aufgabe darin besteht, den Pfad minimaler Länge vom linken unteren Knoten zu jedem anderen Knoten zu finden. Später erörtern wir eine Verbesserung, die für solche Graphen zweckmäßig sein kann. Doch selbst in diesem Graph könnte es angebracht sein, andere Werte für die Gewichte zu verwenden; wenn dieser Graph zum Beispiel ein Labyrinth darstellt (siehe Kapitel 29), könnte das Gewicht einer Kante die Entfernung im Labyrinth selbst darstellen und nicht die im Graph gezeichneten Abkürzungen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]