Rozłożenie przepustowości w grafie

Hej.

Mam taki problem z implementacją problemu "upakowania" przepustowości w grafie.

Powiedzmy, że mamy sobie graf skierowany bez cykli o iluś wierzchołkach, z których jeden bądź więcej to wierzchołki końcowe. Krawędzie mają wagi. Tak aby nadać jakieś wyobrażenie i konkretne zastosowanie - krawędzie to rury mogące transportować wodę, a ich wagi to przepustowość. Do różnych, niekońcowych wierzchołków grafu mogą być podpięte "źródła wody". Taki wierzchołek nazywamy wierzchołkiem początkowym dla źróła Ź. Źródło wody ma określoną liczbę kranów. Każdy kran ma wymaganą przepustowość. Ścieżką nazywamy kolejne wierzchołki od wierzchołka poczatkowego do końcowego. Woda z jednego kranu może płynąć jedną ścieżką (takie uproszczenie do obliczeń).
I teraz tak: w różnych momentach czasowych dostajemy polecenie sprawdzenia czy dla źródła Ź_x wystarczy przepustowości:

• przepustowość sprawdzamy dla każdego kranu
• źródło Ź_x ma wystarczającą przepustowość, jeśli każdy jego kran ma wystarczającą przepustowość

Algorytm wygląda tak:

• jeśli Ź_x miało kiedyś wcześniej zmapowane ścieżki, odmapowujemy je
• dla każdego kranu K_x:
  • dla każdej możliwej ścieżki Ś_x dla K_x:
    • jeśli każda krawędź w tej ścieżce ma przepustowość większą lub równą wymaganej przez kran, to mapujemy ścieżkę do tego kranu oraz zmniejszamy pozostałą przepustowość w każdej z krawędzi tej ścieżki
  • jeśli do kranu nie przypisano żadnej ścieżki:
    • próbujemy przemapować (1) pozostałe ścieżki
  • jeśli nadal do kranu nie przypisano żadnej ścieżki:
    • poddajemy się, brak wystarczającej przepustowości dla tego kranu
• jeśli chociaż jeden kran ze źródła nie ma wystarczającej przepustowości, uznajemy, że nie ma przepustowości dla danego źródła, odmapowujemy przypisane ścieżki dla pozostałych kranów tej ścieżki, "oddajemy" zabraną przepustowość

Zobaczmy najprostszy przykład:

Dla uproszczenia powiedzmy, że każdy kran K_x_y ma wymaganą przepustowość 1.
Mamy tu:
K_1_1:

• możliwe ścieżki: {1: [a], przepustowość 2}
• rezerwujemy ścieżkę 1
• a ma teraz przepustowość 1
  K_1_2:
• możliwe ścieżki: {1: [a], przepustowość 1}
• rezerwujemy ścieżkę 1
• a ma teraz przepustowość 0
  Źródło Ź_1 ma zmapowane ścieżki w grafie.

K_2_1:

• możliwe ścieżki: {2: [b], przepustowość 2}
• rezerwujemy ścieżkę 2
• b ma teraz przepustowość 1
  K_2_2:
• możliwe ścieżki: {2: [b], przepustowość 1}
• rezerwujemy ścieżkę 2
• b ma teraz przepustowość 0
  Źródło Ź_2 ma zmapowane ścieżki w grafie.

I wszystko ok. Dodajmy jednak dwie krawędzie łączące p1 z p2 i powiedzmy, że z losowych przyczyn mapowanie nie przeszło tak jak byśmy chcieli:

K_1_1:

• możliwe ścieżki: {1: [a], przepustowość 2}, {2: [c, b], przepustowość 2}
• rezerwujemy ścieżkę 2
• c ma teraz przepustowość 1, b tak samo

K_1_2:

• możliwe ścieżki: {1: [a], przepustowość 2}, {2: [c, b], przepustowość 1}
• rezerwujemy ścieżkę 2
• c ma teraz przepustowość 0, b tak samo
  Źródło Ź_1 ma zmapowane ścieżki w grafie.

K_2_1:

• możliwe ścieżki: {3: [b], przepustowość 0}, {4: [c, a]: przepustowość 0}
• nie można nic zaalokować, próbujemy przemapować:
  • przenosimy K_1_1 na ścieżkę 1
  • a ma teraz przepustowość 1, b 1, c 1
  • mapujemy K_2_1 na ścieżce 3
  • a ma teraz przepustowość 1, b 0, c 1

K_2_2:

• możliwe ścieżki: {3: [b], przepustowość 0}, {4: [c, a]: przepustowość 0}
• nie można nic zaalokować, próbujemy przemapować:
  • przenosimy K_1_2 na ścieżkę 1
  • a ma teraz przepustowość 0, b 1, c 2
  • mapujemy K_2_2 na ścieżce 3
  • a ma teraz przepustowość 0, b 0, c 2
    Źródło Ź_2 ma zmapowane ścieżki w grafie.

Problemem jest tutaj algorytm przemapowania, gdyż ten, który napisałem jest bardzo niewydajny. Dla tak trywialnego przykładu jak ten tutaj nie jest to problem, ale gdy mamy dość duży graf, to program wstrzymuje się na sekundy, szczególnie w sytuacji, gdy rzeczywiście występuje niewystarczająca liczba zasobów.
Algorytm wygląda tak (na przykładzie K_2_1):

• iterujemy po możliwych ścieżkach dla tego kranu 3: [b], 4: [c, a]:
  • 3: [b]
    • bierzemy wszystkie krany, które są zmapowane już do krawędzi tej ścieżki (b): K_1_1, K_1_2. Iterujemy
      • dla K_1_1: sprawdzamy dostępne ścieżki inne niż ta zmapowana: {1: [a]}. Iterujemy:
        • {1: [a]} - tworzymy strukturkę mówiącą jak wyglądałby graf po przemapowaniu: {do zwolnienia: {2: [c, b]}, do mapowania: {1: [a]}, {a:-1, b+1, c+1}} - jeśli to wystarcza (a w tym wypadku wystarcza, to pzremapowujemy i KOŃCZYMY PROCEDURĘ)

**Czy moglibyście zaproponować jakiś wydajniejszy algorytm, albo chociaż gdzie powinienem szukać? **

Myślałem o tym, żeby najpierw mapować najkrótszą możliwą ścieżkę - tutaj by to zadziałało od razu, ale nie mam pewności, że dla dużo bardziej skomplikowanych grafów będzie to prawidłowe podejście

Na oko jest to maksymalny przepływ, czyli Maximum Flow Problem i algorytm Forda-Fullkersona.