Die Themen des Artikels im Einzelnen:<\/p>\n\n\n\n
- \n
- Schritt-f\u00fcr-Schritt-Beispiel zur Erkl\u00e4rung der Funktionsweise des Algorithmus<\/li>\n\n\n\n
- Quellcode des Dijkstra-Algorithmus (mit
PriorityQueue<\/code>)<\/li>\n\n\n\n- Bestimmung der Zeitkomplexit\u00e4t des Algorithmus<\/li>\n\n\n\n
- Messung der Laufzeit \u2013 mit
PriorityQueue<\/code>,TreeSet<\/code> undFibonacciHeap<\/code><\/li>\n<\/ul>\n\n\n\nFangen wir an mit dem Beispiel!<\/p>\n\n\n\n
Dijkstras Algorithmus \u2013 Beispiel<\/h2>\n\n\n\n
Den Dijkstra-Algorithmus erkl\u00e4rt man am besten an einem Beispiel. Die folgende Grafik zeigt eine fiktive Stra\u00dfenkarte. Orte werden durch Kreise mit Buchstaben dargestellt; die Linien sind Stra\u00dfen und Wege, die diese Orte verbinden.<\/p>\n\n\n
\n![\"Dijkstras](\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x.png\")
Stra\u00dfenkarte<\/figcaption><\/figure>\n<\/div>\n\n\n Die dicken Linien stellen eine Schnellstra\u00dfe dar; die etwas d\u00fcnneren Linien sind die Landstra\u00dfen, und die gestrichelten Linien sind schwer passierbare Feldwege.<\/p>\n\n\n\n
Die Stra\u00dfenkarte bilden wir nun auf einen Graphen ab. D\u00f6rfer werden dabei zu Knoten, Stra\u00dfen und Wege werden zu Kanten.<\/p>\n\n\n