Алгоритм Форда – Фолкерсона:

1. Зададим произвольный начальный поток, можно нулевой.

2. Вершину s пометим двойной пометкой: (0;∞). Первая пометка означает вершину, из которой получена пометка. Вторая нужна для подсчёта возможного увеличения потока. Дальнейшее помечивание по существу означает поиск пути из s в t.

3. Если в графе существует непомеченная вершина j , смежная с какой – то помеченной вершиной i, то в зависимости от того, как ориентирована связывающая их дуга, проводим прямую пометку (если дуга ведёт от i к j, и не насыщенная f_ij< с_ij) или обратную (если дуга ведёт от j к i, и c_ji>0). Прямая пометка: (+i, ∆j=c_ij-f_ij) Обратная пометка: (-i, ∆j=c_ij+f_ij)

4. Если на шаге 3 не удалось пометить вершины, выход из алгоритма, максимальный поток найден.

5. Если j=t, переход к 6, иначе переход к 3.

6. Этот шаг соответствует построенному пути из s в t, на котором возможно увеличение потока на величину ∆=min∆j, где ∆j – вторые метки всех вершин этого пути, кроме s. Начинаем с t и движемся по пометкам назад к источнику. На прямых дугах (1-я метка со знаком +) увеличиваем значение потока на ∆. На обратных дугах уменьшаем значение потока на ∆; если в этом случае fji - ∆.

Для нашего случая

Val f= 4+1+20=25.

1). Путь из s в t по которому поток может быть увеличен, состоит из прямых дуг, соединяющих вершины: s=1→3→t=4. Пометки указанных вершин: s=(0;∞)→(+1;∆ v₁=8-4=4)→ (+1;∆v₂ =9-1=8)→ t. Получили граф

Рис.2.

Путь из s в t (рис.2), на котором возможно увеличение потока построить не удалось. До стока t не дошли. Вершина t не может быть помечена, все входящие в нее дуги насыщены, поэтому поток не может быть увеличен.

Значит поток f (рис.2) максимален. Найдём минимальное сечение. Помеченные вершины: Мs={1,2,3}. Непомеченные вершины: Мt={4}. Прямые насыщенные дуги, идущие из Мs в Мt: e34, e14, e24, образуют минимальное сечение: e34· e14· e24. Величина этого сечения равна 4+1+20=25 и совпадает с величиной максимального потока f.

Найти минимальный путь из вершины вершины s в вершину t.

Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.

Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.

Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.

Для нахождения кратчайших путей от одной вершины до всех остальных, воспользуемся методом динамического программирования. Построим матрицу A_ij, элементы которой будут обозначать следующее: A_ij — это длина кратчайшего пути из s в i, содержащего не более j рёбер.

Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, A_i0 равно 0 при i = s, и +∞ в противном случае.

Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из  j  -1 ребра, к которому добавлено последнее ребро. Если для пути длины j  -1  все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

Помтроим матрицу A_ij.

	1	2	3
V1	8	--	----
V2	9	8+N	----
t	20	10	9+N

Длина кратчайшего пути из s в t равна 8, если N=0,равна 9, если N=1 и равна 10 во всех остальных случаях.