Implementacja algorytmu Forda-Frulkersona z użyciem stosu

Question

Dzień dobry, chciałbym poprosić o pomoc dotyczącą implementacji algorytmu Forda-Fulkersona w javie. Otóż muszę napisać algorytm na podstawie pseudokodu otrzymanego od prowadzącego, jednak nie do końca rozumiem tego pseudokodu oraz jak ten algorytm ma działać akurat ze stosem. Wiem tylko mniej więcej na czym polega algorytm Forda-Fulkersona czyli na znalezieniu ścieżki od początkowego wierzchołka do końcowego, która przechodzi przez nie pełne krawędzie do przodu i nie puste do tyłu, znalezieniu w tej ścieżce aktualnej minimalnej pojemności oraz z sumowaniu tych przepustowości. Tyle wiem, nie wiem czy to wystarczające . Jednak póki co nie widzę w tym wszystkim stosu.

 

 

Nie mogę zrozumieć za co odpowiada etykieta, oraz ogólnie właśnie jak ma działać ten algorytm ze stosem przez co nie wiem jak się zabrać za ten pseudokod. Jeśli ktoś zna temat i mógłby mi opisać przynajmniej jak powinien algorytm działać ze stosem oraz jakich struktur danych użyć do tego aby go zaimplementować, bardzo by mi pomógł. Jaki ja miałem mniej więcej pomysł, zrobiłem listę list która miała reprezentować graf, czyli List<List<Edge>> gdzie Edge to klasa reprezentująca krawędzie i posiadając 4 zmienne, skąd, dokąd, maksymalna pojemność a także aktualna pojemność. Zaczynając od s, zacząć szukać ścieżki trochę jak w Dijkstrze czyli sprawdzać dla aktualnego wierzchołka jakie są połączone z nim krawędzie i potem wybrać tą która spełnia warunki w algorytmie forda, tutaj póki co moje pomysły się skończyły ponieważ to tej czynności nie użyłem w ogóle stosu a to on miał być podstawą tego algorytmu. Z chęcią przyjmę każdą pomoc/radę/pomysły. Pozdrawiam. 

Answer 1

Obejrzyj:

https://www.youtube.com/watch?v=rW4oCwdqd8I&t=1137s

To ogarniesz.

Comments

Niestety dalej do końca nie rozumiem jak to rozgryźć, nic mi ten filmik nie powiedział, a przynajmniej nie udało mi się połączyć dobrze z tym problemem.