Hallo,
der Lee-Algorithmus findet unter gegebener Situation die kürzeste Verbindung zwischen zwei Punkten. Was der Algorithmus aber nicht kann, ist das globale Minimum bei der Verdrahtung mehrerer Netze zu finden (siehe Übung). Die Aussage der Optimalität bezieht sich also nur auf die Situation der Verdrahtung zweier Punkte.
Oder anders: Eine Chipfläche, mehrere Netze. wird das erste Netz berechnet, findet Lee die optimale (kostengünstigste) Verbindung. Für das nächste Netz wird nun die erste Verdrahtung als Hindernis angesehen. Mit dieser zusätzlichen Bedingung findet Lee auch für das zweite Netz wieder die kürzeste Verbindung, usw. usf. Dass heißt aber nicht, dass die zweite (dritte, vierte) Verbindung auch dann die kürzeste gewesen wäre, wenn dieses zweite (dritte, vierte) Netz als erstes geroutet worden wäre.
Alles klar?
Grüße,
Martin
