Podczas implementacji algorytmu trzech hindusów zauważyłem, że dla sytuacji przedstawionej na załączonym screenie reprezentującym sieć residualną (i jednocześnie sieć warstwową), algorytm wybierając jako wierzchołek o minimalnym potencjale przepływowym (zakładając, że krawędzie opisane są przepustowością równą 1 wszystkie węzły mają jednakową wartość pmin) węzeł 1 i w następstwie ścieżkę S-1-4-T zwrócony zostanie przepływ blokujący równy 1 i wykonana zostanie wyłącznie jeden raz pętla algorytmu, w związku z czym przepływ maksymalny też będzie wynosił 1. Wybierając ścieżkę S-1-3-T lub jako wierzchołek o minimalnym potencjale przepływowym węzeł 2 zostałby zwrócony wynik optymalny równy 2, jednakże w żadnym ze znalezionych pseudokodów nie znalazłem informacji o konieczności zabezpieczenia wyboru następnego/poprzedniego wierzchołka - wszędzie wskazywane jest zachłanne przesyłanie potencjału. Czy w związku z tym ja źle implementuję algorytm, czy też nie zwraca on zawsze optymalnych rozwiązań?

Nie mogę odpowiedzieć na komentarz, więc piszę kolejny post. Dla pseudokodu z załącznika i podanego w pierwszym poście screena wykonywane będą następująco kroki algorytmu:

Założenie: wszystkie krawędzie mają wagę 1.

  1. Graf Gf będący siecią warstwową jest identyczny do grafu residualnego z załącznika w pierwszym poście (warstwa 0 - S, warstwa 1 - wierzchołki 1, 2, warstwa 3 - wierzchołki 3 i 4 oraz T w warstwie 4).
  2. Obliczając najmniejsze c(v) dla każdego wierzchołka otrzymamy S=2, 1=1, 2=1, 3=1, 4=1, T=2.
  3. Wybierając pmin możemy wziąć dowolnie (?) wierzchołek 1, 2, 3 lub 4. Zakładamy, że wybrany został węzeł 1.
  4. Przesyłamy zachłannie pmin do ujścia poprzez kolejne warstwy od wybranego wierzchołka (czyli przesyłamy z węzła 1 minimalny potencjał wynoszący 1 do losowo wybranego wierzchołka z warstwy o jeden większej zawierającej węzeł 3 lub 4, a następnie do T). Zakładamy, że wybrany został wierzchołek 4 - potencjał 1 został przesłany więc ścieżką 1-4-T.
  5. Przesyłamy zachłannie pmin do źródła - czyli dla naszego przykładu z S idziemy do 1.
  6. Usuwamy węzeł 1 i szukamy nowego pmin.
  7. Graf traci spójność i algorytm kończy działanie, a przecież wybierając w kroku 3 węzeł 2 lub 3 moglibyśmy przesłać sumarycznie potencjał o wielkości 2 poprzez ścieżkę S-1-3-T oraz S-2-4-T