Projekt:Mathematik in Natur und Technik/dijkstra/Prioritätsschlange

Prioriätsschlange

Die Prioritätsschlange gewährleistet, dass der Knoten aus der Front genommen wird, der den kleinsten Wert enthält. Diese Prioritätsschlange sortiert die Knoten nach ihren Werten. Man kann sich dies als einen Stammbaum vorstellen. Kommt ein neuer Wert (also ein neuer Knoten) zur Front hinzu, wird dieser in eine bestimmte Reihe eingegliedert. Ist der Vorgänger in dieser Reihe größer, so tauschen diese zwei Werte ihren Platz. Dies geschieht so oft bis der Wert, der vor dem neuen Wert ist, kleiner ist. Dann wird der Knoten genommen, der in der Reihe ganz oben steht, die Nachbarknoten bestimmt und aus der Reihe gelöscht. Der "Stammbaum" wird neu gegliedert.