Prim: Mehrere Kanten mit gleichem Gewicht - welche wählen?

[headhumper]

Die Musterlösung wählt als nächste Kante (d,f), warum? (b,j) hat das gleiche Gewicht und kommt in der Sortierung früher.
Ich war/bin mir nicht sicher, wie "Hinweis: Die Menge V ist chronologisch Sortiert und wird auch in dieser Reihenfolge durchlaufen." zu verstehen ist.
Heißt das eventuell, dass zuerst die Kanten mit dem geringsten Gewicht genommen werden, die an einem Knoten hängen, der möglichst früh hinzugefügt wurde?

Edit: Aber das macht irgendwie auch keinen Sinn, denn b war der Startknoten...

prim.PNG (232.75 KiB) 983 mal betrachtet

[Alexj1988]

http://wiki.algo.informatik.tu-darmstadt.de/Prim

V ist eine Menge und daher eigentlich unsortiert. Aus gründen der Berechenbarkeit(Arbeitsspeicher) wird V als Liste behandelt, wobei V chronologisch sortiert ist.

aka es wird die Kante genommen, die für (v,w) als letztes die bedingung im Induktion step erfüllt hat genommen (aus dem vorherigen Induktion step.

mfg Alex

[headhumper]

Dann verstehe ich es immer noch nicht...

Startknoten war f
c ist der jüngste Knoten

Jetzt wird im nächsten Schritt aber (a,d) gewählt und nicht (b,c)

prim2.PNG (249.79 KiB) 972 mal betrachtet

[Alexj1988]

Dann verstehe ich es immer noch nicht...

Startknoten war f
c ist der jüngste Knoten

Jetzt wird im nächsten Schritt aber (a,d) gewählt und nicht (b,c)

prim2.PNG

Ok, da fehlt ein weiterer hinweis. Wird sofort erledigt. (Q wird ist nach Kantengewicht sortiert und bei gleichen Kantengewichten Chronologisch)

Schau am besten auch mal in die Musterlösung, da werden alle Mengen, Warteschlangen etc angegeben.

mfg Alex

[Nullmann]

Es ist immer nur wichtig, zu welchem Knoten die Kante geht! Egal, von welchem diese ausgeht.
Bei deinem ersten Beispiel: d->f und b->j; f kommt im Alphabet vor j
Bei deinem zweiten Beispiel: d->a und c->b; a kommt im Alphabet vor b

Wenn man sich momentan nicht sicher ist, welcher Knoten als nächstes abgearbeitet werden muss, kann man alle restlichen Knoten durchgehen und schauen, was die momentan kürzesten Wege zu dem grünen Baum ist. Ergibt sich dann die Situation wie oben, dass zwei Knoten die gleiche Gewichtung haben, wird der lexikographisch kleinere Knoten genommen.

[headhumper]

Ah, ok! Aber was soll dann der "Hinweis: Die Menge V ist chronologisch Sortiert und wird auch in dieser Reihenfolge durchlaufen." sagen?
An welcher Stelle kommt die chronologische Sortierung ins Spiel

(Oder sollte da ein anderes Wort als "chronologisch" stehen?)

[Alexj1988]

Ah, ok! Aber was soll dann der "Hinweis: Die Menge V ist chronologisch Sortiert und wird auch in dieser Reihenfolge durchlaufen." sagen?
An welcher Stelle kommt die chronologische Sortierung ins Spiel

(Oder sollte da ein anderes Wort als "chronologisch" stehen?)

Ups da sollte lexikographisch hin

mfg Alex

[headhumper]

"Fremdwörter sind Glückssache"?

Dann ist jetzt hoffentlich alles geklärt, danke für die schnelle Hilfe

[Alexj1988]

"Fremdwörter sind Glückssache"?

Dann ist jetzt hoffentlich alles geklärt, danke für die schnelle Hilfe

Frage mich immer noch wieso ich chronologisch geschrieben habe :/

[Stan23]

Ich hab hier noch einen anderen Fall:

Mit welcher Begründung wird hier (b,e) und nicht (e,i) gewählt?
Ebenfalls die lexikographische Sortierung zwischen b und i? Ich kann mich dran erinnern, dass das nicht immer passte...

Gruß,
Stan

[Alexj1988]

Ich hab hier noch einen anderen Fall:

Mit welcher Begründung wird hier (b,e) und nicht (e,i) gewählt?
Ebenfalls die lexikographische Sortierung zwischen b und i? Ich kann mich dran erinnern, dass das nicht immer passte...

Gruß,
Stan

Wie gesagt ins wiki schauen was im induction step passiert. Da kommt nämlich raus, das die Kante am Anfang gewählt wird die in der voriteration bestimmt wurde. (Und dabei wird V durchlaufen)

[Stan23]

Danke!

[Smith]

Ich dachte ich hätte es jetzt verstanden, aber wohl doch noch nicht ganz...
Wieso wird hier nun im nächsten Schritt die Kante b-g ausgewählt und nicht f-j (wird dann als nächstes erst in der Musterlösung gewählt), obwohl f der Startknoten war?
Hatte es jetzt so verstanden, dass die höchste Priorität bei gleicher Pfadlänge sei: welcher Knoten hat den Pfad mit momentan kürzester Länge zuerst gesehen. Dachte dass erst bei gleichen Pfadlängen vom selben Knoten ausgehend dann lexikographisch gewählt wird.
Wo ist der Denk- / Verständnisfehler?

foo6.jpg (54.16 KiB) 709 mal betrachtet

[Alby407]

@Smith

g kommt doch vor j im Alphabet! Deshalb wird auch Kante b-g bevorzugt.

[Smith]

@Alby407

Danke für deine Antwort, aber ich denke nicht, dass das so simpel ist.

Ich bestehe mit meiner Herangehensweise nahezu jede Aufgabe. Dabei gehe ich so vor, dass ich mir immer die Kante mit dem aktuell kürzesten Weg merke. Sei dieser der key der Kante, die Knoten a mit Knoten b verbindet. Kommt ein kürzerer Weg durch neue Verbindungen hinzu wird diese gewählt. Diese kürzere Kante verbinde beispielsweise Knoten b und c.
Sind jetzt durch c keine kürzeren Verbindungen hinzu gekommen und der kürzeste Weg ist in a und b gleich, so bevorzuge ich a (also zB a-x vor b-e), auch mehrfach, vor lexikographischer Ordnung, falls mehrere Kanten der selben, kürzesten, Länge von a abgehen.
Erst in dem Falle, dass in diesem Beispiel tatsächlich mehrere Kanten mit kürzester Länge von a abgehen, wird der lexikografisch niedrigste Zielknoten bevorzugt (also a-g vor a-x, aber beide vor b-e).
So habe ich das verstanden.

Was ist daran falsch?
Es scheint fast immer so zu klappen, aber anhand des Screenshots kann ich die Entscheidung in diesem Fall nicht nachvollziehen...

Dass einfach immer lexikografisch ausgewählt wird ist anhand von zahlreichen Versuchen von meiner Seite aus nicht korrekt.