Effiziente Algorithmen Übung 8.pdf

Assignments
Uploaded by Janik M 4868 at 2018-06-28
Description:

Ausführliche Mitschrift aller Lösungen aus der Übungsgruppe zu den Aufgaben des achten Übungsblatts.

 0
159
2
Download
das müsste doch eine 5 sein, richtig?
View 1 more comment
Die acht müsste eine fünf sein. Das war die Frage ?
Achso, die Markierung war auf dem Buchstaben :D ja klar, du hast Recht, in diesem Schritt ist der Nettofluss bei s 5.
No area was marked for this question
Hallo :) Kann mir jemand erklären, wo die 8 (Knoten r, Initialisierung) herkommt? Bzw was generell in der linken Zahl passiert?
Wenn ich mich richtig erinnere (ist 1 Jahr her und hab das noch nicht im Detail angeschaut) kommt da ne 8 hin, weil es insgesamt 8 Knoten sind. Die linke Zahl (ich glaube "Distanz") wird so lange erhöht (relabel), bis man auf einen Knoten pushen kann, wo die lnike Zahle geringer ist. Deswegen ist Schritt 1 relabel(a) (-> linke Zahl ist 1) und dann erst push(a,d).
Genau, das label von r ist stehts die Anzahl der Knoten im Netzwerk. In der Vorlesung ist der Überschuss von r die Summe der Flüssen, die r an seinen Nachbarn schickt (hier wäre also -13). In der Übung ist der Überschuss von r aber 0. Wurde gesagt warum? Bzw. welche Version wir nutzen sollen?