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.