Dijkstra priority-queues |
| 05.03.2010, 22:26 | plizzz | Auf diesen Beitrag antworten » |
| Dijkstra priority-queues ich möchte einen Dijkstra-Algorithmus implementieren und der soll möglichst schnell sein. Zur Übung habe ich erstmal eine verkettete Liste zur Implementierung benutzt und wollte mich jetzt an die Heaps wagen. Generell gilt für die Laufzeiten wohl (n Anzahl Knoten, m Anzahl Kanten): lineare Liste: O(n^2) Binärheap: O((m+n)*log(n)) Fibonacci-Heaps: O(n*log(n)) (amortisiert) Demnach ist zumindest asymptotisch für den uneingeschränkten Fall die Variante mit den Fibonacci-Heaps wohl die beste Wahl. Die Graphen, auf denen ich den Algorithmus laufen lassen will, haben allerdings die Eigenschaft, dass jeder Knoten Grad <=4 hat, womit die beiden Heaps asymptotisch gleich wären. Kann man für diese Gruppe von Graphen nun trotzdem erwarten, dass im Endeffekt die Fibonacci-Heaps schneller sind oder könnte es eventuell sogar so sein, dass ein Binärheap dann besser ist bzw. wovon hängt das ab? Habe da eine Weile drüber nachgedacht, aber kam zu keinem Ergebnis. Wäre cool, wenn jemand dazu etwas weißt. MfG plizzz |
||
| 05.03.2010, 22:56 | kiste | Auf diesen Beitrag antworten » |
Ich hab jetzt die Methoden vom Fib-Heap nicht mehr Kopf. Aber allgemein wird es von den Konstanten die sich im O(...) verstecken und der Implementierung abhängen. Wenn du genug Zeit hast implementiere einfach beide und teste was schneller ist |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
