prev up inhalt next


6.5 Pert

Eine weitere Anwendung von kürzeste Wege Berechnungen ergibt sich durch die sog. PERT (program evaluation review technique). Bei diesen Problemen hat man es mit azyklischen, gerichteten und bewerteten Graphen G zu tun. Diese Graphen veranschaulichen Produktionsabläufe, wie z.B. das Erstellen von Häusern etc. Die Kanten von G stellen dabei bestimmte Tasks also Teilproduktionen dar, die Länge der Kanten modelliert die benötigte Zeit für diese Task.


Beispiel:



Gesucht ist in einem solchen PERT-Graphen nun der längste Weg vom Startknoten zum Zielknoten. Dessen Länge entspricht dann nämlich der benötigten Gesamtproduktionszeit.

Der Algorithmus, der dieses berechnet, lautet:


     REPEAT
          finde Knoten y, dessen sämtliche Vorgänger markiert sind.
          markiere y mit m[y]:=max{m[x]+c(x,y)|x ist Vorgänger von y}
     UNTIL Zielknoten ist markiert

Die Implementation basiert auf der Idee, sich eine Schlange s mit Knoten, deren sämtliche Vorgänger markiert sind, zu halten. Initial ist die Quelle das einzige Element der Schlange s .


     WHILE NOT emptyqueue(s) DO
          x := dequeue(s);
          WHILE NOT endpos(g[x]) DO
               y := elem(g[x]);
               m[y] := max m[y], m[x]+c(x,y);
               indegree[y] := indegree[y]-1;
               IF indegree[y] = 0 THEN enqueue (s, y) END;
               advance (g[x]);
          END;
     END;

Die Gesamtlaufzeit dieses Algorithmus liegt in O(|E|) , denn auch die Initialisierung des indegree-Arrays läßt sich mit Hilfe der Adjazenzliste in O(|E|) durchführen.


prev up inhalt next