Математические методы исследования операций в экономике (стр. 24 из 37)

3.2.3. Задача о кратчайшем пути. Классическим примером сетевых задач является определение кратчайшего пути между вершинами сети. Пусть задан граф (I, D, G), каждой дуге которого поставлено в соответствие число c_d, называемое длиной. Также пусть выделены две вершины графаs иt, и требуется найти путь наименьшей длины, ведущий из вершины s в вершину t.

Если в графе имеются «кратные» дуги, соединяющие одинаковые начало и конец, то достаточно оставить одну — с наименьшей длиной, а остальные отбросить. Таким образом, достаточно рассматривать задачу о кратчайшем пути для простогографа (I,D), в котором дуги определяются упорядоченными парами вершинd = (i,j). Тогда естественно путьL, идущий из вершины s в вершину t, задавать в виде упорядоченного набора вершин, через которые проходит данный путь:

а длины дуг обозначать как c_d = c_i,j.

Длина описанного выше произвольного пути L определяется по формуле

Легко заметить, что задача о кратчайшем пути является частным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины положить нейтральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и решение ее специальными (частными) методами. К их числу относится, например, метод Минти, основные идеи которого мы изложим ниже.

Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путьL=(s=i₀,i₁, ..., i_p-1, i_p=t).

На предварительном (нулевом) этапе алгоритма:

- формируется массив значений так называемых модифицированных длин

_i,j, которые перед началом первой итерации полагаются равными с_i,j ≥0;

- осуществляется отметка вершиныi₀ = s числом m_i0 =0.

Стандартная итерация включает этапы:

1°. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как

(на первой итерации

={i₀}). Для каждой вершиныi∊

ищутся дуги, соединяющие ее с еще не помеченными вершинами-потомками j, модифицированная длина которых

_i,j = 0. Найденные таким способом вершины j помечаются числом m_j =i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имеющих

_i,j = 0, заканчиваются в одной и той же вершине j, значение для ее пометки выбирается произвольно.

Если среди вновь помеченных вершин окажется вершинаt, то, значит, найден искомый путь (i₀, i₁,..., i_(p-1), i_p), где

на чем алгоритм завершается.

В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

2°. Преобразование значений модифицированных длин дуг. Для каждой вершиныi∊

ищутся дуги, соединяющие ее с еще не помеченными вершинами j, и находятся

Далее модифицированные длины всех дуг, которые соединяют отмеченные вершины с неотмеченными (i∊

,j∉

), уменьшаются на величину

в результате чего кратчайшие неиспользованные дуги получают нулевую модифицированную длину.

Затем происходит переход к следующей итерации.

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

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

Отметим, что описанный алгоритм пригоден для построения кратчайших путей на неориентированных графах.

Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рис. 3.5.

На предварительном этапе вершина 1 отмечается числом m₁ = 0, а модифицированные длины совпадают с заданными длинами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем ∆ = min{

_1,2,

_1,3}=2 и вычитаем ее из

_1,2,

_1,3. После преобразования имеем

_1,2 = 0,

_1,3 = 1.

Итерация 2. Помечаем вершину 2 m₂ = 1 (см. рис. 3.6). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Из чего определяем ∆ = min{

_1,3,

_2,3,

_2,4,

_2,5}=1 ипосле соответствующего преобразования имеем

Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m₃ = 1 (рис. 3.7). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются вершины 4,5. Из чего определяем ∆ = min{

_2,4,

_2,5,

_3,4,

_3,5}=1 и после преобразования имеем

_2,4 =8,

_2,5 =0,

_3,4 =3,

_3,5 =5.

Итерация 4. Помечаем вершину 4 m₄ =2 (см. рис. 3.8). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются вершины 5,6. Из чего определяем ∆ = min{

_2,5,

_3,5,

_4,5,

_4,6}=3 и после преобразования имеем

_2,5 =5,

_3,5 =0,

_4,5 =0,

_4,6 =5.