OR

Ein Weg ist in einem gerichteten Graph eine Kette, wobei die Pfeile nur in eine Richtung zeigen

> in einem ungerichteten Graphen heisst eine Kette Kreis, wenn gilt io = it

> in einem gerichteten Graphen heisst ein Weg mit io = it Zyklus 

> Baum: Baum in G ist ein zusammenhängender, ungerichteter, zyklusloser Graph 

> Wald: ungerichteter kreisloser Graph, seine Komponenten sind Bäume 

• beginne beim Knoten welcher kein Vorgänger hat 
• wähle den nächsten Knoten indem l_v maximiert wird 
• fahre so fort 
• sucht den längsten Weg von einer Quelle s zu allen anderen Knoten im gerichtetem Graphen

Ein Gerüst in G ist ein Baum in G, welcher alle Knoten von G umfasst 

> sucht die kürzesten Wege von Knoten s zu allen anderen Knoten im gerichtetem/ungerichtetem Graphen "one to all"

> alle Längen der Kanten sind nichtnegativ 

> Zyklen sind zulässig, aber Zyklen negativer Länge dürfen nicht auftreten

> da keine negativ bewerten Kanten im Graphen vorkommen dürfen 

• Menge A der Knoten, zu denen bereits kürzester Weg von der Quelle S bekannt ist 
• Menge B der Knoten, zu denen Wege von s aus bekannt sind, jedoch nicht sicher ist, ob diese minimal sind 
• Menge C der Knoten, zu denen noch kein Wege von s aus bekannt sind 

• sortiere Kanten nach aufsteigenden Gewichten 
• markiere diese Kanten rot 
• es dürfen keine Zyklen entstehen 
• alle Orte müssen besucht werden und es muss eine verbindung zwischen den Punkten bestehen