Алгоритм Форда. Максимальная пропускная способность графа.
Рассмотрим алгоритм Форда на примере графа изображенного на рис.1. Допустим, у нас исток будет в 1 узле, а сток в 4 узле. Алгоритм можно разбить на три шага:
Поиск произвольного пути из истока к стоку. Если такого нет, то выдаем значение максимальной пропускной способности и алгоритм завершается.
Нахождение в выбранном пути ребра с минимальной пропускной способностью. Прибавляем значение этого ребра к пропускной способности, которая в начале выполнения алгоритма равна 0.
Вычитание из всех значений ребер пути, значения минимального ребра этого пути. При этом само ребро обратиться в 0 и его уже нельзя учитывать в дальнейшем. Далее продолжаем с шага 1.
В начале у нас пропускная способность равна 0 (P=0).Допустим, мы нашли путь из истока 1 в сток 4 через вершины 2 и 3, т.е. весь путь можно записать как (1-2-3-4). В этом пути минимальное ребро соединяет вершины 2 и 3, его значение 5, увеличиваем пропускную способность на 5 (Р=5). Вычитаем 5 из ребер соединяющих вершины 1 и 2, 2 и 3, 3 и 4. Из исходного графа у нас выпало ребро соединяющее вершины 2 и 3. Получился граф изображенный на рис.2. В этом графе снова ищем произвольный путь из 1 в 4. Нашли (1-2-5-4), где минимальное ребро соединяет 2 и 5, его значение 6. Увеличиваем пропускную способность на 6 (P=5+6=11). Вычитаем 6 из всех ребер пути, выпадает ребро 2-5 (рис.3). На следующем шаге находим путь (1-6-5-4), минимальное ребро 1-6 равно 7, тогда P=11+7=18. Вычитаем из ребер пути 6, при этом выпадает ребро 1-6 и граф распадается на две компоненты рис.4. Мы не находим пути из истока в сток и алгоритм завершается. Получаем максимальную пропускную способность из 18.
Рассмотрим алгоритм Форда на примере графа изображенного на рис.1. Допустим, у нас исток будет в 1 узле, а сток в 4 узле. Алгоритм можно разбить на три шага:
В этом графе снова ищем произвольный путь из 1 в 4. Нашли (1-2-5-4), где минимальное ребро соединяет 2 и 5, его значение 6. Увеличиваем пропускную способность на 6 (P=5+6=11). Вычитаем 6 из всех ребер пути, выпадает ребро 2-5 (рис.3). 
На следующем шаге находим путь (1-6-5-4), минимальное ребро 1-6 равно 7, тогда P=11+7=18. Вычитаем из ребер пути 6, при этом выпадает ребро 1-6 и граф распадается на две компоненты рис.4. 
Мы не находим пути из истока в сток и алгоритм завершается. Получаем максимальную пропускную способность из 18.
