Dijkstra-Algorithmus kürzeste Wege

Was ist der Dijkstra-Algorithmus?

Ein Algorithmus zur Bestimmung der kürzesten Wege in einem Graphen mit nicht-negativen Kantengewichten.

Kernidee des Dijkstra-Algorithmus?

Iterative Auswahl des nächsten Knotens mit dem minimalen Abstand. - Minimale Distanz aktualisieren - Nachbarn betrachten

Was wird beim Dijkstra-Algorithmus verwendet?

Eine Prioritätswarteschlange, um den Knoten mit der geringsten Entfernung effizient zu finden.

Dijkstra-Algorithmus: Eingangsparameter?

Ein startender Knoten und ein Graph, der aus Knoten und Kanten besteht.

Wie funktioniert der Dijkstra-Algorithmus?

1. Initialisieren der Abstände. 2. Knoten mit minimalem Abstand auswählen. 3. Abstände der Nachbarn aktualisieren. 4. Wiederholen.

Wahr oder falsch: Dijkstra kann negative Kanten verwenden.

Falsch. Dijkstra funktioniert nur mit nicht-negativen Kantengewichten.

Was aktualisiert der Dijkstra-Algorithmus?

Die kürzesten Abstände zu jedem Knoten, wenn ein kürzerer Weg gefunden wird.

Was ist der Startknoten?

Der Knoten, von dem aus die Berechnung der kürzesten Wege beginnt.

Wie wird der minimale Abstand ausgewählt?

Durch die Verwendung einer Prioritätswarteschlange (z.B. Min-Heap), die effizient den Knoten mit dem minimalen Abstand liefert.

Ziel des Dijkstra-Algorithmus?

Den kürzesten Weg von einem Startknoten zu allen anderen Knoten im Graphen zu finden.

Dijkstra-Algorithmus: Zeitkomplexität?

Mit einer Prioritätswarteschlange: $\displaystyle O((V + E) imes ext{log}(V))$, wobei V die Knoten und E die Kanten sind.

Was passiert, wenn man einen besuchten Knoten erneut wählt?

Es hat keinen Effekt, da der kürzeste Weg bereits gefunden wurde.

Gibt es einen Unterschied zwischen Dijkstra und BFS?

Ja, BFS findet nur kürzeste Wege in ungewichteten Graphen, Dijkstra in gewichteten Graphen (nicht-negativ).

Wie wird der Algorithmus beendet?

Wenn alle Knoten besucht sind oder die minimale Distanz zu allen Knoten bestimmt wurde.

Was ist ein Beispiel für eine Anwendung?

Routenplanung, um den kürzesten Weg zwischen zwei Städten zu finden, z.B. von Berlin nach München.

Schritt 1 in Dijkstra?

Initialisierung: Setze den Abstand des Startknotens auf 0, alle anderen auf unendlich.

Anwendungsbeispiel Dijkstra-Algorithmus?

Routenplanung in Navigationssystemen, z.B. Google Maps. Berechnung der kürzesten Strecke zwischen zwei Punkten.

Laufzeit des Dijkstra-Algorithmus?

Die Laufzeit ist abhängig von der Implementierung: - Mit Array: O(V²) - Mit Min-Heap: O(E + V log V)

Raumkomplexität des Dijkstra-Algorithmus?

O(V) für die Speicherung von Entfernungen und Vorgängern.

Wahr oder Falsch: Dijkstra findet auch negative Gewichtungen.

Falsch. Der Dijkstra-Algorithmus funktioniert nicht korrekt mit negativen Kanten.

Einsatzgebiet Dijkstra-Algorithmus?

Telekommunikationsnetzwerke, Verkehrsnetzwerke, Logistik, Robotik - überall, wo optimale Pfade nötig sind.

Was ist ein Beispiel für eine Eingabe?

Ein Graph mit Städten als Knoten und Straßen als Kanten mit jeweiligen Entfernungen in Kilometern.

Dijkstra vs. Bellman-Ford?

Dijkstra: schnell für positive Gewichte. Bellman-Ford: unterstützt negative Gewichte, ist jedoch langsamer bei O(VE).

Wie viele Iterationen braucht Dijkstra?

Maximal V Iterationen, wobei V die Anzahl der Knoten im Graphen ist.

Fill in the blank: Dijkstra verwendet _______ zur Auswahl des nächsten Knotens.

eine Prioritätswarteschlange (Min-Heap).

Anwendungsbeispiel im Alltag?

Planung der kürzesten Route zum nächsten Supermarkt in einer Stadt mit Straßen als Kanten.

Komplexität bei vollständigen Graphen?

O(V²) bei Verwendung eines Arrays, da alle Kanten betrachtet werden müssen.

Wahr oder Falsch: Dijkstra findet immer die optimale Lösung.

Wahr, solange alle Kanten nicht negativ sind.

Dijkstra vs. Bellman-Ford: Hauptunterschied?

Dijkstra arbeitet nur mit nicht-negativen Gewichten, Bellman-Ford auch mit negativen Gewichten.

Wahr oder Falsch: Dijkstra findet immer die kürzesten Wege.

Wahr, wenn alle Kanten nicht-negativ sind.

Nachteile von Dijkstra?

- Keine negativen Gewichte - Höhere Laufzeit mit großen Graphen.

Dijkstra vs. A*: Unterschied?

A* nutzt heuristische Schätzungen zur Pfadfindung, Dijkstra nicht.

Fülle die Lücke: Dijkstra benötigt eine ______ Liste.

Prioritätsliste zur Auswahl des nächsten Knotens.

Dijkstra vs. Floyd-Warshall: Grundlegende Anwendung?

Dijkstra: Einzelner Quellknoten; Floyd-Warshall: Alle Paare von Knoten.

Wahr oder Falsch: Dijkstra ist immer schneller als Bellman-Ford.

Falsch. Bellman-Ford kann bei negativen Gewichten effizienter sein.

Was ist die Komplexität von Dijkstra mit Min-Heap?

$\displaystyle O((V + E) imes ext{log}(V))$, wobei V Knoten und E Kanten sind.

Dijkstra: Was benötigt man für die Berechnungen?

Graph, Startknoten und eine Prioritätswarteschlange.

Vor- und Nachteile von A* gegenüber Dijkstra?

- Vorteil: Schnellere Lösungen durch Heuristik - Nachteil: Komplexere Implementierung.

Dijkstra vs. Greedy-Algorithmus: Gemeinsamkeit?

Beide wählen jeweils den nächsten optimalen Schritt, jedoch für unterschiedliche Probleme.

Was ist der Hauptnachteil des Bellman-Ford-Algorithmus?

Langsame Laufzeit von $\displaystyle O(V imes E)$ im Vergleich zu Dijkstra.