Главная Промышленная автоматика.

begin

1. S*-{v,};

2. D[v,]*-0,

3. for veV-{v,} do D[v]*-l(Vo, v);

4. while SV do

begin

5. выбрать узел wV-S, для которого D[w] принимает

наименьшее значение;

6. добавить W к S;

7. forugV-Sdo

8. D[v]mN{D[vl D[w] + l(w, v)) end

Рис. 5.24, Алгоритм Дейкстры.

корректным, нетрудно убедиться, что время 0(e) наилучшее, на что можно надеяться.

В задаче нахождения кратчайших путей из одного источника ситуация иная. Хотя нет причин предполагать, что для ее решения понадобится более 0(e) времени, ни один такой алгоритм не известен. Мы обсудим алгоритм сложности 0(п), работа которого основана на построении множества S узлов, кратчайшие расстояния до которых от источника известны. На каждом шаге к S добавляется тот из оставшихся узлов, скажем и, расстояние до которого от источника меньше всех других оставшихся узлов. Если стоимости всех ребер неотрицательны, то можно быть уверенным, что путь из источника в v проходит только через узлы из S. Поэтому достаточно найти для каждого узла v кратчайшее расстояние до него от источника вдоль пути, проходящего только через узлы из S. Изложим алгоритм формально.

Алгоритм 5.6. Кратчайший путь из одного источника (алгоритм Дейкстры)

Вход. Ориентированный граф G== (V, Е), источник VoV и функция /, отображающая множество ЕхЕ в множество неотрицательных вещественных чисел. Полагаем l(vt, Vj)=+oo, если ребро (Vi, Vj), ViVj, не принадлежит графу, и l(v, и)=0.

Выход. Для каждого vV наименьшая сумма меток на ребрах из Р, взятая по всем путям Р, идущим из Vb в v.

Метод. Строим такое множество SsF, что кратчайший путь из источника в каждый узел vS целиком лежит в S. Массив Dlv] содержит стоимость текущего кратчайшего пути из Vo в и,




Рис. 5.25. Граф с помеченными ребрами.

который проходит только через узлы из S. Алгоритм приведен на рис. 5.24. □

Пример 5.14. Рассмотрим граф, изображенный на рис. 5.25. Вначале S={t)o}, Dlvo]=0, а D[Vi]=2, +оо, -f oo, 10 для t=l, 2, 3, 4 соответственно. При первой итерации цикла в строках 4-8 берем w=Vi, поскольку D[ui]=2 - наименьшее значение для D. Затем вычисляем D[t;J=MIN(+oo, 2+3)=5 и D[t;.]=MIN (10, 2+7)=9. Последовательность значений для D и другие вычисления алгоритма 5.6 приведены на рис. 5.26. □

Теорема 5.8. Алгоритм 5.6 вычисляет стоимость кратчайшего пути среди всех путей, идущих из Vo в любой узел, и занимает О (л*) времени.

Доказательство, for-цикл в строках 7, 8 требует О[п) шагов, столько же шагов требует и выбор w в строке 5. В оценке сложности while-цикла в строках 4-8 эти процессы преобладают над остальными, while-цикл выполняется О (л) раз, так что общая его сложность равна О (л*). Строки 1-3, очевидно, занимают О (л) времени.

Итерация

D[w]

Начальное

значение

+ 00

К fi, fj. у»}

Все узлы

Рис. 5.26. Вычисления алгоритма 5.6 на графе с рис. 5.25.




Рис. 5.27. Пути, идущие в узел и.

Чтобы показать корректность, надо доказать индукцией по размеру множества S, что для каждого ребра vS число Dlv] равно длине кратчайшего пути из Vo в v. Более того, для всех vV-S число D It)] равно длине кратчайшего пути из Vo в v, лежащего целиком (если не считать сам узел v) в S.

Базис. Пусть liS = l. Кратчайший путь из Uo в себя имеет длину О, а путь из Ко в v, лежащий целиком (исключая v) в S, состоит из единственного ребра (vo, v). Таким образом, строки 2 и 3 корректно формируют начальные значения массива D.

Шаг индукции. Пусть w - узел, выбранный в строке 5. Если число Dlw] не равно длине кратчайшего пути из Vo в w, то должен быть более короткий путь Р. Этот путь Р должен содержать некоторый узел, отличный от ш и не принадлежащий S. Пусть v - первый такой узел на Р. Но тогда расстояние от Vo до v меньше Dlw], а кратчайший путь в v целиком (исключая сам узел v) лежит в S (см. рис. 5.27). Следовательно, по предположению индукции Dlv]<iDlw] в момент выбора w; пришли к противоречию. Отсюда заключаем, что такого пути Р нет и Dlw] - длина кратчайшего

пути из Vo в W.

Второе утверждение (о том, что Dlw] остается корректным) очевидно ввиду строки 8. □

5.11. ДОМИНАТОРЫ В ОРИЕНТИРОВАННЫХ АЦИКЛИЧЕСКИХ ГРАФАХ: КОМБИНИРОВАНИЕ ПОНЯТИЙ

В этой главе мы уже познакомились с несколькими приемами, применяемыми для разработки эффективных алгоритмов, например с поиском в глубину и разумным упорядочением вычислений. В гл. 4 изучили много структур данных, полезных для представления множеств, над которыми выполняются различные операции. Эту главу мы закончим примером, иллюстрирующим, как можно строить эффективные алгоритмы, комбинируя структуры данных из гл. 4 с техникой для графов, развитой в данной главе. Мы будем





0 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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0039