Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 109
Текст из файла (страница 109)
Хотя вес или мера, присвоенные ребрам, могут иметь различные значения, для упрощения будем рассматривать вес ребра как расстояние, а наилучший путь из точки А в точку В как кратчайший путь между точками А и В. Это всего лишь вопросы терминологии, и они ни в коей мере не ограничивают использование теории или общность результатов. Тем не менее, одно важное ограничение будет введено.
Предположим, что вес или мера, названные теперь расстоянием и приписываемые ребрам между двумя различными точками, положительные. Существуют алгоритмы, которые с некоторыми ограничениями допускают отрицательные значения веса ребер. Например, алгоритм Флойда-Уоршолла, приведенный в данном разделе, можно использовать для ребер с отрицательным весом. В оставшейся части раздела будем использовать символ оо.
Для упрощения рассмотрения предположим, что все целые числа меньше оо, так что ш)п(а, оо) = а для каждого неотрицательного целого числа а и ппп(оо,оо) = оо. Примем также, что а + сю = со + оо = сю. Это — для удобства обозначений. Для улучшения системы обозначений используется следующее определение. Первый алгоритм, который будет описан, назывется алгоритмом Дейкстры. Существует несколько версий этого алгоритма. Первым будет приведен оригинальный алгоритм, а затем его улучшенная версия, которая является более эф- 612 ГплВА 14.
некопюрые специальные вопросы теории графов фективной. Кроме того, алгоритм обладает дополнительным свойством, которое позволяет определить не только длину кратчайшего пути, но и сам путь. Это достигается с помошью указателя, который для каждой вершины из кратчайшего пути указывет предыдушую вершину пути. Таким образом, если найдена длина кратчайшего пути между А и В, то двигаясь вдоль кратчайшего пути в обратном направлении от В к А, можно найти сам путь.
Далее будет продемонстрирована улучшенная версия алгоритма Дейкстры вместе с возможностью находить путь. Прежде, чем начать, сформулируем теорему, которая может показаться интуитивно очевидной. Доказательство предоставляется читателю. ТЕОРЕМА 14.86. Пусть а = вг и 6 = в„. Если ог, вз,..., о;, о,+ы..., в,, о,.ь ы..., о„ есть кратчайший путь между а и 6, то о„в,ч.ы..., в, часть этого пути между вершинами в, и о, является кратчайшим путем между в, и о . Начнем с формулировки первого алгоритма Дейкстры, а затем дадим пример его использования. Согласно алгоритму отыскивается кратчайшее расстояние от вершины ог к вершине в„. Начинаем с вершины ог н находим расстояние от вг до каждой из смежных с ней вершин. Выбираем вершину, расстояние от которой до вершины ог наименьшее, пусть это будет вершина вь Далее находим расстояние от вершины ог до каждой вершины, смежной к в< вдоль пути, проходяшего через вершину о,.
Если это расстояние меньше, чем текущее расстояние, присвоенное каждой из вершин, то заменяем им текушее расстояние. Снова выбираем вершину, ближайшую к ог, но не совпадающую с выбранной ранее, и процесс повторяется. Алгоритм Дейкстры(1) Для данного взвешенного графа алгоритм дает кратчайшее расстояние от вершины о~ к вершине о„. Каждой вершине поставим в соответствие упорядоченную пару (оо,0). Первая координата вершины в;(т,о„) будет означать присвоенное расстояние от вершины вг к вершине в,, а вторая координата — предыдущую вершину пути от ог к в,. (1) Начать в вершине ог(оо,0), заменить ее на ог(0,0) н сделать постоянной. Остальные вершины на этот момент оставить временными. (2) Когда вершина оь(т,о„) станет постоянной, для каждой вершины в,, смежной к оь, прибавить величину т к расстоянию от вершины оь к вершине о .
Если это значение меньше, чем текушее расстояние, присвоенное вершине в, заменить текушее расстояние этой суммой и заменить вторую координату на вы (3) Найти минимум из расстояний, приписанных временным вершинам. Первую из вершин с таким расстоянием делаем постоянной. (4) Если о„ вЂ” не постоянная вершина, то возврашаемся к пункту (2).
(5) Если ℠— постоянная вершина, то расстояние, присвоенное вершине в„, является кратчайшим расстоянием от ог к в„. (6) Для нахождения пути начать в вершине о„, найти предшествуюшую ей вершину пути (вторая координата). Для каждой вершины пути ву находить предшествующую ей вершину пути, пока не будет достигнута вершина оы Перестановка вершин в обратном порядке даст кратчайший путь. РАЗДЕЛ 14.5.
Взвешенные графы и алгоритмы поиска кратчаишего пути 613 ПРИМЕР 14.66. Пусть граф, изображенный на рис. 14.84, — взвешенный граф, в котором отыскивается кратчайшее расстояние от вершины А к вершине Г. Поставив в соответствие каждой вершине упорядоченную пару (оо,0), рассматриваемый граф приводим к виду, показанному на рис. !4.85. )з(оо,О) Е(очО) А(со,О) Е С(оо,О) 7 Е(~о,О) Рис.
14.85 Рис. 14.84 Приступим к построению путей от вершины А к другим вершинам. Первая компонента упорядоченной пары покажет длину кратчайшего пути к вершине в момент достидения, а вторая компонента укажет на предыдущую вершину кратчайшего пути. Первая компонента будет содержать со, а вторая — 0 до тех пор, пока путь не найден. Вершина, которая стала постоянной, будет выделена жирным шрифтом.
Выполнив шаг 1 алгоритма, получаем граф, изображенный на рис. 14.86. Поскольку вершины В и С вЂ” смежные с вершиной А, выполняем шаг 2 и упорядоченной паре для вершины В присваиваем значение (5, А), а упорядоченной паре для вершины С присваиваем значение (6, А). (Фактичестки, изменения вносятся, тогда и только тогда, когда новые расстояния меньше старых, но поскольку старые расстояния до вершин В и С равны со, в данном случае это не имеет значения.) Выполнив шаг 3, выбираем наименьшее из временных присвоенных значений.
В данном случае это расстояние до вершины А, равное 5, и вершину В(5, А) делаем постоянной. Таким образом, получаем рис. 14.87. 1з( о,О) )з(оо,О) Р(оо,О) Е(очО) А(0,0) А(0,0) С(б,А) 7 Е(очО) Рис. 14.87 Рис. 14.85 Возвращаясь к шагу 2, рассмотрим временные вершины С, Р, Е и Р, смежные с вершиной В. В каждом случае прибавляем расстояние от вершины А к вершине В к расстоянию от вершины В к данным вершинам.
Таким образом, для вершины С это будет 5+ 3 = 8. Для вершины 1) имеем 5+ 7 = 12. Для вершины Е имеем 5+ 2 = 7. Для вершины Р получаем 5+ 10 = 15. Поскольку новое 644 ГЛАВА 14, Некоторые специальные вопросы теории графов расстояние до вершины С не меньше, чем уже присвоенное, упорядоченную пару С(6, А) оставляем без изменения.
Новые расстояния до вершин О, Е и Е меньше уже присвоенных, поэтому им задаем значения, которые получены для пути из вершины В, т.е. меняем их на Р(12,В), Е(7,В) и Г(16,В). Выполнив шаг 3, находим наименьшее из расстояний, присвоенных временным вершинам, поэтому берем ш!п(6, 12,16,7) = 6, и поскольку вершина С имеет это расстояние, делаем вершину С(6, А) постоянной. Таким образом, получаем рис. 14.88. Р(12,В) г(15,В) А(0,0) С(б>А) Б(7,В) рис.
74 8л П Теперь берем новую постоянную вершину С. Выполнение шага 2 не приводит к изменениям. Выполнив шаг 3, делаем вершину Е(7, В) постоянной. Получаем в результате рис. !4.89. Р(12,В) г(15,В) А(0,0) Е(7,В) С(б,А) Рис. !4.89 Берем новую постоянную вершину Е и, используя шаг 2, меняем Г(16, В) на Е(11, Е). Выполнив шаг 3, делаем вершину Е(11, Е) постоянной. Таким образом, получаем рис. 14.90.
Р(12,В) )г(11,В) А(0,0) С(б,А) ( ' ) Рис. 14.90 Вершина Г стала постоянной, поэтому процесс завершен и 11 — это кратчайшее расстояние от вершины А к вершине Г. Если бы совокупность вершин, смежных с постоянной вершиной, была исчерпана до того, как мы достигли вершину Г, то задача не имела бы решения, поскольку не было бы пути от вершины А к вершине Г. Для нахождения кратчайшего пути заметим, что вершине Е предшествует вершина Е, вершине Е предшествует вершина В, а вершине В предшествует вершина А. Поэтому кратчайшим путем является АВЕР.
(:) РКЭДЕЛ 14.5. Взвешенные графы и алгоритмы поиска кратчайшего пути 615 Сформулируем теперь второй алгоритм Дейкстры, в котором для нахождения кратчайшего расстояния между двумя вершинами использованы матрицы. Пусть и — количество вершин в графе. Матрица ЪЪ' — матрица размерности и х гг, в которой значение ЪЪ'(г',у) равно расстоянию между вершинами иг и игч если они смежные, или полагается равным оо в противном случае. Обозначим г'-ю строку матрицы И~ через И'(4). Используем вспомогательные матрицы Р, Т, Яигп и ргед размерности 1 хи и переменную Ъ'.
Матрица-строка ргеи(г) содержит индекс вершины, которая предшествует вершине и, в кратчайшем пути к и;. Матрица-строка Р(1) хранит постоянное расстояние от вершины иг к вершине ьы если вершина о, выбрана как постоянная вершина. Матрица-строка Т(1) содержит значения временного расстояния от вершины иг к вершине сы Переменная Ъ' отслеживает последнюю постоянную вершину. Матрица-строка Яигп используется просто для временного хранения значений Р(Ъ') + ЪЪ'(Ъ'). Алгоритм Дейкстры(2) (1) Установить Р(1) = О, Т(1) = оо и И' г = оо при 1 < 1 < 5.
Положить Ъ' = 1. (2) Добавить Р(Ъ') к каждому элементу И'(Ъ'). Более точно, пусть Бит = Р(Ъ') + И'(Ъ'). Для Бит(1) < Т(1') положить ргег)(Я = Ъ". Далее, положить Т = Т д Випм и для наименьшего г такого, что Т(1) = пип(Т(у): 1 < г < п) положить Р(1) = Т(1), Т(4) = оо и ЪЪ',; = оо для 1 < 1 < и. Положить Ъ' = г. (3) Если г ~ и, вернуться к шагу 2.
(4) Если г = и, то Р(1) — кратчайшее расстояние от и~ к и„. (5) Для нахождения пути использовать ргеЯп) и найти вершину, которая предшествует п. Для каждой вершины пути о использовать ргег)Я и находить предшествующую ей вершину, пока не будет достигнута вершина оы Перестановка вершин в обратном порядке даст кратчайший путь. ПРИМЕР 14.87. Определим кратчайший путь от вершины иг к вершине из для графа, изображенного на рис. 14.91.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
