электронный учебник

"Экономико-математические методы"

 

На главную страницу

Графы и сети. Потоки в сетях

В конец страницы

14.9.  ЗАДАЧА  О  КРАТЧАЙШЕМ  ПУТИ

       Частным случаем задачи об оптимальном потоке является задача построения   кратчайшего   пути   между  двумя   вершинами   пути.   Пусть  дан граф  ,   каждой   дуге   которого   поставлено  в  соответствие   число ,  называемое  длиной  дуги . Выделяются две вершины графа – s  и  t. Требуется найти путь наименьшей длины, ведущий из вершины s в вершину t. При этом длина произвольного пути  определяется следующим образом: .

 

 

 

 

 

 

 

Рисунок 14.8.

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

, где .

        Рассмотрим теперь сеть, вершина s которой является источником единичной интенсивности, t – стоком единичной интенсивности, остальные вершины – нейтральные. Дугам приписываются неограниченные пропускные способности, а стоимость перевозок по дуге полагается равной длине дуги. Для потока  в рассматриваемой сети

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

 

 

Назад     К началу страницы     Вперед