- zu jedem Zeitpunkt
sind Knoten in
U V schon behandelt
(es ist ein MST für U bekannt)
- für die Knoten aus
V U verwaltet man
eine geeignete Kostenschätzung.
- man fügt einen geeigneten Knoten zu U hinzu
(durch eine geeignete Kante zwischen U und
V U.
- das erfordert eine Anpassung der geschätzten Kosten.
Vergleiche mit Algorithms von Dijkstra
für kürzeste Wege.
Johannes Waldmann
2005-01-25