Максимальний потік — алгоритм проштовхування передпотоку (push-relabel)

Алгоритм проштовхування передпотоку (push-relabel) (також відомий як алгоритм preflow-push) — це алгоритм для обчислення максимального потоку в потоковій мережі. Точне формулювання задачі, яку ми хочемо розв'язати, можна знайти у статті Максимальний потік — Форда-Фалкерсона та Едмондса-Карпа.

У цій статті ми розглянемо розв'язання задачі шляхом проштовхування передпотоку через мережу, що працює за час $O(V^4)$, а точніше за час $O(V^2 E)$. Алгоритм розробили Ендрю Голдберг та Роберт Тарджан у 1985 році.

Коли підходить цей алгоритм?

• Потрібен максимальний потік у мережі з пропускними здатностями (без вартостей на ребрах)? (якщо ребра мають вартості → потік мінімальної вартості)
• Граф щільний, і гарантований час $O(V^2 E)$ привабливіший за пошук доповнювальних шляхів? (для більшості задач достатньо простішого Дініца)
• Готовий до складнішої реалізації заради кращої практичної швидкодії? (ще швидша версія → покращений push-relabel)

Означення

Під час роботи алгоритму нам доведеться мати справу з передпотоком — тобто з функцією $f$, яка схожа на функцію потоку, але не обов'язково задовольняє умову збереження потоку. Для неї мають виконуватися лише обмеження

$$0 \le f(e) \le c(e)$$

та

$$\sum_{(v, u) \in E} f((v, u)) \ge \sum_{(u, v) \in E} f((u, v))$$

Отже, деяка вершина може отримувати більше потоку, ніж вона розподіляє. Ми кажемо, що така вершина має деякий надлишок потоку, і визначаємо його величину за допомогою функції надлишку $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$.

Так само, як і з функцією потоку, ми можемо визначити залишкові пропускні здатності та залишковий граф за допомогою функції передпотоку.

Алгоритм починає роботу з початкового передпотоку (деякі вершини мають надлишок), і під час виконання передпотік буде оброблятися та змінюватися. Розкриваючи деякі деталі наперед: алгоритм вибиратиме вершину з надлишком і проштовхуватиме надлишок до сусідніх вершин. Він повторюватиме це, доки всі вершини, окрім витоку та стоку, не позбудуться надлишку. Легко бачити, що передпотік без надлишку є коректним потоком. Завдяки цьому алгоритм завершується зі справжнім потоком.

Залишаються ще дві проблеми, з якими ми маємо розібратися. По-перше, як ми гарантуємо, що це справді завершиться? А по-друге, як ми гарантуємо, що це справді дасть нам максимальний потік, а не якийсь випадковий потік?

Щоб розв'язати ці проблеми, нам потрібна допомога ще однієї функції, а саме функції мітки $h$, яку часто також називають функцією висоти і яка присвоює кожній вершині ціле число. Ми називаємо мітку коректною, якщо $h(s) = |V|$, $h(t) = 0$ і $h(u) \le h(v) + 1$ за умови, що в залишковому графі є ребро $(u, v)$ — тобто ребро $(u, v)$ має додатну пропускну здатність у залишковому графі. Інакше кажучи, якщо можна збільшити потік з $u$ до $v$, то висота $v$ може бути не більш ніж на одиницю меншою за висоту $u$, але вона може бути рівною або навіть більшою.

Важливо зауважити, що якщо існує коректна функція мітки, то в залишковому графі не існує доповнювального шляху від $s$ до $t$. Адже такий шлях матиме довжину щонайбільше $|V| - 1$ ребер, і кожне ребро може зменшити висоту щонайбільше на одиницю, що неможливо, якщо перша висота дорівнює $h(s) = |V|$, а остання — $h(t) = 0$.

Використовуючи цю функцію мітки, ми можемо сформулювати стратегію алгоритму push-relabel: Ми починаємо з коректного передпотоку та коректної функції мітки. На кожному кроці ми проштовхуємо деякий надлишок між вершинами та оновлюємо мітки вершин. Ми маємо подбати про те, щоб після кожного кроку передпотік і мітка залишалися коректними. Якщо ж алгоритм визначає, що передпотік є коректним потоком. А оскільки в нас також є коректна мітка, то в залишковому графі не існує шляху між $s$ і $t$, а це означає, що потік справді є максимальним.

Якщо порівняти алгоритм Форда-Фалкерсона з алгоритмом push-relabel, то здається, що ці алгоритми є двоїстими один до одного. Алгоритм Форда-Фалкерсона весь час підтримує коректний потік і покращує його, доки більше не існує доповнювального шляху, тоді як в алгоритмі push-relabel доповнювального шляху не існує в жоден момент, і ми покращуємо передпотік, доки він не стане коректним потоком.

Алгоритм

Спочатку ми маємо ініціалізувати граф коректним передпотоком та функцією мітки.

Використати порожній передпотік — як це робиться в алгоритмі Форда-Фалкерсона — неможливо, бо тоді існуватиме доповнювальний шлях, а це означає, що коректної мітки не існує. Тому ми ініціалізуємо кожне ребро, що виходить з $s$, його максимальною пропускною здатністю: $f((s, u)) = c((s, u))$. А всі інші ребра — нулем. У цьому випадку існує коректна мітка, а саме $h(s) = |V|$ для витоку і $h(u) = 0$ для всіх інших.

Тепер опишемо дві операції докладніше.

За допомогою операції push (проштовхування) ми намагаємося проштовхнути якомога більше надлишку потоку з однієї вершини $u$ до сусідньої вершини $v$. У нас є одне правило: нам дозволено проштовхувати потік з $u$ до $v$, лише якщо $h(u) = h(v) + 1$. Простими словами, надлишок потоку має текти вниз, але не надто стрімко. Звісно, ми можемо проштовхнути лише $\min(x(u), c((u, v)) - f((u, v)))$ потоку.

Якщо вершина має надлишок, але неможливо проштовхнути цей надлишок до жодної сусідньої вершини, то нам потрібно збільшити висоту цієї вершини. Цю операцію ми називаємо relabel (підняття). Ми збільшуємо її настільки, наскільки це можливо, але так, щоб мітка залишалася коректною.

Підсумовуючи, алгоритм у двох словах такий: Ми ініціалізуємо коректний передпотік і коректну мітку. Поки ми можемо виконувати операції проштовхування або підняття, ми їх виконуємо. Після цього передпотік стає справжнім потоком, і ми його повертаємо.

Складність

Легко показати, що максимальна мітка вершини дорівнює $2|V| - 1$. У цей момент увесь решта надлишку може бути і буде проштовхнутий назад до витоку. Це дає щонайбільше $O(V^2)$ операцій підняття.

Можна також показати, що буде виконано щонайбільше $O(V E)$ насичувальних проштовхувань (проштовхування, де використовується вся пропускна здатність ребра) і щонайбільше $O(V^2 E)$ ненасичувальних проштовхувань (проштовхування, де пропускна здатність ребра використовується не повністю). Якщо ми оберемо структуру даних, яка дозволяє знаходити наступну вершину з надлишком за час $O(1)$, то загальна складність алгоритму становить $O(V^2 E)$.

Реалізація

C++

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess, seen;
queue<int> excess_vertices;

void push(int u, int v) {
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d)
        excess_vertices.push(v);
}

void relabel(int u) {
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u) {
    while (excess[u] > 0) {
        if (seen[u] < n) {
            int v = seen[u];
            if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
                push(u, v);
            else 
                seen[u]++;
        } else {
            relabel(u);
            seen[u] = 0;
        }
    }
}

int max_flow(int s, int t) {
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
    	if (i != s)
	        push(s, i);
    }
    seen.assign(n, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != s && u != t)
            discharge(u);
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

Python

from collections import deque

INF = 10**9


def max_flow(n, capacity, s, t):
    # flow[u][v] — поточний потік ребром (u, v); від'ємний на зворотному ребрі
    flow = [[0] * n for _ in range(n)]
    height = [0] * n
    excess = [0] * n
    seen = [0] * n
    excess_vertices = deque()
    height[s] = n
    excess[s] = INF

    def push(u, v):
        d = min(excess[u], capacity[u][v] - flow[u][v])
        flow[u][v] += d
        flow[v][u] -= d
        excess[u] -= d
        excess[v] += d
        if d and excess[v] == d:
            excess_vertices.append(v)

    def relabel(u):
        d = INF
        for i in range(n):
            if capacity[u][i] - flow[u][i] > 0:
                d = min(d, height[i])
        if d < INF:
            height[u] = d + 1

    def discharge(u):
        while excess[u] > 0:
            if seen[u] < n:
                v = seen[u]
                if capacity[u][v] - flow[u][v] > 0 and height[u] > height[v]:
                    push(u, v)
                else:
                    seen[u] += 1
            else:
                relabel(u)
                seen[u] = 0

    for i in range(n):
        if i != s:
            push(s, i)

    while excess_vertices:
        u = excess_vertices.popleft()
        if u != s and u != t:
            discharge(u)

    return sum(flow[i][t] for i in range(n))

TypeScript

const INF = 1_000_000_000;

function maxFlow(n: number, capacity: number[][], s: number, t: number): number {
    // flow[u][v] — поточний потік ребром (u, v); від'ємний на зворотному ребрі
    const flow: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
    const height = new Array(n).fill(0);
    const excess = new Array(n).fill(0);
    const seen = new Array(n).fill(0);
    // черга реалізована масивом з рухомою головою — popFront за амортизований O(1)
    const excessVertices: number[] = [];
    let head = 0;
    height[s] = n;
    excess[s] = INF;

    const push = (u: number, v: number) => {
        const d = Math.min(excess[u], capacity[u][v] - flow[u][v]);
        flow[u][v] += d;
        flow[v][u] -= d;
        excess[u] -= d;
        excess[v] += d;
        if (d && excess[v] === d) excessVertices.push(v);
    };

    const relabel = (u: number) => {
        let d = INF;
        for (let i = 0; i < n; i++) {
            if (capacity[u][i] - flow[u][i] > 0) d = Math.min(d, height[i]);
        }
        if (d < INF) height[u] = d + 1;
    };

    const discharge = (u: number) => {
        while (excess[u] > 0) {
            if (seen[u] < n) {
                const v = seen[u];
                if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v]) push(u, v);
                else seen[u]++;
            } else {
                relabel(u);
                seen[u] = 0;
            }
        }
    };

    for (let i = 0; i < n; i++) if (i !== s) push(s, i);

    while (head < excessVertices.length) {
        const u = excessVertices[head++];
        if (u !== s && u !== t) discharge(u);
    }

    let result = 0;
    for (let i = 0; i < n; i++) result += flow[i][t];
    return result;
}

Go

const inf = 1000000000

func maxFlow(n int, capacity [][]int, s, t int) int {
	// flow[u][v] — поточний потік ребром (u, v); від'ємний на зворотному ребрі
	flow := make([][]int, n)
	for i := range flow {
		flow[i] = make([]int, n)
	}
	height := make([]int, n)
	excess := make([]int, n)
	seen := make([]int, n)
	// черга реалізована зрізом з рухомою головою head
	excessVertices := make([]int, 0)
	head := 0
	height[s] = n
	excess[s] = inf

	push := func(u, v int) {
		d := excess[u]
		if r := capacity[u][v] - flow[u][v]; r < d {
			d = r
		}
		flow[u][v] += d
		flow[v][u] -= d
		excess[u] -= d
		excess[v] += d
		if d != 0 && excess[v] == d {
			excessVertices = append(excessVertices, v)
		}
	}

	relabel := func(u int) {
		d := inf
		for i := 0; i < n; i++ {
			if capacity[u][i]-flow[u][i] > 0 && height[i] < d {
				d = height[i]
			}
		}
		if d < inf {
			height[u] = d + 1
		}
	}

	discharge := func(u int) {
		for excess[u] > 0 {
			if seen[u] < n {
				v := seen[u]
				if capacity[u][v]-flow[u][v] > 0 && height[u] > height[v] {
					push(u, v)
				} else {
					seen[u]++
				}
			} else {
				relabel(u)
				seen[u] = 0
			}
		}
	}

	for i := 0; i < n; i++ {
		if i != s {
			push(s, i)
		}
	}

	for head < len(excessVertices) {
		u := excessVertices[head]
		head++
		if u != s && u != t {
			discharge(u)
		}
	}

	result := 0
	for i := 0; i < n; i++ {
		result += flow[i][t]
	}
	return result
}

Тут ми використовуємо чергу excess_vertices, щоб зберігати всі вершини, які наразі мають надлишок. У такий спосіб ми можемо вибрати наступну вершину для операції проштовхування або підняття за константний час.

А щоб не витрачати забагато часу на пошук сусідньої вершини, до якої можна проштовхнути потік, ми використовуємо структуру даних під назвою current-arc (поточне ребро). По суті, ми перебиратимемо ребра в циклічному порядку і завжди зберігатимемо останнє використане ребро. У такий спосіб для певного значення мітки ми змінюватимемо поточне ребро лише $O(n)$ разів. А оскільки підняття вже займає $O(n)$ часу, ми не погіршуємо складність.

Відеоматеріали