Robert Sedgewick: Algorithmen

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


31. Gewichtete Graphen



Oft möchten wir praktische Probleme unter Verwendung von Graphen modellieren, in denen mit jeder Kante Gewichte oder Kosten verknüpft sind. Auf einer Karte der Fluglinien, auf der Kanten Flugstrecken darstellen, könnten diese Gewichte Entfernungen oder Flugpreise bezeichnen. In einer elektrischen Schaltung, in der Kanten Drähte darstellen, könnten als Gewichte Länge oder Kosten des Drahtes verwendet werden. In einem Scheduling-Chart können Gewichte den Zeitaufwand oder Ausführungs- oder Wartekosten von Aufgaben darstellen.

Fragen, die mit der Minimierung von Kosten zusammenhängen, entstehen in solchen Situationen in natürlicher Weise. Im vorliegenden Kapitel wollen wir Algorithmen für zwei derartige Probleme ausführlich betrachten: »Finde die mit den geringsten Kosten verbundene Möglichkeit, alle Punkte zu verbinden«, und »finde den mit den geringsten Kosten verbundenen Pfad zwischen zwei gegebenen Punkten.« Das erste Problem, das offensichtlich für Graphen von Nutzen ist, die etwas wie eine elektrischen Schaltung darstellen, wird Problem des minimalen Spannbaumes genannt; das zweite, das offenbar für Graphen nützlich ist, die etwas wie eine Streckenkarte von Fluglinien darstellen, wird Problem des kürzesten Pfades genannt. Diese Probleme sind für eine Vielzahl von Problemen repräsentativ, die im Zusammenhang mit gewichteten Graphen entstehen.

Unsere Algorithmen erfordern ein Durchsuchen des Graphen, und manchmal wird unsere Vorstellung dadurch unterstützt, daß wir uns die Gewichte als Abstände vorstellen; wir sprechen von dem »nächsten Knoten von x« usw. Tatsächlich ist diese Interpretration in der Nomenklatur für das Problem des kürzesten Pfades enthalten. Dennoch ist es wichtig, sich daran zu erinnern, daß die Gewichte keineswegs einem Abstand entsprechen müssen; sie könnten Zeit oder Kosten oder etwas anderes, völlig davon verschiedenes darstellen. Wenn die Gewichte tatsächlich Abstände darstellen, sind möglicherweise andere Algorithmen geeignet. Auf diese Frage gehen wir am Ende dieses Kapitels noch ausführlicher ein.

Abbildung 31.1 zeigt ein Beispiel eines gewichteten ungerichteten Graphen. Es ist offensichtlich, wie gewichtete Graphen dargestellt werden können: Bei der Darstellung mittels einer Adjazenzmatrix kann die Matrix anstelle boolescher Werte Kantengewichte enthalten, und bei der Darstellung mittels einer Adjazenzstruktur kann zu jedem Element der Liste (das eine Kante darstellt) ein Feld für das Gewicht hinzugefügt werden. Wir setzen voraus, daß alle Gewichte positiv sind. Manche Algorithmen können an die Behandlung negativer Gewichte angepaßt werden, doch sie werden dann um einiges komplizierter. In anderen Fällen verändern negative Gewichte die Natur des Problems in grundlegender Weise und erfordern Algorithmen, die erheblich ausgeklügelter sind als die hier betrachteten. Als Beispiel für möglicherweise auftretende Schwierigkeiten betrachte man die Situation, daß die Summe der Gewichte der Kanten entlang eines Zyklus negativ ist: Durch einfaches wiederholtes Durchlaufen des Zyklus könnte ein unendlich kurzer Weg erzeugt werden.

Abbildung 31.1
Abbildung 31.1 Ein gewichteter ungerichteter Graph.

Für die Probleme des minimalen Spannbaumes und des kürzesten Weges sind verschiedene »klassische« Algorithmen entwickelt worden. Diese Verfahren gehören zu den bekanntesten und am häufigsten verwendeten Algorithmen in diesem Buch. Wie wir schon früher bei der Untersuchung von seit langem bekannten Algorithmen gesehen haben, liefern die klassischen Verfahren einen allgemeinen Zugang, doch moderne Datenstrukturen helfen bei der Erstellung kompakter und effizienter Implementationen. Im vorliegenden Kapitel werden wir sehen, wie für eine Verallgemeinerung der Methoden für das Traversieren von Graphen aus Kapitel 29 Prioritätswarteschlangen benutzt werden können, um beide Probleme für lichte Graphen effizient zu lösen; wir untersuchen die Beziehung zwischen diesen Methoden und den klassischen Verfahren für dichte Graphen, und wir betrachten ein Verfahren für das Problem des minimalen Spannbaumes, das einen vollständig anderen Ansatz verwendet.


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