назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [ 71 ] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


71

которой вершины (например, вершины 1) до всех остальных вершин может быть применен алгоритм Дейкстры.

Первоначально присвоим вершине 1 постоянное значение метки 0. Затем каждой вершине, связанной с вершиной 1 только одной дугой, присвоим текущие метки, равные длинам этих дуг. Всем остальным вершинам (кроме вершины 1) присвоим значение метки со. Выберем вершину с самой маленькой временной меткой и сделаем ее постоянной.

Теперь предположим, что /-я вершина стала (к + 1)-й вершиной, получившей постоянную метку. Тогда скажем, что вершина / имеет (к + 1)-ю степень близости к вершине 1. В этот момент временные метки каждой вершины (например, вершины /) есть величина кратчайшего пути из вершины 1 до вершины /, который обязательно проходит через вершину кй степени близости к вершине 1. Для каждой вершины j\ которая имеет временную метку и связана с вершиной / дугой, заменяем текущее значение метки на

. Гтекущее значение метки вершины J

постоянное значение метки вершины / + Су.

Для иллюстрации алгоритма Дейкстры применим его для нахождения кратчайшего пути из вершины 1 в вершину 6 в задаче о передаче электроэнергии (рис. 8.2). Символ * будет обозначать постоянную метку. Метки будем представлять в виде массива, на /-м месте которого стоит текущее значение метки вершины /. Тогда первоначальный набор меток может быть представлен как o*43ooooooj.

Вершина 3 имеет наименьшее значение из всех временных меток. Поэтому ее метку помечаем как постоянную и получаем следующий набор меток 0* 4 3* 00 00 00 j.

Теперь пересчитываем значение временных меток для всех вершин, которые связаны дугой с вершиной 3. Таковой является только вершина 5. Согласно приведенному правилу имеем «новое значение метки вершины 5» = min(oo,3 + 3) = 6.

Теперь наименьшее значение временной метки имеет вершина 2, а следовательно, она становится постоянной. Получаем набор меток 0* 4* 3* 00 6 00j.



Рассмотрим вершины, связанные дугами с вершиной, получившей постоянную метку (вершина 2). Таковыми вершинами являются вершины 4 и 5. Необходимо пересчитать значения их временных меток. Эти значения находятся из соотношений min (сю, 4 + З) = 7 (для вершины 4) и

min (6, 4 + 2) = 6 (для вершины 5). Вершина 5 имеет теперь самое маленькое значение временной метки, поэтому оно становится постоянным, а массив меток принимает вид о* 4* 3* 7 6* оо j.

Так как только вершина 6 связана дугой с вершиной 5, получившей постоянную метку, значение временной метки пересчитывается только для вершины 6, а именно: min(oo, 6 + 2) = 8. Из всех временных меток

наименьшим является значение метки вершины 4, поэтому оно становится постоянным. Новый массив меток выглядит на данном этапе следующим образом: о* 4* 3* 7* 6* sj.

Так как только вершина 6 связана с вершиной 4, получившей постоянную метку, мы пересчитываем значение временной метки для вершины 6, а именно: min (8, 7 + 2) = 8. Теперь остается лишь пометить метку вершины 6 как постоянную, поскольку она имеет наименьшее значение среди временных меток, и получить окончательный набор меток

(0*4*3*7*6*8*).

Теперь осталось найти кратчайший путь из вершины 1 в вершину 6, применяя процедуру «обратного хода». Разница между значениями меток вершины 6 и 5 равняется 2, что соответствует длине дуги (5,6). Поэтому возвращаемся в вершину 5. Разница между значениями меток вершины 5 и 2 равняется 2, что соответствует длине дуги (2,5). Поэтому возвращаемся в вершину 2. Разница между значениями меток вершины 2 и 1 равняется 4, что соответствует длине дуги (1,2). Поэтому возвращаемся в вершину 1. Таким образом, кратчайший путь из вершины 1 в вершину 6 есть путь: 1-2-5-6. Заметим, что из вершины 5 мы могли бы вернуться в вершину 3 и в этом случае получили бы в качестве кратчайшего пути путь 1-3-5-6.

8.2,2. Сведение задачи о кратчайшем пути к транспортной задаче.

Если необходимо найти кратчайший путь в некоторой сети из вершины / в вершину у, то рассмотрим транспортную задачу, в которой необходимо перевезти продукт в количестве 1 из вершины / в вершину j. При этом стоимость перевозок между любыми двумя вершинами равна длине дуги



(в том случае, если дуга существует) и некоторому большому положительному числу М, если дуги между парой вершин не существует. Стоимость перевозок из вершины в саму себя равна нулю. Представим соответствующую транспортную задачу для рассмотренной задачи о кратчайшем пути в виде табл. 8.3.

Таблица 8.3

Вершины

Запасы

Спрос

Транспортная задача, представленная выше, имеет два оптимальных решения.

1)2 = 4 + 2 + 2 = 8, л:,2 = = = = = 1, остальные переменные равны 0. Это решение соответствует пути 1-2-5-6;

2)2 = 3 + 3 + 2 = 8, 13 = Х35 = = 22 = Х44 = 1, остальные переменные равны 0. Это решение соответствует пути 1-3-5-6.

8.3. Задача о максимальном потоке

Задачу о максимальном потоке можно представить как задачу линейного программирования.

Во многих сетевых задачах имеет смысл рассматривать дуги как некоторые коммуникации, обладающие определенной пропускной способностью. В этом случае, как правило, рассматривается задача о максимизации некоторого потока, направленного из выделенной вершины (источник) в некоторую другую вершину (сток). Задача такого типа называется задачей о максимальном потоке. Существует ряд специальных алгоритмов для решения данной задачи. Первоначально рассмотрим два примера подобных задач.

Пример. Нефтедобывающая компания перекачивает нефть от места добычи (вершина 1) на нефтеперерабатывающий завод (вершина 5). Участки нефтепроводов с их пропускными способностями (миллионы баррелей в час) изображены на рис. 8.4. Необходимо определить поток максимальной мощности из вершины 1 в вершину 5. 222

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [ 71 ] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]