Алгоритъм на Форд-Фулкърсън

В този урок ще научите какво представлява алгоритъмът на Ford-Fulkerson. Също така ще намерите работни примери за намиране на максимален поток в поточна мрежа в C, C ++, Java и Python.

Алгоритъмът на Форд-Фулкерсън е алчен подход за изчисляване на максимално възможния поток в мрежа или графика.

Термин, поточна мрежа , се използва за описване на мрежа от върхове и ръбове с източник (S) и мивка (T). Всеки връх, с изключение на S и T , може да получава и изпраща равно количество неща през него. S може само да изпраща, а T може да получава само неща.

Можем да визуализираме разбирането на алгоритъма, като използваме поток от течност в мрежа от тръби с различен капацитет. Всяка тръба има определен капацитет на течност, която може да прехвърли в даден случай. За този алгоритъм ще намерим колко течност може да изтече от източника към мивката в даден случай, използващ мрежата.

Графика на поточната мрежа

Използвани терминологии

Увеличаващ път

Това е пътят, наличен в поточна мрежа.

Остатъчна графика

Той представлява поточната мрежа, която има допълнителен възможен поток.

Остатъчен капацитет

Това е капацитетът на ръба след изваждане на потока от максималния капацитет.

Как работи алгоритъмът на Форд-Фулкърсън?

Алгоритъмът следва:

  1. Инициализирайте потока във всички краища до 0.
  2. Въпреки че има увеличаващ се път между източника и мивката, добавете този път към потока.
  3. Актуализирайте остатъчната графика.

Можем да помислим и за обратен път, ако е необходимо, защото ако не ги разгледаме, може никога да не намерим максимален поток.

Горните понятия могат да бъдат разбрани с примера по-долу.

Пример за Форд-Фулкерсън

Потокът на всички ръбове е 0 в началото.

Пример за графика на поточна мрежа
  1. Изберете произволен път от S до T. В тази стъпка ние избрахме път SABT. Намиране на пътека
    Минималният капацитет между трите ръба е 2 (BT). Въз основа на това актуализирайте потока / капацитета за всеки път. Актуализирайте капацитетите
  2. Изберете друг път SDCT. Минималният капацитет сред тези ръбове е 3 (SD). Намерете следващия път
    Актуализирайте капацитета според това. Актуализирайте капацитетите
  3. Сега, нека разгледаме и BD с обратен път. Избор на път SABDCT. Минималният остатъчен капацитет между ръбовете е 1 (DC). Намерете следващия път
    Актуализиране на капацитетите. Актуализиране на капацитетите
    Капацитетът за преден и обратен път се разглежда отделно.
  4. Добавяне на всички потоци = 2 + 3 + 1 = 6, което е максимално възможният поток в поточната мрежа.

Имайте предвид, че ако капацитетът на който и да е ръб е пълен, тогава този път не може да се използва.

Примери за Python, Java и C / C ++

Python Java C C ++ 
 # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = (False) * (self.ROW) queue = () queue.append(s) visited(s) = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph(u)): if visited(ind) == False and val> 0: queue.append(ind) visited(ind) = True parent(ind) = u return True if visited(t) else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = (-1) * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph(parent(s))(s)) s = parent(s) # Adding the path flows max_flow += path_flow # Updating the residual values of edges v = sink while(v != source): u = parent(v) self.graph(u)(v) -= path_flow self.graph(v)(u) += path_flow v = parent(v) return max_flow graph = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)) g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))
 // Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson ( static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph()(), int s, int t, int p()) ( boolean visited() = new boolean(V); for (int i = 0; i < V; ++i) visited(i) = false; LinkedList queue = new LinkedList(); queue.add(s); visited(s) = true; p(s) = -1; while (queue.size() != 0) ( int u = queue.poll(); for (int v = 0; v 0) ( queue.add(v); p(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph()(), int s, int t) ( int u, v; int Graph()() = new int(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph(u)(v) = graph(u)(v); int p() = new int(V); int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) ( int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p(v)) ( u = p(v); path_flow = Math.min(path_flow, Graph(u)(v)); ) for (v = t; v != s; v = p(v)) ( u = p(v); Graph(u)(v) -= path_flow; Graph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) public static void main(String() args) throws java.lang.Exception ( int graph()() = new int()() ( ( 0, 8, 0, 0, 3, 0 ), ( 0, 0, 9, 0, 0, 0 ), ( 0, 0, 0, 0, 7, 2 ), ( 0, 0, 0, 0, 0, 5 ), ( 0, 0, 7, 4, 0, 0 ), ( 0, 0, 0, 0, 0, 0 ) ); FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); ) )
 / Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity(MAX_NODES)(MAX_NODES); int flow(MAX_NODES)(MAX_NODES); int color(MAX_NODES); int pred(MAX_NODES); int min(int x, int y) ( return x < y ? x : y; ) int head, tail; int q(MAX_NODES + 2); void enqueue(int x) ( q(tail) = x; tail++; color(x) = B; ) int dequeue() ( int x = q(head); head++; color(x) = C; return x; ) // Using BFS as a searching algorithm int bfs(int start, int target) ( int u, v; for (u = 0; u < n; u++) ( color(u) = A; ) head = tail = 0; enqueue(start); pred(start) = -1; while (head != tail) ( u = dequeue(); for (v = 0; v 0) ( enqueue(v); pred(v) = u; ) ) ) return color(target) == C; ) // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) ( int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) ( for (j = 0; j = 0; u = pred(u)) ( increment = min(increment, capacity(pred(u))(u) - flow(pred(u))(u)); ) for (u = n - 1; pred(u)>= 0; u = pred(u)) ( flow(pred(u))(u) += increment; flow(u)(pred(u)) -= increment; ) // Adding the path flows max_flow += increment; ) return max_flow; ) int main() ( for (int i = 0; i < n; i++) ( for (int j = 0; j < n; j++) ( capacity(i)(j) = 0; ) ) n = 6; e = 7; capacity(0)(1) = 8; capacity(0)(4) = 3; capacity(1)(2) = 9; capacity(2)(4) = 7; capacity(2)(5) = 2; capacity(3)(5) = 5; capacity(4)(2) = 7; capacity(4)(3) = 4; int s = 0, t = 5; printf("Max Flow: %d", fordFulkerson(s, t)); )
 // Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph(V)(V), int s, int t, int parent()) ( bool visited(V); memset(visited, 0, sizeof(visited)); queue q; q.push(s); visited(s) = true; parent(s) = -1; while (!q.empty()) ( int u = q.front(); q.pop(); for (int v = 0; v 0) ( q.push(v); parent(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph(V)(V), int s, int t) ( int u, v; int rGraph(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph(u)(v) = graph(u)(v); int parent(V); int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) ( int path_flow = INT_MAX; for (v = t; v != s; v = parent(v)) ( u = parent(v); path_flow = min(path_flow, rGraph(u)(v)); ) for (v = t; v != s; v = parent(v)) ( u = parent(v); rGraph(u)(v) -= path_flow; rGraph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) int main() ( int graph(V)(V) = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)); cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; )

Приложения на Ford-Fulkerson

  • Водоразпределителен тръбопровод
  • Проблем с двустранно съвпадение
  • Тираж с искания

Интересни статии...