Какой алгоритм мне следует использовать, чтобы найти минимальный поток на орграфе, где есть нижние границы, но не верхние границы потока?

В отсутствие верхних границ самый простой способ - самый простой для реализации, понимания и достаточно эффективный - найти минимальный поток графа:

1. Найдите допустимый поток, то есть поток, который удовлетворяет правилам потока и нижним границам потока, но не обязательно является минимальным потоком. Этого можно достичь, выполняя обход графа в глубину, отслеживая текущий путь по мере того, как мы проходим, и при посещении ранее обнаруженного узла или целевого узла t, увеличивая поток на текущем пути с максимальным нижним значением. -связка неудовлетворенных ребер на текущем пути до t.

2. Превратите возможный расход в минимальный, решив задачу о максимальном расходе. Вам нужно найти максимальный поток на графике, который имеет пропускную способность, равную потоку (e) - нижняя граница (e), где поток (e) означает поток из допустимого потока. Этот максимальный расход, вычтенный из допустимого расхода, будет минимальным расходом.

Вариант вышеизложенного также может быть выполнен в случае, когда граф также имеет верхние границы для потока. В этом случае шаг 1. более сложен, но его можно решить, выполнив начальное вычисление максимального потока на специально построенном графе.

Написать решатель нетривиально.

См. Библиотеку LEMON (часть COIN-OR). Он имеет ряд высоко оптимизированных алгоритмов для решения проблемы минимальной стоимости потока. Вы можете выбрать, какой алгоритм лучше всего работает с вашими данными.

См. http://lemon.cs.elte.hu/trac/lemon для получения информации о ЛИМОН.

См. http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html для получения подробной информации о минимальной стоимости сетевого потока.

Добавьте все «нижние границы» потоков на каждом ребре: это все равно потребуется для любого допустимого решения.

Для каждого узла n в топологическом порядке (т. Е. По ребрам) от приемника t, если сумма S- того, что идет по ребру, больше, чем сумма S+ того, что выходит, тогда добавьте поток S+ - S- на всех ребрах кратчайший путь между s и t (для повышения эффективности составьте список кратчайших путей).

Затем у вас есть «минимальное» задание (в том смысле, что оно необходимо для каждого возможного решения), например, S+ - S- неотрицательно на каждом узле, а минимальная пропускная способность удовлетворяется на каждом ребре.

Затем проблема сводится к проблеме с несколькими потоками на той же структуре графа:

• источник тот же;
• нет ограничения мощности;
• каждый узел, где S+ - S- строго положителен, становится стоком с требуемым потоком S+ - S-.
• начальный сток (который имел требуемый поток F) становится стоком с потоком F - S-, если F-S- неотрицательный (в противном случае начальное ограничение будет удовлетворено любым решением).

Изменить: для вашей проблемы график выглядит так

     x1 -- x2
   /   \     \
 s      \     t
   \     \   /
     x3 -- x4

с минимальной пропускной способностью 1 для каждого ребра, и я полагаю, что на приемнике t не требуется минимального потока.

Сначала присвойте 1 каждому ребру.

Разница S+ - S- для каждого узла (кроме, конечно, s и t):

x1: 1
x2: 0
x3: 0
x4: -1

единственный отрицательный - для x4; мы добавляем 1 к каждому ребру на кратчайшем пути от x4 до t, в этом случае к ребру (x4, t).

Теперь S+ - S- неотрицательно для каждого узла и положительно только для x1; проблема сводится к проблеме с несколькими потоками (в этом случае это простая проблема с потоком), где запрошенный поток равен 1 в x1, а источник по-прежнему s.