Seite 1 von 1

Zykel bei Goldberg-Tarjan

Verfasst: 1. Feb 2017 16:16
von the D
Hallo allerseits,

ich habe gerade Goldberg-Tarjan implementiert und mir fiel auf, dass der produzierte (zulässige) Fluss am Ende viele "unnötige" Zykel enthält, also solche, wo Fluss aus s (dem Startknoten) herausfließt und dann über einen Zykel wieder nach s zurückkommt.

Ich vermute es liegt daran, dass der "Überfluss" i.A. nicht auf dem selben Weg nach s zurück "gepusht" wird auf dem er s verlassen hat. Bei den anderen Algorithmen, die mittels DFS/BFS augmentierende Pfade suchen kann sowas aus naheliegenden gründen ja nicht passieren.

Ist das mit den Zykeln ein normaler Nebeneffekt von Goldberg-Tarjan oder habe ich irgendwo etwas falsch gemacht?

Grüße

Dominik

Re: Zykel bei Goldberg-Tarjan

Verfasst: 12. Feb 2017 20:23
von Prof. Karsten Weihe
the D hat geschrieben: Ist das mit den Zykeln ein normaler Nebeneffekt von Goldberg-Tarjan oder habe ich irgendwo etwas falsch gemacht?
Ich denke, das ist absolut ok.

Man kann ja hinterher die Zykel wieder eliminieren (nicht gefordert).

KW