Membervariablen für PriorityQueue vergleichen?

[hawkeye78]

Hallo,

da ich in ein paar Wochen eine Klausur über Algorithmen und Datenstrukturen schreiben muß habe ich mich gestern daran versucht den Algorithmen von Dijkstra zu implementieren....und bin daran ziemlich erfolgreich gescheitert.

Ich hatte gestern in erster Linie das Problem gehabt das die gefundenen Knoten laut Algorithmusbeschreibung in einer Prioritäts-Warteschlange abgelegt werden sollen. Dazu hatte ich mir nun überlegt das ich eine Klasse anlege die nur die Variablen "Quellknoten", "Zielknoten" sowie "Kosten" enthält (sowie die entsprechenden setter- und getter-Methoden).

Da Java glücklicherweise bereits die Datenstruktur PriorityQueue zur Verfügung stellt wollte ich diese eigentlich nutzen, was für mich zu dem Problem führt das ich nicht weiß wie ich Java beibringen kann die Objekte nach ihren Kosten in die Queue einzusortieren. Ich hatte bereits gelesen das für die Vergleiche die Objekte Comparable sein müssen, aber wie bringe ich nun Java dazu die Knoten anhand ihrer Kosten zu vergleichen? (vielleicht kann mir ja jemand ein minimales beispiel dafür zeigen?)
Ich hoffe ich konnte einigermaßen logisch erklären was mein Problem ist. Kurz zusammen gefaßt möchte ich Objete in eine PriorityQueue einsortieren und dieses anhand einer Variable.

Ich hatte mir zwar bereits überlegt meine eiene Queue zu schreiben aber ich möchte gerne das programm nicht weiter aufblähen als umbedingt nötig und wäre daher über eine entsprechende Antwort sehr dankbar.
viele Grüsse
Dan

 

[@x.l]

Du schreibst dir eine Klasse Knoten, welche die Schnittstelle Comparable implementiert. Die compareTo() musst du dann so schreiben, dass die Knoten anhand der Kosten verglichen werden.

public class Knoten implements Comparable {
    
    double kosten;
    
    public int compareTo(Knoten k) {
        int result = -1;
        if(k.kosten < kosten)
            result = -1
        else if(k.kosten == kosten)
            result = 0;
        else
            result = 1;
        return result;
    }
}

So in der Art....

 

[Kim Stebel]

ein bisschen weniger umständlich...

public class Knoten implements Comparable { 
    
    double kosten; 
    
    public int compareTo(Knoten k) { 
        if(k.kosten < kosten) 
           return -1 
        if (k.kosten == kosten) 
            return 0; 
        return 1; 
    } 
}

 

[@x.l]

ein bisschen weniger umständlich...

hängt ganz davon ab, wieviele "return" statements man in seinem Code haben möchte. Das ist halt Geschmackssache...

 

[Beni]

ein bisschen korrekter... :bae: (Generics habt ihr vergessen :wink: )

public class Knoten implements Comparable<Knoten> { 
    
    double kosten; 
    
    public int compareTo(Knoten k) { 
        if(k.kosten < kosten) 
           return -1 
        if (k.kosten == kosten) 
            return 0; 
        return 1; 
    } 
}

 

[@x.l]

ein bisschen korrekter... :bae: (Generics habt ihr vergessen :wink: )

der lachende dritte... 🙂

 

[hawkeye78]

Hallo euch,

vielen Dank für die Antworten, ich denke das sollte ich jetzt hinbekommen 🙂. Ich hätte allerdings noch eine Frage zum eigentlichen Einfügen. Ist es ausreichend wenn ich die Objekte erzeuge und dann einfüge oder muß ich die compareTo Methode noch einmal explizit aufrufen? Nach meinem Verständnis würde ich es im moment so implementieren

class Dijkstra
{
	public static void main(String args[])
	{
		PriorityQueue q=new PriorityQueue();
		Knoten k1=new Knoten(1,2,4);
		q.insert(k1);

		Knoten k2=new Knoten(3,5,7);
		q.insert(k2);

		Knoten k3=new Knoten(4,6,3);
		q.insert(k3);		
	}
}

 

[Beni]

Die compareTo-Methode wird von der Queue aufgerufen, da musst du garnichts mehr machen (ausser implementieren). Der ganze Witz an diesen Interfaces ist ja, dass man sie implementiert, und jemand anderen dann die Arbeit machen lässt.