Анализ оптимального плана Из 1-го склада необходимо груз направить в 1-й магазин (10 ед

Придадим вершине s’ значение потенциала 0.
Вычислим потенциалы для других вершин:
для вершины 6:0+6=6,
для вершины 4:0+7=7,
для вершины 5:6+8=14,
для вершины 3:max{14+9=23, 6+8=14, 0+15=15, 7+5=12}=23,
для вершины 2:max{23+10=33, 7+6=13}=33,
для вершины 1:max{14+4=18, 23+5=28}=28,
для вершины s’:max{28+12=40, 23+22=45, 33+10=43}=45.
Таким образом, максимальный поток составляет 45, проходит через вершины s, 3, 5, 6, s’.
2