R2 Wegeprobleme
Längste Wege
Längste Wege im Graphen
Der Dijkstra-Algorithmus in der beschriebenen Form eignet sich nur zum Auffinden des kürzesten Weges. Hier wird ein Vorgehen zum Auffinden des längsten Weges vorgestellt. Längste Wege spielen bei der Planung von Abläufen und Projekten eine Rolle. In diesem Bereich wurde die Netzplantechnik entwickelt. Netzpläne sind Graphen, die noch mit einer Reihe von zusätzlichen für die Projektplanung hilfreichen Informationen angereichert sind.
Längste Wege in der Projektplanung
Die Aussage, dass längste Wege bei der Projektplanung eine Rolle spielen, klingt vielleicht zunächst überraschend, schließlich sollen Projekte ja möglichst schnell zum Ziel kommen. Aber genau dafür ist es wichtig, den längsten Weg zu kennen, der in der Projektplanung kritischer Pfad genannt wird. Typisch für ein Projekt ist, dass für das Beginnen eines Vorgangs oft mehrere andere Vorgänge abgeschlossen sein müssen. Und die Kette von Vorgängen, die am längsten braucht, ist entscheidend für das Gesamtprojekt. Ist dieser kritische Pfad bekannt, kann er besonders beobachtet werden, damit sichergestellt ist, dass keine Verzögerungen auftreten, die das gesamte Projekt verlängern.
In einer Wohngemeinschaft wird spontan beschlossen, ein kleines Kaffeekränzchen zu organisieren, nach Meinung der Mitglieder gehören dazu ein Kuchen mit Schokoglasur und eine Flasche gut temperierter Sekt, ein bisschen Luxus muss sein. Beides soll zu Beginn auf dem Tisch stehen. Es ist noch eine Backmischung für den Teig im Schrank, allerdings fehlen die Glasur und der Sekt. Helfende Hände gibt es genug und die Küche ist auch groß genug. Wie lange dauert es, bis das Kaffeekränzchen frühestens beginnen kann?
Folgende Vorgänge gibt es:
- V1: Einkaufen von Glasur und Sekt (30 min, kann jederzeit starten)
- V2: Sekt kaltstellen (60 min, kann nach V1 starten)
- V3: Vorheizen Backofen (10 min, kann jederzeit starten)
- V4: Zusammenrühren des Teigs (20min, kann jederzeit starten)
- V5: Backen des Kuchens (60 min, kann nach V3 und V4 starten)
- V6: Erhitzen der Glasur (10 min, kann nach V1 starten)
- V7: Übergießen des Kuchens mit der Glasur und kurz Abkühlen (20min, nach V5 und V6)
- V8: Beginn der Party (0 min, nach V2 und V7)
Die Startzeitpunkte jedes Vorgangs sind in Abb. 2-9a als Knoten eingezeichnet, die ausgehenden Pfeile mit der Dauer des Vorgangs. Ist eine Vorgang Voraussetzung für das Beginnen mehrerer Folgevorgänge, sind mehrere ausgehende Pfeile mit der gleichen Kantengewichtung eingezeichnet.
Hinweis:
Die vorstehende Darstellung konzentriert sich auf den graphentheoretischen Kern des Problems und eignet sich, um die Zeiten zu berechnen. Sie weicht von den Darstellungsformen gängiger Methoden der Netzplantechnik wie CPM und MPM ab.
Ermittlung des längsten Weges
Nachfolgend wird ein Algorithmus vorgestellt, der in einem gerichteten, kreisfreien Graphen angewendet werden kann. Das ist nicht einschränkend, da in anderen Fällen die Frage nach dem längsten Weg nicht sonderlich sinnvoll ist. In einem ungerichteten Graphen ist es zum Beispiel möglich, eine Kante hin- und her zu benutzen und den Weg beliebig zu verlängern. Im gerichteten Graphen mit einem Kreis führt der längste Weg unendlich Mal durch den Kreis.
Dieser wird anhand des Beispiels aus Abb 2.9a vorgestellt.
Initialisierung:
Der Startknoten V0 wird endgültig markiert.
Alle Knoten erhalten die Markierung 0.
Der Startknoten ist der Arbeitsknoten.
Iteration 1
Schritt 1:
Alle vom Arbeitsknoten ausgehenden Kanten werden markiert.
Schritt 2:Für alle über diese Kanten erreichten Knoten wird geprüft, ob sich durch Nutzung der Kante der Weg verlängert, oder anders ausgedrückt: si+cij >sj ? Verlängert sich der Weg, wird die alte Markierung am Knoten durch si+cij ersetzt.
Da vom Startknoten aus alle Kantengewichte 0 sind, ist dies bei allen Knoten der Fall.
Schritt 3:
Es wird ein Knoten gewählt, bei dem alle eingehenden Kanten markiert sind. Es wird im Beispiel V1 als neuer Arbeitsknoten gewählt, V3 oder V4 könnten aber auch gewählt werden.
Iteration 2
Schritt 1:
Die beiden vom Arbeitsknoten V1 ausgehenden Kanten zu V2 und V6 werden markiert.
Schritt 2:
Es wird si+cij > sj geprüft. Ist dies zutreffend, wird die Markierung von j auf si+cij gesetzt, ansonsten bleibt sie erhalten.
Für V2: 0+30>0, die Markierung von V2 wird auf 30 gesetzt.
Für V6: 0+30>0, die Markierung von V6 wird auf 30 gesetzt.
Schritt 3:
Es gibt einige Knoten, bei denen alle eingehenden Kanten markiert sind. Im Beispiel wird V2 als neuer Arbeitsknoten gewählt.
Iteration 3
Schritt 1:
Die ausgehende Kante zu Knoten V8 wird markiert.
Schritt 2:
30+60>0, die Markierung von V8 wird auf 30+60=90 gesetzt.
Schritt 3:
Es können V3, V4 und V6 als neue Arbeitsknoten gewählt werden.
Im Beispiel wird V3 als neuer Arbeitsknoten gewählt
Iteration 4
Schritt 1:
Die ausgehende Kante zu Knoten V5 wird markiert.
Schritt 2:
0+10>0? Ja, V5 erhält die Markierung 10.
Schritt 3:
Es wird V4 gewählt.
Iteration 5
Schritt 1:
Die ausgehende Kante zu Knoten V5 wird markiert.
Schritt 2:
0+20>10? Ja, V5 erhält die Markierung 20.
Diesmal wurde es tatsächlich etwas spannender, weil ja schon in der 4. Iteration der Knoten markiert wurde. Diese Markierung wurde nun ersetzt.
Schritt 3:
Es wird V5 gewählt.
Iteration 6
Schritt 1:
Kante zu V7 markieren
Schritt 2:
20+60>0, Markierung von V7 auf 80 setzten
Schritt 3:
V6!
Iteration 7
Schritt 1:
Kante zu V7 markieren.
Schritt 2:
30+10>80 ? Nein! Die alte Markierung 80 bleibt erhalten.
Schritt 3:
V7
Iteration 8
Schritt 1:
Kante zu V8, dem Zielknoten, markieren.
Schritt 2:
80+20>90? Ja, die Markierung von V8 wird auf 100 gesetzt.
Schritt 3:
Der Zielknoten V8 wird als Arbeitsknoten gewählt, das Verfahren endet erfolgreich.
Der längste Weg: V0-V4-V5-V7-V8, mit einer Länge von 100 min
Das Kaffeekränzchen kann frühestens nach 100 min anfangen, auf dem kritischen Pfad liegen die Vorgänge „Zusammenrühren des Teigs“, „Backen des Kuchens“ und „Übergießen des Kuchens mit der Glasur und kurz Abkühlen“. Eine Verzögerung bei einem dieser Vorgänge führt dazu, dass der Kaffeeklatsch erst später beginnen kann.
