Kommentare zu: Dijkstra-Algorithmus (mit Java-Beispiel) https://www.happycoders.eu/de/algorithmen/dijkstra-algorithmus-java/ Fri, 02 May 2025 07:55:58 +0000 hourly 1 Von: Sven Woltmann https://www.happycoders.eu/de/algorithmen/dijkstra-algorithmus-java/#comment-16441 Sat, 17 Apr 2021 12:32:07 +0000 https://www.happycoders.eu/?p=16720#comment-16441 Als Antwort auf MissingDecreaseKeyInJavaPriorityQueue.

Hallo, der Artikel schlägt sowohl das TreeSet als auch den FibonacciHeap (ein Min-Heap) als mögliche O(log(n))-Alternativen zur eingebauten PriorityQueue mit vor und zeigt im letzten Kapitel eine Übersicht der jeweiligen Zeitkomplexitäten.

]]> Von: MissingDecreaseKeyInJavaPriorityQueue https://www.happycoders.eu/de/algorithmen/dijkstra-algorithmus-java/#comment-16440 Sat, 17 Apr 2021 08:58:14 +0000 https://www.happycoders.eu/?p=16720#comment-16440 Ich denke man sollte erwähnen, dass man Priority Queues durch Min-Heaps mit einer O(log(n)) Methode 'decrease-key' implementieren kann. Diese Methode kann dann im Dijkstra Algorithmus anstelle von remove/add verwendet werden. Es liegt nur an Javas Implementierung, dass die Priority Queue hier so schlecht abschneidet, da man auf den Workaround remove/add zurückgreift. Siehe z.B. das Buch "Introduction to Algorithms" von Cormen/Leiserson/Rivest/Stein. Dies wurde auch ausführlich auf stackoverflow.com diskutiert: siehe die Antworten https://stackoverflow.com/questions/6267172/which-datatype-to-use-as-queue-in-dijkstras-algorithm/6267630#6267630 und https://stackoverflow.com/questions/6267172/which-datatype-to-use-as-queue-in-dijkstras-algorithm/42443252#42443252.

]]>