У цьому посібнику ви дізнаєтесь, що таке алгоритм Форда-Фулькерсона. Крім того, ви знайдете робочі приклади пошуку максимального потоку в потоковій мережі на C, C ++, Java та Python.
Алгоритм Форда-Фулькерсона - це жадібний підхід до розрахунку максимально можливого потоку в мережі або графіку.
Термін, потокова мережа , використовується для опису мережі вершин і ребер із джерелом (S) і поглиначем (T). Кожна вершина, крім S і T , може приймати і надсилати через неї рівну кількість речей. S може лише відправляти, а T може отримувати лише речі.
Ми можемо візуалізувати розуміння алгоритму, використовуючи потік рідини всередині мережі труб різної ємності. Кожна труба має певну ємність рідини, яку вона може передати в окремому випадку. Для цього алгоритму ми будемо знаходити, скільки рідини може надходити від джерела до раковини в екземплярі за допомогою мережі.
Графік потокової мережі
Використовувана термінологія
Збільшення шляху
Це шлях, доступний в потоковій мережі.
Залишковий графік
Він представляє потокову мережу, яка має додатковий можливий потік.
Залишкова ємність
Це ємність краю після віднімання витрати від максимальної потужності.
Як працює алгоритм Форда-Фулькерсона?
Алгоритм наступний:
- Ініціалізуйте потік по всіх краях до 0.
- Поки між джерелом і стоком є збільшуючий шлях, додайте цей шлях до потоку.
- Оновіть графік залишків.
Ми також можемо розглянути зворотний шлях, якщо потрібно, тому що, якщо ми не врахуємо їх, ми можемо ніколи не знайти максимальний потік.
Вищезазначені поняття можна зрозуміти на прикладі нижче.
Приклад Форда-Фулькерсона
Потік усіх ребер на початку дорівнює 0.
Приклад графіку потокової мережі
- Виберіть будь-який довільний шлях від S до T. На цьому кроці ми вибрали шлях SABT.
Знайдіть шлях
Мінімальна ємність між трьома ребрами - 2 (BT). Виходячи з цього, оновіть потік / пропускну здатність для кожного шляху.
Оновіть потужність - Виберіть інший шлях SDCT. Мінімальна ємність серед цих країв - 3 (SD).
Знайти наступний шлях
Оновіть потужності відповідно до цього.
Оновіть потужність - А тепер давайте розглянемо також BD із зворотним шляхом. Вибір шляху SABDCT. Мінімальна залишкова ємність між краями дорівнює 1 (постійного струму).
Знайти наступний шлях
Оновлення потужностей.
Оновлення
пропускної спроможності Пропускна здатність прямого та зворотного трактів розглядається окремо. - Додавання всіх потоків = 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; )
Заявки Форда-Фулькерсона
- Водорозподільний трубопровід
- Проблема двостороннього узгодження
- Тираж із вимогами
