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

Answer 1

[Seliba]

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.

Woher ich das weiß: Studium / Ausbildung – Informatikstudent

Comments

[Niinbo]

und die PriorityQueue ist aus der JDK

[Niinbo]

@Override
 public int compareTo(Node o) {
    return Integer.compare(this.cost, o.cost);

}

das ist in der Node Klasse drin

[Seliba]

@Niinbo

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

[Niinbo]

@Seliba

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

[Seliba]

@Niinbo

Das weiß sie, weil die Elemente (Node) Comparable#compareTo() implementiert. Darüber ist die Reihenfolge festgelegt