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

Щю] + C[w, v] < DfvJ, при выполнении которого элементу P[v] присваивается значение W. После выполнения алгоритма кратчайший путь к калсдой вершине можно найти с помош;ью обратного прохождения по предшествуюш;им вершинам массива Р.


Рис. 6.6. Орграф с помеченными дугами

Таблица 6.1. Вычисления по алгоритму Дейкстры для орграфа из рис. 6.6

Итерация

D[2]

0[3]

0[4]

ЙГ51

Начало

U. 2)

<1, 2, 4>

п. 2, 4, 3}

{1, 2, 4, 3, 5}

Пример 6.7. Для орграфа из примера 6.6 массив Р имеет следующие значения: Р[2] = 1, Р[3] = 4, Р[4] = 1, Р[5]= 3. Для определения кратчайшего пути, например от вершины 1 к вершине 5, надо отследить в обратном порядке предшествующие вершины, начиная с вершины 5. На основании значений массива Р определяем, что вершине 5 предшествует вершина 3, вершине 3 - вершина 4, а ей, в свою очередь, - вершина 1. Таким образом, кратчайший путь из вершины 1 в вершину 5 составляет следующая последовательность вершин: 1,4, 3, 5. □

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

Алгоритм Дейкстры - пример алгоритма, где "жадность" окупается в том смысле, что если что-то "хорошо" локально, то оно будет "хорошо" и глобально. В данном случае что-то локально "хорошее" - это вычисленное расстояние от источника к вершине ш, которая пока не входит в множество S, но имеет кратчайший особый путь. (Напомним, что особым мы назвали путь, который проходит только через вершины множества S.) Чтобы понять, почему не может быть другого кратчайшего, но не особого, пути, рассмотрим рис. 6.7. Здесь показан гипотетический кратчайший путь к вершине w, который сначала проходит до вершины х через вершины множества S, затем после вершины х путь, возможно, несколько раз входит в множество S и выходит из него, пока не достигнет вершины w.

Но если этот путь короче кратчайшего особого пути к вершине w, то и начальный сегмент пути от источника к вершине х (который тоже является особым путем) такясе короче, чем особый путь к w. Но в таком случае в строке (5) листинга 6.3 при выборе вершины W мы долясны были выбрать не эту вершину, а вершину х, поскольку Щ.х] меньше Х)[и>]. Таким образом, мы пришли к противореию, следовательно, не может

6.3. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕЕО ПУТИ 189



быть другого кратчайщего пути к верщине w, кроме особого. (Отметим здесь определяющую роль того факта, что все стоимости дуг неотрицательны, без этого свойства помеченного орграфа алгоритм Дейкстры не будет работать правильно.)


Множество S

Рис. 6.7. Гипотетический кратчайший путь к вершине w

Для заверщения обоснования алгоритма Дейкстры надо еще доказать, что D[v] действительно показывает кратчайщее расстояние до верщины v. Рассмотрим добавление новой верщины w к множеству S (строка (6) листинга 6.3), после чего происходит пересчет элементов массива D в строках (7), (8) этого листинга; при этом может получиться более короткий особый путь к некоторой верщине i, проходящий через верщину w. Если часть этого пути до верщины w проходит через верщины предыдущего множества S и затем непосредственно к верщине v, то стоимость этого пути, Щю] + C[w, V], в строке (8) листинга 6.3 сравнивается с Л[и]и, если новый путь короче, изменяется значение D[v].

Существует еще одна гипотетическая возможность кратчайщего особого пути к верщине v, которая показана на рис. 6.8. Здесь этот путь сначала идет к верщине w, затем возвращается к верщине х, принадлежащей предыдущему множеству S, затем следует к верщине v. Но реально такого кратчайщего пути не может быть. Поскольку верщина х помещена в множество S раньще верщины w, то все кратчайщие пути от источника к верщине х проходят исключительно через верщины предыдущего множества S. Поэтому показанный на рис. 6.8 путь к верщине х, проходящий через верщину W, не короче, чем путь к верщине х, проходящий через верщины множества S. В результате и весь путь к верщине v, проходящий через верщины х и w, не короче, чем путь от источника к верщине х, проходящий через верщины множества S, и далее непосредственно к верщине v. Таким образом, доказано, что оператор в строке (8) листинга 6.3 действительно вычисляет длину кратчайщего пути.


Предыдущее множество S

Рис. 6.8. Реально невозможный кратчайший особый путь



Время выполнения алгоритма Дейкстры

Предположим, что процедура листинга 6.3 оперирует с орграфом, имеющим я верщин и е дуг. Если для представления орграфа используется матрица смежности, то для выполнения внутреннего цикла строк (7) и (8) потребуется время 0(л), а для выполнения всех и - 1 итераций цикла строки (4) потребуется время порядка О(л). Время, необходимое для выполнения оставшейся части алгоритма, как легко видеть, не превышает этот же порядок.

Если количество дуг е значительно меньше л, то лучшим выбором для представления орграфа будут списки смежности, а для множества вершин V \ S - очередь с приоритетами, реализованная в виде частично упорядоченного дерева. Тогда время выбора очередной вершины из множества V\S w пересчет стоимости путей для одной дуги составит O(logn), а обшее время выполнения цикла строк (7) и (8) - 0(е logn), а не 0(п\

Строки (1) - (3) выполняются за время порядка 0(л). При использовании очередей с приоритетом для представления множества V\S строка (5) реализуется посредством оператора DEEETEMIN, а каждая т п - \ итераций цикла (4) - (6) требует времени порядка O(logn).

В результате получаем, что обшее время выполнения алгоритма Дейкстры ограничено величиной порядка 0(с logn). Это время выполнения значительно меньше, чем О(п), когда е сушественно меньше п.

6.4. Нахождение кратчайших путей между парами вершин

Предположим, что мы имеем помеченный орграф, который содержит время полета по маршрутам, связывающим определенные города, и мы хотим построить таблицу, где приводилось бы минимальное время перелета из одного (произвольного) города в любой другой. В этом случае мы сталкиваемся с общей задачей нахождения кратчайших путей, т.е. нахождения кратчайших путей между всеми парами вершин орграфа. Более строгая формулировка этой задачи следуюшая: есть ориентированный граф G = (V, Е), каждой дуге v - > ц) этого графа сопоставлена неотрицательная стоимость C[v, wJ. Обшая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, w) любого пути от вершины V в вершины W, длина которого минимальна среди всех возможных путей от v к w.

Можно решить эту задачу, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве источника. Но сушествует прямой способ решения данной задачи, использующий алгоритм Флойда (R. W. Floyd). Для опрёт деленности положим, что вершины графа последовательно пронумерованы от 1 до л. Алгоритм Флойда использует матрицу А размера л х л, в которой вычисляются длины кратчайших путей. Вначале А[г, •»= C[i,f\ для всех / Ф]. Если дуга i -J отсутствует, то C[i.= >°. Каждый диагональный элемент матрицы А равен 0.

Над матрицей А выполняется л итераций. После к-& итерации A[i, j] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим к. Другими словами, между концевыми вершинами пути i и j могут находиться только вершины, номера которых меньше или равны k.

На fe-й итерации для вычисления матрицы А применяется следуюшая формула:

АД1,Л = min(At.i[(:,/], A ,[i,*] +А.,[,Л).

Нижний индекс к обозначает значение матрицы А после fe-й итерации, но это не означает, что сушествует л различных матриц, этот индекс используется для сокра-шения записи. Ерафическая интерпретация этой формулы показана на рис. 6.9.





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

0.0038