Deutsch
Menü

Datenstrukturen und Algorithmen

Welche Bedingung an den Graphen ist erforderlich, damit der Dijkstra-Algorithmus korrekte kürzeste Wege findet?

  1. ADer Graph enthält keine Zyklen (Wege, die zum selben Knoten zurückführen)
  2. BDie Kanten sind ungerichtet
  3. CAlle Kantengewichte sind größer oder gleich 0
Antwort und Erläuterung anzeigen

Antwort: C. Alle Kantengewichte sind größer oder gleich 0

Der Dijkstra-Algorithmus legt unter den noch nicht festgelegten Knoten denjenigen mit der kleinsten Entfernung endgültig fest. Das beruht auf der Annahme, dass ein Umweg über andere Knoten eine Entfernung nur vergrößern, nie verkleinern kann. Gibt es eine Kante mit negativem Gewicht, kann eine Entfernung später über einen anderen Weg kürzer werden; in einem gerichteten Graphen mit S→A 2, S→B 3 und B→A −2 wird A zum Beispiel mit 2 festgelegt, bevor der Weg S→B→A mit der Länge 1 gefunden wird. Bei negativen Gewichten verwendet man den Bellman-Ford-Algorithmus oder ähnliche Verfahren. Mit Zyklen und mit gerichteten Kanten funktioniert der Dijkstra-Algorithmus, solange alle Gewichte größer oder gleich 0 sind.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Für die Aufgaben A bis E gelten die Reihenfolgebedingungen „A vor C“, „B vor C“, „C vor D“, „B vor E“ und „E vor D“. Welche Reihenfolge erfüllt alle Bedingungen (ein Ergebnis der topologischen Sortierung)?
  2. Eine Funktion f(x, y) ist definiert als „ist y gleich 0, gib x zurück; andernfalls gib f(y, x mod y) zurück“. Welchen Rückgabewert liefert der Aufruf f(84, 36), und wie oft wird f aufgerufen, den ersten Aufruf eingeschlossen?
  3. Eine Funktion fib(n) für die Fibonacci-Zahlen ist rekursiv definiert als „ist n kleiner oder gleich 1, gib n zurück; andernfalls gib fib(n−1) + fib(n−2) zurück“. Wie oft wird fib beim Aufruf von fib(5) aufgerufen, den ersten Aufruf eingeschlossen?
  4. 8 Yen sollen mit Münzen zu 1 Yen, 4 Yen und 6 Yen bezahlt werden. Welche Aussage über die Zahl der Münzen, die ein Greedy-Algorithmus wählt (der zuerst so viele der größten Münze wie möglich verwendet), im Verhältnis zur kleinstmöglichen Münzzahl ist richtig?
  5. Ein Rucksack mit der Kapazität 8 wird mit Gegenständen aus vier Gegenständen mit (Gewicht, Wert) (2, 3), (3, 4), (4, 5) und (5, 6) gefüllt. Jeden Gegenstand gibt es nur einmal, und Gegenstände lassen sich nicht teilen. Wie groß ist der höchste Gesamtwert bei einem Gesamtgewicht von höchstens 8?