Поток минимальной стоимости, Форд-Фалкерсон.

Описание Области

подробнее…

Постановка задачи

Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.

Дано:

  1 источник – завод (склад), с которого начинается передача потока (перевозка товара).

  1 сток – магазин (склад), которым заканчивается передача потока (перевозка товара).

  Набор промежуточных вершин (складов), через которые проходит поток (перевозятся товары).

  Набор дуг (дорог), соединяющих вершины графа. Каждой дуге сопоставляется 2 характеристики: пропускная способность дуги и стоимость дуги.

  Величина потока (объем товара) который требуется передать от источника к стоку.

Требуется:

Найти поток минимальной стоимости заданной величины от источника к стоку. Т.е. самый дешевый способ перевозки заданного объема товара от завода до магазина.

кратко