Обобщенный алгоритм Дейкстры

(именно здесь и только здесь используется функция 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, k₁ и k₂ [k₁ < k₂] → [Z(i,k₁)  ≥ Z(i,k₂)].

Лемма 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)).                                                                                                                          (11)

Доказательство. По условию леммы, путь P(0,s,t) состоит из двух участков: участка P₀(0,s), соединяющего вершину 0 с вершиной s, и ребра (s,t). По условию а) леммы вершина s получила пос-тоянную метку ks на одном из первых k шагов, откуда по предположению индукции построенный ОАД путь P* из 0 в s, длина которого равна постоянной метке Z(s,ks), является кратчайшим. В силу этого предположения любой другой путь из 0 в s, в том числе и путь P₀(0,s), не могут быть короче, чем путь P*. Поскольку длина пути P* по построению равна метке Z(s,ks), то для длины L(P₀(0,s)) пути P₀(0,s) имеет место неравенство

Z(s,ks) ≤ L(P₀(0,s)).                                                                                                                                        (12)

Вернёмся к пути P(0,s,t), состоящему из двух частей: P₀(0,s) и ребра (s,t). В силу формулы (2)

L(P(0,s,t)) = F(L(P₀(0,s)), l(s,t)).                                                                                                               (13)

Учитывая, что функция  длины F(x,y) является монотонно неубывающей по каждому аргументу, из (13) и (12) получаем

F(Z(s,ks),l(s,t)) ≤ L(P(0,s,t)).                                                                                                                     (14)

Левая часть неравенства (14) с точностью до обозначений совпадает с правой частью равенства (10b) F(M[k–1], l(P[k–1],T[t]),                                                                                                                             (15)

использующегося при вычислении нового значения временной метки вершины 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)

(16) и (14) влекут

Z(t,ks+1) ≤ L(P(0,s,t)).                                                                                                                    (17)

Теперь в силу леммы 1 для любого k’, бóльшего ks,  из (17) следует

Z(t,k’) ≤ L(P₀(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).                                                                                                                                     (18)

Рассмотрим путь Р(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))                                                                                                                               (19)

(см. утверждение 2 в разделе 2).

В силу условий а) и б) число k’ = k+1 и путь P(0,s,t) удовлетворяют условиям леммы 2. В силу этой леммы

Z(t,k+1) ≤ L(P(0,s,t)).                                                                                                                                   (20)

Неравенства (18) – (20) влекут неравенство

Z(t,k+1) < Z(u,k+1).                                                                                                                                     (21)

Напомним, что по построению на (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 = á•,•,•,•,•ñ;