die laufzeit einer rekrusiven methode fixen

[unknown]

eigendlich müsste das in O(T+nachfolger.size()) = O(nachfolger.size()) laufen,

Wie kommst du darauf?
Alleine
for(int n=0;n<nachfolger.size();n++)//alle in der naechsten zeiteinheit zu erreichende
{
  if(map.containsKey(nachfolger.get(n).id))
ist eine Schleife über nachfolger.size() Elemente. map.containsKey ist eine weitere Suche. nachfolger.get auch nochmal (wobei ich nicht weiß, was in Java eine ArrayList ist, könnte also auch nur ein indizierter Zugriff sein).
Und das geht dann so weiter.

Wenn dir dass auf einen Rutsch zu lange dauert, versuche es aufzuteilen, wenn es geht. Also beim Einfügen eines Knoten diesen an allen Anderen mit seinem Gewicht vermerken. Das macht natürlich nur Sinn, wenn die Knoten nicht am Stück eingelesen werden.
Oder mache es nach Bedarf. Wenn du die Werte zu einem Knoten benötigst, sieh nach ob der Knoten mit Gewicht vorhanden ist, dann nimm diese Daten, sonst berechne sie und trage sie ein.