Обобщенный алгоритм Дейкстры
ОБОБЩЁННЫЙ АЛГОРИТМ ДЕЙКСТРЫ
1. Постановка задачи.
Рассматриваются неориентированные простые графы (напомним, что простым называется граф, любые две вершины которого соединены не более чем одним ребром). С каждым ребром (x, y) заданного графа G ассоциировано неотрицательное число l(x, y), называемое весом или длиной ребра (содержательно это число может быть расстоянием, стоимостью, пропускной способностью и т.д; здесь используется наиболее распространённый термин «длина»). Удобно считать, что любые две вершины соединены ребром, но для реально отсутствующих рёбер l(x, y) = ¥.
С каждым путём P в графе G связано неотрицательное
число L(P) (далее называемое длиной
пути P). Для любых
двух вершин графа G минимальным
или кратчайшим путём называется лю-бой соединяющий
их путь P с минимальной
длиной L(P). Подробнее:
путь P, соединяющий
заданные вершины a и b, называется
минимальным или кратчайшим, если для
любого другого пути P', соеди-няющего
те же самые вершины a и b, верно, что L(P) ≤ L(P' ).
Основной задачей, рассматриваемой и решаемой в настоящей работе, является следующая: Для заданной вершины a найти кратчайшие пути, соединяющие a со всеми вершинами графа G. В том случае, когда длина пути считается равной сумме длин всех его рёбер, данная задача была ре-шена около полувека тому назад выдающимся современным математиком Дейкстрой (Dijkstra). В данном материале будет изложена модификация его алгоритма, позволяющая практически при той же конструкции найти минимальные пути для достаточно широкого класса функций длины (выража-ющих зависимость обобщённой длины L(P) от длин входящих в путь P рёбер). Описанию рассмот-ренного класса функций посвящён раздел 2. В 3-ем разделе излагается обобщённый алгоритм Дейкс-тры (ОАД) и доказывается его корректность. В 4-ом разделе проиллюстрировано применение ОАД для классического и минимаксного случая. В 5-м разделе рассмотрены реальные задачи, в которых использование минимаксной функции длины является естественным и целесообразным.
2. Обобщённая длина
Введём необходимые понятия и обозначения. Пусть P – любой путь, соединяющий вершины a и с и пусть вершина b является предпоследней (перед с) вершиной на пути P. Обозначим часть пути P от a до b через P(a, b), а весь путь обозначим через P(a, b, с). Все вершины a, b и с считаются раз-личными. Далее рассматриваются функции длины L(P), для которых выполнены следующие условия.
1. Для путей P, не содержащих рёбер (т.е. состоящих из одной вершины), L(P) = 0.
2. Для каждого пути P, состоящего из единственного ребра (a, b),
L(P) = Φ(l(a, b)),
где Φ(x) - неотрицательная функция от одной неотрицательной переменной.
3. Существует неотрицательная функция F(x, y) от двух неотрицательных переменных, такая, что для всех путей P, содержащих хотя бы два ребра
L(P(a, b, с)) = F(L(P(a, b), l(b, c)).
4. В тех же обозначениях
L(P(a, b)) ≤ L(P(a, b, с)).
5. Функции Φ(x) и F(x, y) являются неубывающими по всем переменным.
6. Φ(∞) = ∞, F(∞,y) = F(x,∞) = F(∞,∞ ) = ∞.
Условие 1 является совершенно естественным. Условие 2 выражает длину пути, состоящего из одного ребра, через длину самого ребра. Условие 3 означает, что длина пути P(a, b, с) однозначно выражается через длину этого же пути P(a, b) без последнего ребра, и длины последнего ребра l(b, c). Условие 4 выражает естественное требование: длина части пути не может превосходить длину всего пути. Условие 5 выражает естественное требование к зависимости длины пути от длин его частей: при увеличении длины части длина всего пути не может уменьшиться. Условие 6 также является естественным, если считать, что любые две вершины соединены ребром, но при отсутствии реального ребра считать длины таких фиктивных рёбер равными ∞.
Условия 1 – 6 играют центральную роль в дальнейших конструкциях. Остановимся на этом подробнее, для чего рассмотрим некоторые примеры функций длины L(P).
1. Длина пути равна сумме длин всех его рёбер («классический» случай). В этом случае F(x, y)= x + y, Φ(x) = x и выполнение условий 1 – 6 очевидно.
2. Длина пути равна
максимальной длине ребра
3. Длина пути L(P) определяется формулой
L(P) = f(Σl(x, y)),
где сумма берётся по всем рёбрам, входящим в путь P, и f – строго возрастающая функция одной неотрицательной переменной. Покажем, что в этом случае функция F(x,y), удовлетворяющая (1), (2), (3) и (4), существует. Действительно, можно положить
F(x, y) = f (f –1(x) + y), Φ(x) = f(x).
Формулы (1), (2), (3) и (4) прямо следует из (5) и (6).
Заметим, что длина пути L(P), равная корню квадратному из суммы длин всех его рёбер, как и длина пути L(P), равная квадрату суммы длин всех его рёбер, укладываются в рассматриваемый случай.
4. Длина пути равна среднему арифметическому длин всех рёбер, входящих в путь. В этом слу-чае
L(P(a, b, с)) = L(P(a, b))• + l(b, c)• ,
где n – число рёбер в пути P(a, b, с). Это значит, что представления (2) в рассматриваемом случае не существует, поскольку в формулу (7) в явном виде входит зависимость от n.
Назовём функцию длины L(P), для которой выполнены условия 1 – 5, длиной Дейкстры или Дейкстровой длиной. В трёх первых случаях длина была Дейкстровой, а в 4-м случае – нет.
Имеют место
Утверждение 1. Пусть P(a, b, с) – некоторый путь, P(a, b) – его начальный участок, P0(a, b) – другой путь из a в b, такой что L(P0(a, b)) ≤ L(P(a, b)). Тогда
L(P0(a, b, с)) ≤ L(P(a, b, с)).
Доказательство непосредственно следует из представления (2) и условия 5 ■
Утверждение 2. Пусть P – любой путь, соединяющий вершины a и с и пусть вершина b являет-ся любой промежуточной вершиной на пути P. Тогда
L(P(a, b)) ≤ L(P(a, b, с)).
Доказательство. Разница между формулами (9) и (3) состоит в том, что в (3) промежуточная вершина b является предпоследней, а в (9) – любой. Доказательство получается последовательным применением (3), начиная с предпоследнего места и кончая заданной позицией. Подробнее: зануме-руем все вершины на пути P: x0, x1, …, xk, …, xn–1, xn. В силу (3) имеем
L(P(x0, xn–1)) ≤ L(P(x0, xn–1, xn)).
Далее, аналогично
L(P(x0, xn–2)) ≤ L(P(x0, xn–2, xn–1)),
……………………………………
L(P(x0, xk)) ≤ L(P(x0, xk, xk+1)),
откуда и следует требуемое равенство:
L(P(x0, xk)) ≤ L(P(x0, xk, xn)) ■
3. Обобщённый алгоритм Дейкстры
Предлагаемый алгоритм основан на продолжении путей через последнюю вершину, для кото-рой уже точно известны и минимальный путь, и его длина. Он практически совпадает с классическим алгоритмом Дейкстры, отличаясь только деталями.
Идея алгоритма построения дерева минимальных путей и определения их длин, предложенного в 1959г. Е. Дейкстрой, такова. На каждом этапе одна новая вершина включается в множество S отме-ченных вершин, для которых минимальные пути найдены. Обозначим эту только что включённую в множество S вершину через w. Тогда на следующем этапе к множеству S добавляется вершина v с са-мым коротким путем из а, проходящим по множеству S, предпоследней вершиной на котором явля-ется w.
В работе предлагается алгоритм именно такой структуры. Отличие его от классического состо-ит в возможности находить кратчайшие пути при описанной выше функции длины (зависимости длины пути от длин входящих в него рёбер) достаточно общего вида (см раздел 2). При изложении алгоритма, как и при доказательстве его корректности, использовались книги [1, 2].
Введём необходимые понятия и обозначения. Пусть G = áV, Eñ – неориентированный граф с множеством вершин V и множеством рёбер E. Понятия длины ребра и пути были введены в разделе 1. Ищутся минимальные пути из фиксированной вершины а во все остальные вершины. Если для каждой вершины vÎV, достижимой из а, зафиксировать один кратчайший путь из а в v, то получив-шийся граф будет представлять ориентированное дерево с корнем а. Это дерево называется деревом минимальных путей из а.
Предполагается, что задан неориентированный граф G = áV, Eñ, содержащий n вершин. Без ог-раничения общности можно считать, что все вершины задаются номерами от 0 до n–1 и что началь-ная вершина имеет номер 0. Длина ребра между вершинами i и j обозначена через l(i, j); если нет реб-ра, соединяющего эти вершины, то l(i, j) = ¥. Предполагается, что заданы функция Φ(x) одной пере-менной, функция F(x, y) двух переменных и функция длины L, удовлетворяющие условиям 1 – 6.
Обобщённый алгоритм Дейкстры (ОАД). Алгоритм находит кратчайшие пути из начальной вершины 0 во все остальные вершины графа. Для реализации алгоритма вводятся пять одномерных массивов:
1) Массив P вершин, уже получивших постоянные метки (для этих вершин кратчайшие пути из начальной вершины уже известны, а постоянная метка – это длина кратчайшего пути из начальной вершины в данную вершину). Длина массива P равна n.
2) Массив M постоянных меток (на i-ом месте стоит длина кратчайшего пути из начальной вершины в вершину P[i]). Длина массива M равна n.
3) Массив T вершин, ещё не получивших постоянных меток. Длина массива T равна n–1.
4) Массив W временных меток (на i-ом месте стоит длина текущего пути из вершины 0 в вер-шину T[i]). Длина массива W равна n–1.
5) Массив PR номеров вершин, непосредственно предшествующих вершинам 0, 1, …, n–1 в текущих путях (после завершения работы алгоритма все пути будут кратчайшими) из вершины 0. В массиве PR на i-ом месте стоит вершина PR[i], непосредственно предшествующая вершине i. Длина массива PR равна n.
В процессе работы алгоритма происходит заполнение всех массивов. Позиции в массивах, значения которых в данный текущий момент могут быть произвольными, заполняются знаком •.
Инициализация. Положим
P[0] = 0 (в массиве вершин, получивших постоянные метки, на 0-м месте стоит начальная вершина 0);
M[0] = 0 (длина кратчайшего пути от вершины 0 до самой себя равна 0);
T[i] = i+1, i = 0, 1, …, n–2 (все вершины, кроме начальной, образуют массив T);
W[i] = ¥, i = 1, …, n–1 (временные метки всех вершин, кроме начальной, инициализируют-
ся бесконечностью);
PR[0] = −1 (у начальной вершины 0 нет предшествующей).
В результате инициализации массив P включает (на нулевом месте) одну вершину 0, для которой минимальный путь из неё же самой в неё же саму является пустым (не содержит рёбер), а его длина равна 0 в соответствие с условием 1 из раздела 2. Временные метки (т.е. текущие длины путей) равны ¥ для всех остальных вершин, в том числе и тех, которые соединены ребром с вершиной 0.
На шагах 1, 2, … , n ровно для одной вершины определяется путь минимальной длины. Суть операций на каждом шаге – модификации пяти указанных массивов (массив PR, вообще говоря, на некоторых шагах может не изменяться).
Шаг 1
1. Для i = 0, 1, …, n–1 выполняются следующие действия:
1.1. W’[i] = Φ(l(0,T[i])
(именно здесь и только здесь используется функция Φ длины пути, состоящего из одного ребра, соединяющего вершину 0 с вершиной T[i]);
1.2. Если W’[i] < ¥, то W[i] = W’[i] и PR[T[i]] = 0 (в том случае, когда ребро из начальной вершины 0 в вершину T[i] реально присутствует, временная метка вершины T[i] становится равной длине пути, состоящего из одного этого ребра, а предшествующей вершиной – на-чальная вершина 0).
2. Выбираем в массиве W временных меток минимальную (если их несколько, то можно взять любую из них). Обозначим номер выбранного минимума в массиве W через im, а его значение – через vm.
3. Положим VC = T[im]. Таким образом, VC – это вершина с минимальной временной меткой, равной vm.
4. Положим P[1] = VC, M[1] = vm. Таким образом, число вершин, имеющих постоянную метку, стало равным 2. Сама эта вершина занесена в массив P, а её постоянная метка – в массив M на 1-ую позицию (следующую за 0-ой).
5. Удалим из массивов T и W элементы с номером im (сдвинув все элементы с бóльшими индек-
сами на одну позицию влево). Таким образом, число вершин, имеющих временную метку, стало меньше на единицу.
Шаг k (k > 1).
1. Для i = 0, 1, …, n–k–1 выполняются следующие действия:
1.1. W’[i] = F(M[k–1], l(P[k–1],T[i])
(именно здесь и только здесь используется функция F, задающая длину пути, состоящего из двух участков: кратчайшего пути из вершины 0 в вершину P[k–1], имеющего длину M[k–1], и одного ребра, соединяющего вершину P[k–1] с текущей вершиной T[i]);
1.2. Если W’[i] < W[i], то W[i] = W’[i] и PR[T[i]] = P[k–1] (в том случае, когда путь 0→P[k–1] →T[i] оказывается короче, чем ранее имевшийся путь из 0 в T[i], временная метка вершины T[i] становится равной длине этого пути 0→P[k–1] →T[i], а предшествующей T[i] вершиной объявляется P[k–1]).
2. Выбираем в массиве W временных меток минимальную (если их несколько, то можно взять любую из них). Обозначим номер выбранного минимума в массиве W через im, а его значение – через vm.
3. Положим VC = T[im]. Таким образом, VC – это вершина с минимальной временной меткой, равной vm.
4. Положим P[k] = VC, M[k] = vm. Таким образом, число вершин, имеющих постоянную метку, стало равным k +1. Сама эта вершина занесена в массив P, а её постоянная метка – в массив M на k-ую позицию.
5. Удалим из массивов T и W элементы с номером im (сдвинув все элементы с бóльшими индек-
сами на одну позицию влево). Таким образом, число вершин, имеющих временную метку, стало меньше на единицу, чем было.
Построение кратчайших путей. Число шагов в рассматриваемом алгоритме равно n–1. После выполнения (n–1)-го шага все вершины оказываются записанными в массив P. Сам минимаксный путь из начальной вершины 0 в любую другую вершину a строится следующим образом: вершиной, предшествующей a на искомом пути, является вершина b = PR[a]; вершиной, предшествующей b на искомом пути, является вершина с = PR[b] и т.д., вплоть до начальной вершины 0. Сам требуемый путь из 0 в a состоит из тех же вершин в обратном порядке.
Основным утверждением данного раздела является
Теорема 1. Если функция длины является Дейкстровой, то ОАД находит кратчайшие пути между начальной вершиной 0 и всеми остальными вершинами.
Доказательство. Введём новые обозначения:
Z(i,k) – метка (временная или постоянная) вершины i, полученная на шаге k. Это значит, что именно это значение используется в пункте 1.2 на шаге k+1 при вычислении новой метки. Обозначим через ki номер шага, на котором метка вершины i становится постоянной, а через ik номер вершины, получившей постоянную метку на шаге k; в ранее введённых обозначениях ik = P[k].
Лемма 1. Для любых i, k1 и k2 [k1 < k2] → [Z(i,k1) ≥ Z(i,k2)].
Лемма 1 непосредственно следует из правила изменений метки в пункте 1.2 1-го и k-го шагов ОАД ■
Доказательство теоремы 1 будем проводить по индукции. Будем предполагать, что найденные ОАД вплоть до шага k пути из начальной вершины 0 в вершины P[i] (i = 1, …, k) являются кратчай-шими (они извлекаются из массива PR), и их длины равны M[k]). Базис индукции при k = 1 очевиден (в качестве вершины с номером 1 выбирается вершина, ближайшая к начальной вершине 0).
Лемма 2. Пусть для числа k выполнено предположение индукции. Рассмотрим любой путь вида P(0,s,t) (т.е. путь из 0 в t, на котором вершина s является предпоследней) и число k’, такие, что:
а) вершина s получила постоянную метку не позднее, чем на шаге k;
б) вершина t не получила постоянной метке вплоть до шага k;
в) k < k’.
Тогда имеет место неравенство
Z(t,k’) ≤ L(P(0,s,t)).
Доказательство. По условию леммы, путь P(0,s,t) состоит из двух участков: участка P0(0,s), соединяющего вершину 0 с вершиной s, и ребра (s,t). По условию а) леммы вершина s получила пос-тоянную метку ks на одном из первых k шагов, откуда по предположению индукции построенный ОАД путь P* из 0 в s, длина которого равна постоянной метке Z(s,ks), является кратчайшим. В силу этого предположения любой другой путь из 0 в s, в том числе и путь P0(0,s), не могут быть короче, чем путь P*. Поскольку длина пути P* по построению равна метке Z(s,ks), то для длины L(P0(0,s)) пути P0(0,s) имеет место неравенство
Z(s,ks) ≤ L(P0(0,s)).
Вернёмся к пути P(0,s,t), состоящему из двух частей: P0(0,s) и ребра (s,t). В силу формулы (2)
L(P(0,s,t)) = F(L(P0(0,s)), l(s,t)).
Учитывая, что функция длины F(x,y) является монотонно неубывающей по каждому аргументу, из (13) и (12) получаем
F(Z(s,ks),l(s,t)) ≤ L(P(0,s,t)).
Левая часть неравенства (14)
с точностью до обозначений совпадает
с правой частью равенства (10b) F(M[k–1], l(P[k–1],T[t]),
использующегося при вычислении нового значения временной метки вершины t на шаге ks+1, так как по условию б) леммы вершина t вплоть до шага ks не получила постоянной метки (в рассматрива-емом здесь случае в формуле (15) k–1 = ks, P[k–1] = s, M[k–1] = Z(s,ks) и T[i] = t). По описанию пунк-та 1.2 алгоритма, с учётом используемых обозначений имеем
Z(t,ks+1) = min{Z(t,ks), F(Z(s,ks),l(s,t))},
откуда
Z(t,ks+1) ≤ F(Z(s,ks),l(s,t));
(16) и (14) влекут
Z(t,ks+1) ≤ L(P(0,s,t)).
Теперь в силу леммы 1 для любого k’, бóльшего ks, из (17) следует
Z(t,k’) ≤ L(P0(0,s)),
что совпадает с требуемым неравенством (11) при указанных k’.
Так как по построению ks ≤ k, то из того, что (11) верно для всех k’ > ks следует, что (11) верно и для всех k’ > k, что и завершает доказательство ■
Перейдём теперь непосредственно к доказательству теоремы 1 по индукции. Предположим, что число k удовлетворяет требуемым условиям: найденные ОАД вплоть до шага k пути из началь-ной вершины 0 в вершины P[i] (i = 1, …, k) являются кратчайшими, и их длины равны соответствую-щим меткам M[k]). Пусть r – k-ая вершина, получившая постоянную метку (обозначенную через Z(r,k)). Перейдём к следующему значению k+1. Предположим, что для него теорема неверна: на шаге k+1 ОАД присваивает постоянную метку некоторой вершине u,но путь Р(0,r,u) длины Z(u,k+1) не яв-ляется кратчайшим путём из 0 в u. Это означает, что есть некоторый другой путь Р(0,u) из 0 в u, для которого
L(Р(0,u)) < Z(u,k+1).
Рассмотрим путь Р(0,u) подробнее. Этот путь начинается в вершине 0, получившей постоянную мет-ку на 0-м шаге. Поскольку вершина u по построению получила постоянную метку только на (k+1)-ом шаге, то на этом пути найдутся две соседние вершины s и t, такие, что:
а) вершина s получила постоянную метку не позднее, чем на шаге k;
б) вершина t не получила постоянной метке вплоть до шага k.
Положим k’ = k+1 и рассмотрим путь P(0,s,t), либо являющийся начальным участком пути Р(0,u), ли-бо целиком с ним совпадающим. В обоих случаях
L(P(0,s,t)) ≤ L(Р(0,u))
(см. утверждение 2 в разделе 2).
В силу условий а) и б) число k’ = k+1 и путь P(0,s,t) удовлетворяют условиям леммы 2. В силу этой леммы
Z(t,k+1) ≤ L(P(0,s,t)).
Неравенства (18) – (20) влекут неравенство
Z(t,k+1) < Z(u,k+1).
Напомним, что по построению на (k+1)-ом шаге ОАД присваивает постоянную метку вершине u. По описанию пункта 2 общего шага алгоритма это значит, что метка Z(u,k+1) является минимальной. Но это противоречит неравенству (21), что и завершает доказательство теоремы 1 ■
В рассмотренном алгоритме существенна сама возможность выражения длины пути из 0 в s, продолженного ребром (s,t), через длину L(P(0,s)) начального участка P(0,s) и длины ребра l(s, t) по формуле (2).
4. Классические и минимаксные и кратчайшие пути
В данном разделе более подробно рассмотрены две функции длины: классическая, когда за дли-ну пути принимается сумма длин его рёбер, и минимаксная, когда за длину пути принимается длина его самого длинного ребра. Обе эти функции длины удовлетворяют условиям 1 – 6 из раздела 2 и, следовательно, к ним применим ОАД, описанный в разделе 3. В данном разделе подробно излагают-ся примеры, иллюстрирующие применение ОАД в обоих случаях. ОАД для этих (как и для любых других конкретных функций длины) отличаются только формулами пересчёта меток (10а) и (10b); в остальном они полностью совпадают.
4.1. Алгоритм Дейкстры в классическом случае. Рассматривается традиционное понятие длины пути как суммы длин всех входящих в него рёбер. Формулы пересчёта меток (10а) и (10b) принимают вид
W’[i] = l(0,T[i]), W’[i] = M[k–1] + l(P[k–1],T[i])
Проиллюстрируем ОАД на примере показанного на рис. 1 графа. В данном графе число вершин n = 6. При указанной на рисунке нумерации вершин после выполнения инициализации имеем:
Рис. 1
P = á0,•,•,•,•,•ñ;
M = á0,•,•,•,•,•ñ;
T = á1,2,3,4,5ñ;
W = á¥,¥,¥,¥,¥ñ;
PR = á–1,•,•,•,•,•ñ.
Для 1-го шага (k = 1) формула (10а) принимает вид W’[i] = l(0,T[i]), откуда
W[0] = min{¥, 1} = min{¥,1} = 1;
W[1] = min{¥, 5} = min{¥,5} = 5;
W[2] = min{¥, ¥} = min{¥,¥} = ¥;
W[3] = min{¥, ¥} = min{¥,¥} = ¥;
W[4] = min{¥, ¥} = min{¥,¥} = ¥
Заметим, что новая метка стала меньше старой при i = 0, i = 1. Поэтому в соответствии с пунктом 1.2 1-го шага алгоритма получаем
PR[T[0]] = PR[1] = P[0] = 0;
PR[T[1]] = PR[2] = P[0] = 0.
Далее, минимальным значением в новом массиве W = á1,5,¥,¥,¥ñ является число 1, стоящее на 0-м месте, т.е. im = 0, vm = 1. В соответствии с пунктом 3, VC = T[im] = T[0] = 1. В соответствии с пунктом 4 получаем P = á0,1,•,•,•,•ñ, M = á0,1,• ,•,•,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á2,3,4,5,•ñ, W = á5,¥,¥,¥,•ñ. Таким образом, после выполнения 1-го шага получаем следующие 5 массивов:
P = á0,1,•,•,•,•ñ;
M = á0,1,•,•,•,•ñ;
T = á2,3,4,5,•ñ;
W = á5,¥,¥,¥,•ñ;
PR = á–1,0,0,•,•,•ñ.
Для 2-го шага (k = 2) формула (10b) принимает вид W’[i] = M[1] + l(P[1],T[i]), откуда
W[0] = min{5, 1+8} = min{5,9} = 5;
W[1] = min{¥, 1+10} = min{¥,11} = 11;
W[2] = min{¥, 1+6} = min{¥,7} = 7;
W[3] = min{¥, 1+¥} = min{¥,¥} = ¥.
Заметим, что новая метка стала меньше старой при i = 1, i = 2. Поэтому в соответствии с пунктом 1.2 k-го шага алгоритма при k = 2 получаем
PR[T[1]] = PR[3] = P[1] = 1;
PR[T[2]] = PR[4] = P[1] = 1.
Далее, минимальным значением в новом массиве W = á5,11,7,¥,•ñ является число 5, стоящее на 0-м месте, т.е. im = 0, vm = 5. В соответствии с пунктом 3, VC = T[im] = T[0] = 2. В соответствии с пунктом 4 получаем P = á0,1,2,•,•,•ñ, M = á0,1,5,•,•,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á3,4,5,•,•ñ, W = á11,7,¥,•,•ñ. Таким образом, после выполнения 2-го шага получаем следующие 5 массивов:
P = á0,1,2,•,•,•ñ;
M = á0,1,5,•,•,•ñ;
T = á3,4,5,•,•ñ;
W = á11,7,¥,•,•ñ;
PR = á–1,0,0,1,1,•ñ.
Для 3-его шага (k = 3) формула (10b) принимает вид W’[i] = M[2] + l(P[2],T[i]) = 5 + l(2,T[i]), отку-да
W[0] = min{11, 5 + l(2,3)} = min{11, 5 + ¥} = 11;
W[1] = min{7, 5 + l(2,4)} = min{7, 5 + 7}} = 7;
W[2] = min{¥, 5 + l(2,5)}} = min{¥, 5 + ¥} = ¥;
Заметим, что новая метка не стала меньше старой ни при каком i. Поэтому в соответствии с пунктом 1.2 k-го шага алгоритма массив PR не изменяется.
Далее, минимальным значением в новом массиве W = á11,7,¥,•,•ñ является число 7, стоящее на 1-м месте, т.е. im = 1, vm = 6. В соответствии с пунктом 3, VC = T[im] = T[1] = 4. В соответствии с пунктом 4 получаем P = á0,1,2,4,•,•ñ, M = á0,1,5,7,•,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á3,5,•,•,•ñ, W = á11,¥,•,•,•ñ. Таким образом, после выполнения 3-его шага получаем следующие 5 массивов:
P = á0,1,2,4,•,•ñ;
M = á0,1,5,7,•,•ñ;
T = á3,5,•,•,•ñ;
W = á11,¥,•,•,•ñ;
PR = á–1,0,0,1,1,•ñ.
Для 4-го шага (k = 4) формула (10b) принимает вид W’[i] = M[3] + l(P[3],T[i]) = 7 + l(4,T[i]), отку-да
W[0] = min{11, 7 + l(4,3)}} = min{11, 7 + 5} = 11;
W[1] = min{¥, 7 + l(4,5)}} = min{¥, 7 + 4} = 11;
Новая метка стала меньше старой при i = 1. Поэтому в соответствии с пунктом 1.2 k-го шага алгоритма при k = 4 получаем
PR[T[1]] = PR[5] = P[3] = 4;
Далее, минимальным значением в новом массиве W = á11,11,•,•,•ñ является число 11. Выберем 11, стоящее на 0-м месте, т.е. im = 0, vm = 11. В соответствии с пунктом 3, VC = T[im] = T[0] = 3. В соответствии с пунктом 4 получаем P = á0,1,2,4,3,•ñ, M = á0,1,5,7,11,•ñ; наконец, изменяя в соответст-вии с пунктом 5 массивы T и W, получаем T = á5,•,•,•,•ñ, W = á11,•,•,•,•ñ. Таким образом, после выпол-нения 4-го шага получаем следующие 5 массивов:
P = á0,1,2,4,3,•ñ;
M = á0,1,5,7,11,•ñ;
T = á5,•,•,•,•ñ;
W = á11,•,•,•,•ñ;
PR = á–1,0,0,1,1,4ñ.
Для 5-го шага (k = 5) формула (10b) принимает вид W’[i] = M[4] + l(P[4],T[i]) = 11 + l(3,T[i]), отку-да
W[0] = min{11, 11 + l(3,5)}} = min{11, 11 + 1} = 11;
Новая метка не стала меньше старой при i = 0. Поэтому в соответствии с пунктом 1.2 k-го шага алго-ритма массив PR не меняется. Далее, минимальным значением в новом массиве W = á11,•,•,•,•ñ является число 11. Имеем im = 0, vm = 11. В соответствии с пунктом 3, VC = T[im] = T[0] = 5. В соответствии с пунктом 4 получаем P = á0,1,2,4,3,5ñ, M = á0,1,5,7,11,11ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á•,•,•,•,•ñ, W = á•,•,•,•,•ñ. Таким образом, после выполнения 5-го шага получаем следующие 5 массивов:
P = á0,1,2,4,3,5ñ;
M = á0,1,5,7,11,11ñ;
T = á•,•,•,•,•ñ;
