Постановка задачи. В приложениях теории графов для сетей с одним источником s и одним стоком r большое значение имеет группа задач о кратчайшей (или максимальной) цепи из истока

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

Формулировка задачи имеет следующий вид:

задана сеть - G = {N, A}; для всех дуг из A определена обобщенная стоимость c_ij прохождения единицы потока по дуге, которая в реальных задачах в зависимости от выбранного критерия оптимальности может быть либо временем выполнения каких-либо процессов в моделируемом объекте, либо расстоянием, либо величиной, имеющей денежное выражение и связанной со стоимостью. Для фиктивных дуг, задающих только последовательность узлов, c_ij = 0, для пары узлов i и j, не соединенных дугой, c_ij = .

Интенсивности истока и стока: d_s = 1, d_r = -1; для остальных узлов сети

d = 0.

Требуется найти цепь [ s,..., r ] с оптимальной (минимальной или максимальной) суммарной обобщенной стоимостью c_sr всех входящих в нее дуг.

Эта задача может быть представлена, как задача дискретного программирования:

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