Dijkstra Algorithmus implementieren, Priority Queue nach den geringsten Kosten in der Queue sortieren?
Also ich möchte meine queue so sortieren, dass die Kosten der Knoten die in der Queue sind, aufsteigend sind. meine Klasse Node implementiert Comparable<Node>,dadurch wäre man in der Lage nach kosten zu vergleichen, aber nicht gleich zu sortieren,
so und meine Frage wäre jetzt wie ich die elemente innerhalb der Queue sortiere, denn was ich grad nur versuche ist das Element mit den geringsten Kost en zu ermitteln und das dann auf nen Node abspeichern, aber ich denke das ha t den sinn der priority queue verfehlt
private static Node decideNextMarked(PriorityQueue<Node> queue) {
Node bestOption = null;
if (queue.size() > 1) {
for (Node possibleCandidate : queue) {
for (Node comparison : queue) {
switch (possibleCandidate.compareTo(comparison)) {
case -1:
bestOption = possibleCandidate;
case 1:
bestOption = comparison;
case 0:
}
}
}
}
return bestOption;
}
was ich noch mache ist beim einfügen der Kosten in das int[] distance, die Nodes der queue hinzufügen die in der unvisited (ArrayList<Node>) drin sind
1 Antwort
Eine PriorityQueue ist eigentlich von sich aus bereits sortiert, und nicht einfach eine Sammlung von gewichteten Objekten. Die Sortierung kann beim Einfügen oder auch beim Auslesen passieren.
Ist das deine eigene PriorityQueue-Klasse oder woher kommt die? Wenn es die aus dem JDK ist, solltest du dir die Javadocs anschauen. Man kann im Konstruktor einen Comparator angeben, wenn einem die natürliche Ordnung nicht gefällt. Ansonsten könntest du deine Nodes auch Comparable implementieren lassen.
Dann verstehe ich das Problem aber nicht. Die PriorityQueue ist sortiert, und du bekommst das niederwertigste Element mit PriorityQueue#poll() (oder PriorityQueue#peek(), wenn du es nicht automatisch entfernen möchtest). Das steht alles in den oben verlinkten Javadocs
ich wusste nicht genau woher die queue wissen will, ob ich eine ascending order oder descending order haben will..., naja ich bin jz so mehr oder weniger damit durch , hab nen großteil fertig, aber es gab da ne winzige sache der nen fehler verursacht, hab ich zum teil gefunden aber nicht die lösung dazu... naja ist jz abgegeben die HA
das ist in der Node Klasse drin