Nächste Seite: Dijkstra-Beweis Aufwärts: Hauptseite Algorithmen Vorherige Seite: Weitere Sortierverfahren Inhalt
Graphen - Tiefensuche/Breitensuche
Tiefensuche läuft mit einem Stack, die Breitensuche mit einer Queue. Sie laufen mit einer Laufzeit
, weil jeder Knoten einmal auf den Speicher gelegt wird und jede Kante inspiziert wird. Mittels Breitensuche lassen sich kürzeste Wege ermitteln, wobei das Kostenmaß der Kanten uniform, d.h
ist, indem man für jeden unbesuchten Knoten, den man in die Queue einreiht die Kosten des Vorgängers um 
erhöht und in den Knoten schreibt. Die Kosten kann man in einer Matrix ablegen.
Kosten für längste Wege lassen sich erzeugen, indem man die Kosten negiert und eine Algorithmus verwendet, der die kürzesten Wege berechnet.