Алгоритм Эдмондса-Карпа

Контенус

Алгоритм Эдмондса-Карпа имеет время работы O(VE²), он быстрее, чем алгоритм Форд-Фулкерсон для плотных графов, т.е. график содержащий большое количество ребер (или дуг) в зависимости от количества вершин.

Алгоритм Эдмондса-Карпа идентичен алгоритму Форда-Фалкерсона, за исключением порядка поиска, используемого для определения возрастающего пути. Найденный путь должен быть кратчайшим путем с положительной пропускной способностью. Такой путь может быть найден ширина курса, предполагая, что все дуги имеют единичную длину. Обратите внимание, что длина возрастающего пути увеличивается с каждой итерацией.

Код из википедии
алгоритм ЭдмондсКарп
    вход: С[1..n, 1..n] (матрица емкости)
        Э[1..п, 1..?] (список соседей)
        с             (источник)
        ты             (Что ж)
    выход:ф             (максимальное значение расхода)
        Ф             (матрица, дающая действительный поток максимального значения)
    ф := 0 (начальный поток равен нулю)
    Ф:= множество(1..н, 1..н) ( остаточная мощность от u до v есть C[u,v] - F[u,v])
    навсегда
        m, P := Поиск в ширину (C, E, s, t, F)
        если м = 0
            ломать
        е := е + м
        (Бэктрек и поток нот)
        v := т
        пока v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u
    возвращаться (ж, ж)

алгоритм ШиротаFirstSearch
    вход: это ф
    выход: М[т]          (пропускная способность пути найдена)
        п             (родительская таблица)
    П:= множество(1..н)
    за а в 1..n P[u]:= -1 P[s]:= -2 (чтобы источник не был обнаружен повторно) 
    М:= множество(1..н) (мощность найденного пути к узлу)
    M[s] := ∞ Q := queue() Q.push(s)
    пока Q.size() > 0 u := Q.pop()
        за в в Европа]
            если C[u,v] - F[u,v] > 0 а также P[v] = -1 P[v] := u M[v] := min(M[u], C[u,v] - F[u,v])
                если v ≠ т Q.push(v)
                еще
                    возвращаться М[т], П
    возвращаться 0.П