Алгоритм Форда‑Фулькера – максимальний потік

Повне пояснення

Коротке пояснення

Алгоритм Форда‑Фулькера шукає послідовно збільшуючі шляхи від джерела до стоку, додаючи потік по кожному знайденому шляху. Коли більше шляхів не існує, отриманий потік є максимальним.

Аналогія

Уявіть, що мережа – це система річок з різними ширинами; алгоритм поступово розширює потік, доки не заповнить всі доступні «труби».

Коли застосовувати

• Задачі про транспорт, логістика або мережевий трафік.
• Мережа з неотрицательними пропускними способностями.
• Потрібен точний максимум, а не лише оцінка.
• Вхід – граф у вигляді списку суміжності або матриці.
• Потрібно обчислити потік між конкретними вершинами‑джерелом і стоком.

Кроки алгоритму

1. Ініціалізувати потік у всіх ребрах нульовим.
2. Знайти в графі шляхи, що збільшують потік (BFS/DFS), використовуючи залишкові пропускні способності.
3. Якщо шлях знайдено, визначити мінімальну залишкову пропускність по цьому шляху.
4. Додати цей мінімум до потоку кожного ребра на шляху і оновити залишкові пропускності.
5. Повторювати кроки 2–4, доки нові шляхи не будуть знайдені.
6. Повернути сумарний потік як результат.

Візуальна інтуїція (текстова)

  source
    | 5
    v
   (1) --3--> (2)
    |          |
  4|          |2
    v          v
   (3) --6--> sink

Перший шлях: source→1→2→sink (мін. 3). Потім оновлюємо пропускності і шукаємо новий шлях: source→3→sink (мін. 4). Після двох ітерацій потік = 7.

Складність

Часова складність: O(VE²) у найгіршому випадку, де V – кількість вершин, E – ребер. Пам’ятна складність: O(V+E) для зберігання графу і залишкових пропускностей.

Код (js)

// Функція для знаходження максимального потоку за алгоритмом Форда‑Фулькера
function fordFulkerson(graph, source, sink) {
  // graph – об’єкт, ключі – вершини, значення – масив ребер {to, capacity}
  const residual = {}; // залишкові пропускності

  // ініціалізуємо залишкову мережу
  for (const u in graph) {
    residual[u] = [];
    for (const edge of graph[u]) {
      // додаємо пряме ребро
      residual[u].push({ to: edge.to, capacity: edge.capacity });
      // додаємо зворотне ребро з нульовою пропускністю
      residual[edge.to] = residual[edge.to] || [];
      residual[edge.to].push({ to: u, capacity: 0 });
    }
  }

  let maxFlow = 0; // загальний потік

  while (true) {
    // ініціалізуємо BFS: черга, відвідані вершини і шлях
    const queue = [source];
    const visited = new Set([source]);
    const parent = {}; // зберігаємо попередника і ребро

    while (queue.length && !visited.has(sink)) {
      const u = queue.shift();
      for (const edge of residual[u]) {
        if (!visited.has(edge.to) && edge.capacity > 0) {
          visited.add(edge.to);
          parent[edge.to] = { from: u, edge };
          queue.push(edge.to);
        }
      }
    }

    // якщо шлях не знайдено, завершуємо цикл
    if (!visited.has(sink)) break;

    // знаходимо мінімальну пропускність по знайденому шляху
    let pathFlow = Infinity;
    for (let v = sink; v !== source; v = parent[v].from) {
      pathFlow = Math.min(pathFlow, parent[v].edge.capacity);
    }

    // оновлюємо пропускності по шляху
    for (let v = sink; v !== source; v = parent[v].from) {
      const u = parent[v].from;
      // зменшуємо пряме ребро
      const e = residual[u].find(e => e.to === v);
      e.capacity -= pathFlow;
      // збільшуємо зворотне ребро
      const rev = residual[v].find(e => e.to === u);
      rev.capacity += pathFlow;
    }

    maxFlow += pathFlow; // додаємо до загального потоку
  }

  return maxFlow;
}

// Тестовий приклад
const graph = {
  source: [{ to: '1', capacity: 10 }, { to: '2', capacity: 5 }],
  '1': [{ to: '3', capacity: 4 }, { to: '2', capacity: 15 }],
  '2': [{ to: '4', capacity: 10 }],
  '3': [{ to: sink, capacity: 10 }],
  '4': [{ to: sink, capacity: 10 }]
};
const sink = 'sink';
console.log(fordFulkerson(graph, 'source', sink)); // очікуваний результат: 15

Типові помилки і поради

1. Неправильне оновлення залишкових ребер – переконайтеся, що зворотні ребра створюються лише один раз.
2. Використання DFS замість BFS – це може призвести до O(VE) у найгіршому випадку; BFS гарантує швидший збіг.
3. Забудьте про нульові пропускності – вони потрібні для зворотних ребер, інакше алгоритм не працюватиме.
4. Не перевіряйте наявність вершини‑стоку – якщо вона відсутня, алгоритм завершиться помилкою.
5. Оптимізація – використовуйте алгоритм Едмонда‑Карпа (BFS) замість простого DFS, щоб досягти O(VE²).

Перевір себе

1. Яка залишкова пропускність після першої ітерації у тестовому прикладі?
2. Чому BFS використовується для пошуку шляхів у Ford‑Fulkerson?