D120.de/forum

also ich kann mich jetzt auch mit der tud-id einloggen auf der informatik seite, und dann aeh ich meine alten daten mittels der hir angegebenen links ABER. ich bekomm laufend die fehlermeldung "Die folgenden Module wurden anders angemeldet als hier angegeben" und dann werden module aufgelistet die ...

Also ich kann nur empfehlen sich die Originalarbeit von Reinefeld anzuschauen. Der Algorithmus ist da sehr verständlich erklärt. Hat mir mehr gebracht das entsprechende Kapitel in dem Paper zu lesen als zu versuchen, die zugehörigen Folien im KI-Skript zu verstehen. Allerdings: Der Algorithmus in de...

Kann mir jemand von euch das PW ebenfalls zukommen lassen?
Besten Dank!

Ich wünsche euch allen auch viel Erfolg! Wird schon schiefgehen...

Naja du kannst ja nicht einfach mal blind den excess zu einem beliebigen Nachbarknoten w pushen, da du nicht weißt, wieviel throughput w - bzw. seine Nachfolger - hat (in Richtung s). Aus diesem Grund *musst* du Pfade zu s aufbauen (ausgehend von jedem excess node) da jeder dieser Pfade evtl. eine K...

Die Pfade zu den Nachbarknoten sind aber nicht notwendigerweise eindeutig bestimmt. D.h. du pushst nicht einfach blind zu den Nachbarknoten, die auf einem Distanzlevel untendrunter liegen, sondern baust Pfade nach s auf, damit du weißt, wieviel überhaupt über einen solchen Pfad zurückfließen kann. D...

Angenommen du hast in der ersten Phase einen Layered Graph mit d(s) = 3. Dann findest du in dieser Phase blockierende Kanten für alle kantenkürzesten s-t-Wege der Länge 3. Dadurch, dass du einen Blocking Flow aufbaust, gibts keine weiteren Wege der Länge 3 mehr, auf denen du Fluss schicken würdest. ...

Ja gut, du kannst die Pfade natürlich auch anders aufbauen :). Ich hatte es zuerst so (in dieser Reihenfolge): 1-3-5-6, saturiert 3-5 (+Fluss 1) 1-2-4-6, saturiert 1-2, 2-4 (+Fluss 3) 1-3-4-6, saturiert 4-6 (+Fluss 1) Dabei sieht man auch gut, dass auch nicht saturierte Kanten aus dem Layered Graph ...

Ja, ich denke so in etwa sollte das hinkommen. Ich versuche mal zu beschreiben, wie ich es verstanden habe. Der Layered Graph pro Phase besteht lediglich aus admissible arcs (in Anbetracht des aktuellen Rediualgraphen!). Das heißt ferner, wir finden dort nur s-t-Pfade, die kantenkürzest sind. Wir ba...

Danke für die Hilfestellung! Mir ist inzwischen klar geworden, wo bei der Sache mein Denkfehler gelegen hat .

In Übung 8 hatten wir uns in der 1. Aufgabe mit optimalen Knotenpotenzialen \pi(v) beschäftigt und den Graphen so transfomiert, dass der Fluss mit einem Maxflow-Algorithmus gefunden werden kann. Wenn ich mich recht erinnere, dann gingen wir dabei so vor: Wir berechnen die reduzierten Kantenkosten c^...

Warum es da Zyklen geben kann, ist klar. BFS läuft laut Folien jedoch in O(m), nicht O(n)... Genau genommen in O(n+m) laut Skript ;). Zum Problem: Ich denke es geht auch folgendermaßen. Die Knoten im predecessor graph sind zu Beginn nicht gelabelt. Nun startest du bei einem beliebigen Knoten v im p...

Der Bellman-Ford-Algorithmus verwendet gar keine Queues... Genausowenig die CORRECT-Prozedur. Das ist auch der Grund, warum ich die FIFO- und Deque-Varienten eher für Implementierungen des modifizierten Label-Correcting-Algorithmus halte und nicht direkt für Varienten des Bellman-Ford-Algorithmus'....

Ich habe auch noch eine: Auf Folie 109 steht "Label setting algorithms are applicable only to directed acyclic graphs (DAGs) OR to graphs with non-negative arc lengths". Jedoch ist auf Folie 133 schon ein Beispiel angegeben für einen DAG wo Dijkstra nicht funktioniert, oder? Ich stimme dir zu. Dijk...

Hallo, ich poste mal die Fragen zu Kapitel, die bei mir noch offen sind, hier, damit jeder was von den Antworten hat, sollten welche auftauchen! (S. 143) Ist die Deque-Variente eine Modifikation des Bellman-Ford-Algorithmus (oder eher eigenständig)? Falls ja, wie würde man das in den Algorithmus ei...