Hilfe zur Klausuraufgabe Klausur Sep 2012 (SS 2012)

Hi Uried,
warum sind bei Dir in M Knoten 1-5? Bei mir wird die Menge M sukzessive "leerer" und ist ab 2.3 { }.
Ab 2.3. nehmen bei mir die Knoten um einen Schritt jeweils ab ( wie Du selber schreibtest ) und Knoten 0 habe ich 0,
den Rückwärtspfeil mal geflissentlich mißachtet ;)

Grüße

PS: War eine meiner ersten Übungen zur Klausur, deswegen erhebe ich keinerlei Anspruch auf Korrektheit ;)

Ottokarotto schrieb:

Hi Uried,
warum sind bei Dir in M Knoten 1-5? Bei mir wird die Menge M sukzessive "leerer" und ist ab 2.3 { }.
Ab 2.3. nehmen bei mir die Knoten um einen Schritt jeweils ab ( wie Du selber schreibtest ) und Knoten 0 habe ich 0,
den Rückwärtspfeil mal geflissentlich mißachtet ;)

Grüße

PS: War eine meiner ersten Übungen zur Klausur, deswegen erhebe ich keinerlei Anspruch auf Korrektheit ;)

Zum Vergrößern anklicken....

Die 0 bei Knoten 0 ist wahrscheinlich richtiger.

Die Knoten 1,2,3,4,5 bei M stehen deshalb (m.A.n.) drin, weil sich diese in jedem Schritt ändern. Gemäß Algo. zum Ford baut sich ja M in jedem Iterationsschritt neu auf, indem geprüft wird, ob jeder Knoten aus L (L ist ja eine Kopie des M im letzten Schritt) nicht doch günstiger zu erreichen ist. Und das ist hier ja auf Grund des neg. Zyklus der Fall. Mit jedem Schritt ab 2.3 sind alle Knoten (außer 0) um je 1 immer besser zu erreichen. Nach meinem Verständnis.

Deine These würde belegen, daß auf S.57 im letzten Satz von c) steht: das Verfahren bricht ab, wenn M leer ist.
Ich hätte also viel früher abbrechen müssen.
Auf der anderen Seite steht bei der Vorstellung vom Ford-Algo: Netzwerk, nicht notwendig zyklenfrei, aber nur Zyklen nicht-negativer-Länge....

Von daher finde ich den didaktischen Ansatz in einer Klausur etwas zweifelhaft.