 |
 |
 |
 |
|
 |
 |
71
Легко заметить, что задача о кратчайшем пути является частным случаем транспортной задачи в
сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно
присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины
положить нейтральными, а дугам присвоить неограниченные пропускные способности. Однако, как
правило, более рациональным оказывается использование конкретных свойств данной задачи и ре-
шение ее специальными (частными) методами. К их числу относится, например, метод Минти,
основные идеи которого мы изложим ниже.
Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в
ходе которого строится путь L=(s=i
0
,
i1, ..., i
p-1
, i
p
=t).
На предварительном (нулевом) этапе алгоритма:
формируется массив значений так называемых модифицированных длин
c
~
i,j
, которые перед
началом первой итерации полагаются равными с
i,j
?0
;
осуществляется отметка вершины i
0
= s числом m
i0
= 0.
Стандартная итерация включает этапы:
1°. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как
I
~
(на первой
итерации
I
~
={i
0
}). Для каждой вершины
i?
I
~
ищутся дуги, соединяющие ее с еще не
помеченными вершинами-потомками j, модифицированная длина которых
c
~
i,j
= 0. Найденные таким
способом вершины j помечаются числом m
j
= i, указывающим на «родителя». В том случае, когда сразу
несколько дуг, имеющих
c
~
i,j
= 0, заканчиваются в одной и той же вершине j, значение для ее пометки
выбирается произвольно.
Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь (i
0
, i1,...,
i
(p-1)
, i
p
), где
на чем алгоритм завершается.
В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой
вершины, то переходим к этапу 2.
2°. Преобразование значений модифицированных длин дуг. Для каждой вершины
i?
I
~
ищутся дуги,
соединяющие ее с еще не помеченными вершинами j, и находятся
Далее модифицированные длины всех дуг, которые соединяют отмеченные вершины с
неотмеченными (i?
I
~
,
j?
I
~
), уменьшаются на величину
в результате чего кратчайшие неиспользованные дуги получают нулевую модифицированную длину.
Затем происходит переход к следующей итерации.
Путь, построенный по методу Минти, будет кратчайшим. Это можно доказать с помощью индукции
по номеру итерации, на которой была помечена вершина t, или, что то же самое, по количеству дуг,
составляющих кратчайший путь. Если это произошло на первом шаге (что возможно только в случае,