Komplexität Prim und Dijkstra

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Komplexität Prim und Dijkstra

Beitrag von robertH »

Hallo zusammen,

ich stehe hier etwas auf dem Schlauch und wäre für Hilfe dankar. Ich verstehe nicht warum die Komplexität von Prim (kantenzahl + knotenzahl)*Komplexität priority queue ist während
die von Dijkstra Knotenzahl*Komplexität von priority queue + Kantenzahl ist. Speichern wir irgendetwas zusätzliches bei Prim in der Queue ab und müssen diese deshalb häufiger verwenden und ja warum? Ich bin verwirrt weil die so verdammt ähnlich sind.

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Re: Komplexität Prim und Dijkstra

Beitrag von ob1 »

Der Unterschied liegt darin begründet, dass Dijkstra nur einen Pfad sucht, während Prim den MST ausgibt. Dijkstra schaut sich in einer Iteration nur einen Knoten (bzw. dessen ausgehende Kanten) an, nämlich den, der bis dahin den kürzesten Weg hatte. Prim dagegen muss alle Kanten mit einbeziehen, um den Pfad mit dem geringsten Gewicht zum nächsten Knoten zu finden.

Das sieht man, wenn man es weiß, auch beim Draufschauen auf die Induktionsschritte der beiden Algorithmen.

29917180
Erstie
Erstie
Beiträge: 12
Registriert: 17. Mai 2013 21:21

Re: Komplexität Prim und Dijkstra

Beitrag von 29917180 »

Das habe ich nicht gesehen und habe daher in der Wikipedia nachgeschaut. Dort steht für beide Algorithmen, dass sie eine Komplexität von O(m + n*log(n)) haben. Das liegt daran, dass man im worst case bei beiden Algorithmen m-mal decreaseKey aufrufen muss. Die Wikipedia geht von einem Fibonacci-Heap aus, bei dem die Operation decreaseKey O(1) Laufzeit hat. Da wir hier nur normale Heaps kennen, bei denen die Operation decreaseKey eine Laufzeit von O(log(n)) hat, sollte eigentlich bei beiden Operationen eine Komplexität von O((n+m)*log(n)) stehen. Ich denke es ist einfach ein kleiner Fehler in unserem Wiki, außer ich habe etwas falsch verstanden, dann entschuldige ich mich

Antworten

Zurück zu „Archiv“