Sortierte Liste / Map

[mikemodanoxxx]

Hallo,

ich bin gerade dabei einen Dijkstra-Algorithmus zu implentieren. Funktioniert auch schon alles wunderbar, jetzt will ich aber den Code noch etwas optimieren und verschönern.

Momentan habe ich in einer Klasse eine HashMap<String, Node>, die alle Knoten enthält.

Da der Dijkstra ja eine Prioritätswarteschlange benutzt, würde ich auch gerne eine solche implementieren. Wie kann ich also meine Datenstruktur am besten sortieren (die Kosten d sind in der Klasse Node gespeichert und über getD() erreichbar. Nach denen würde ich gerne sortieren)?

Momentan rufe ich halt eine Funktion extractMin auf, die alle Kanten nach dem kürzesten Pfad durchsucht und diesen Knoten dann zurück gibt. Das ist natürlich nicht sehr schön und effizient. Ich hätte am liebsten eine sortierte Liste/Map bei der ich dann einfach pop() machen kann und bekomme das niedrigste Element.

Muss ich über das keySet sortieren, oder sollte ich generell eine andere Datenstrukur als die HashMap benutzen?

ciao, Mike.

 

[SlaterB]

auf
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
kann man bei jedem Schritt lesen
> Neusortieren der Prioritätswarteschlange Q (1. Mannheim, 2. Kassel, 3. Würzburg, ...)

da gibts also pro Schritt eine Liste mit Nodes, die neu sortiert wird,
sowas muss du auch haben, eine einfache Liste,
fertige Nodes entfernen (oder d=0),
sortieren mit einem Compartor oder Comparable,

nach jedem Durchgang müssen alle zum zuletzt gewählen Knoten benachbarten Knoten neu bewertet werden,
dann dürfte die Liste leicht unsortiert sein,
ein sort() bereinigt das,
ob die allgemeine Collections.sort() (MergeSort) besonders effizient ist für nur leicht geänderte Liste kann ich gerade nicht automatisch erinnern,
dürfte aber für den Gesamtalgorithmus irrelevant sein

 

[Grasstampfer]

nutz doch einfach http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

 

[SlaterB]

funktioniert die auch wenn man die Objekte darin ändert? nachträglich sortieren scheint es nicht zu geben

dann eben die fraglichen Objekte herausnehmen und neu einfügen

 

[mikemodanoxxx]

oh cool priorityqueue war mir neu.

Wie implementiere ich jetzt meine Sortierung? Also wie sage ich dem comparator, nach welchen Gesichtspunkten er zwei Elemente vergleichen soll?

ciao, Mike.

 

[SlaterB]

indem du ganz normal einen Comparator baust, Lehrbuch?

http://www.galileocomputing.de/open...12_004.htm#mjaf8d671aa3283d042df48c24f0c0c87b
12.4 Vergleichen von Objekten

 

[mikemodanoxxx]

Hm ich habe jetzt aus meiner Klasse Node ein Node implements Comparator gemacht und die Methode implementiert.

Bei PriorityQueue<Node> q2 = new PriorityQueue<Node>();

q2.addAll(graph.values());

erhalte ich nun eine ClassCastException, Node cannot be cast to java.lang.comparable

Was habe ich falsch gemacht?

edit: mit comparable gehts

 

[Gelöschtes Mitglied 5909]

Du hast die beiträge oben nicht gelesen

Node implements Comparator<Node>

 

[Marco13]

Nicht
Node implements Comparator
sondern
Node implements Comprable<Node>