Работа с графами. Лекция 6. Задача о кратчайшем пути В задаче о кратчайшем пути (shortest-paths problem) задается взвешенный ориентированный граф G = - презентация

1 Работа с графами. Лекция 6

2 Задача о кратчайшем пути В задаче о кратчайшем пути (shortest-paths problem) задается взвешенный ориентированный граф G = (V, Е) с весовой функцией w : Е > R, отображающей ребра на их веса, значения которых выражаются действительными числами. Вес (weight) пути р ( V 0, V 1,..., V K ) равен суммарному весу входящих в него ребер. Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику. Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму. 2

3 Варианты Задача о кратчайшем пути в заданный пункт назначения (single-destination shortest-paths problem). Требуется найти кратчайший путь в заданную вершину назначения (destination vertex) t, который начинается в каждой из вершин v. Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине. Задача о кратчайшем пути между заданной парой вершин (single-pair shortest-paths problem). Требуется найти кратчайший путь из заданной вер­шины и в заданную вершину v. Если решена задача о заданной исходной вершине и, то эта задача тоже решается. Более того, для этой задачи не найдено ни одного алгоритма, который бы в асимптотическом пределе был производительнее, чем лучшие из известных алгоритмов решения задачи об одной исходной вершине в наихудшем случае. 3

4 Представление кратчайших путей Часто требуется вычислить не только вес каждого из кратчайших путей, но и входящие в их состав вершины. Представление, которое используется для кратчайших путей, аналогично тому, что используется для деревьев поиска в ширину. В заданном графе G = (V, Е) для каждой вершины v Є V поддерживается атрибут предшественник (predecessor) π [v], в роли которого выступает либо другая вершина, либо значение NIL. В рассмотренных ранее алгоритмах поиска кратчайших путей атрибуты π присваиваются таким образом, что цепочка предшественников, которая начинается в вершине v, позволяет проследить путь, обратный кратчайшему пути из вершины S в вершину v. Таким образом, для заданной вершины v, для которой π [v] NIL, с помощью описанной ранее процедуры P RINT _P ATH (G, s,v) можно вывести кратчайший путь из вершиныsв вершину v. 4

5 Ослабление В рассмотренных далее алгоритмах используется метод релаксации, или ослабления (relaxation). Для каждой вершины v Є V поддерживается атрибут d [v], представляющий собой верхнюю границу веса, которым обладает кратчайший путь из истока s в вершину v. Назовем атрибут d [v] оценкой кратчайшего пути (shortest-path estimate). Инициализация оценок кратчайших путей и предшественников производится в приведенной ниже процедуре, время работы которой равно θ (V): INITIALIZE_SINGLE_S0URCE 5

6 for (Для) каждой вершины v Є V[G] do d[v] π[v] NIL d[s] 0 После инициализации для всех v Є V π [v] = NIL, d [s] = 0 и для всех v Є V{s} d [v] =. Процесс ослабления (relaxation) ребра (u, v;) заключается в проверке, нельзя ли улучшить найденный до сих пор кратчайший путь к вершине v, проведя его через вершину и, а также в обновлении атрибутов d [v] и π [v] при наличии такой возможности улучшения. Ослабление может уменьшить оценку кратчайшего пути d [v] и обновить поле π [v] вершины v. Приведенный ниже код выполняет ослабление ребра (u, v): Relax(u, v, w) if d[v] > d[u] + w(u, v) then d[v] d[u] + w(u, v) π[v] и 6

7 В каждом из описанных алгоритмов сначала вызывается процедура INITIALIZE_SINGLE_S0URCE, а затем производится ослабление ребер. Более того, ослабление единственная операция, изменяющая оценки кратчайших путей и предшественников. Описанные в этой главе алгоритмы различаются тем, сколько раз в них производится ослабление ребер, а также порядком ребер, над которыми выполняется ослабление. В алгоритме Дейкстры и алгоритме поиска кратчайших путей в ориентированных ациклических графах каждое ребро ослабляется ровно по одному разу. В алгоритме Беллмана- Форда (Bellman-Ford) каждое ребро ослабляется по несколько раз. 7

8 Алгоритм Беллмана-Форда Алгоритм Беллмана-Форда (Bellman-Ford algorithm) позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным. Для заданного взвешенного ориентированного графа G = (V,E) с истоком s и весовой функцией w : Е R алгоритм Беллмана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес. В этом алгоритме используется ослабление, в результате которого величина d [v], представляющая собой оценку веса кратчайшего пути из истока s к каждой из вершин v Є V, уменьшается до тех пор, пока она не станет равна фактическому весу кратчайшего пути δ(s,v). 8

9 Значение TRUE возвращается алгоритмом тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока. Bellman_Ford(G, w, s) 1. I NITIALIZE _S INGLE _S OURCE (G, s) 2. for i 1 to |V[G]| 1 3. do for (для) каждого ребра (и, v) Є E[G] 4. do Relax(u, v, w) 5. for (для) каждого ребра (и, v) Є E[G] 6. do if d[v] >d[u] + w(u,v) 7. then return FALSE 8. return TRUE 9

10 работа алгоритма B ELLMAN _F ORD с графом, содержащим 5 вершин, в котором исток находится в вершине s. 10

11 Рассмотрим, как работает алгоритм. После инициализации в строке 1 всех значений d и π, алгоритм осуществляет |V| 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла for в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После |V| 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответствующее булево значение. В примере, приведенном на слайде, алгоритм Беллман-Форда возвращает значение true. 11

12 в вершинах графа показаны значения атрибутов d на каждом этапе работы алгоритма, а выделенные ребра указывают на значения предшественников: если ребро (и, v) выделено, то π [v] = и. В рассматриваемом примере при каждом проходе ребра ослабляются в следующем порядке: (t, х), (t, у), (t, z), (x,t), (у,х), (y,z), (z,x), (z,s), (s,t), (s,y). В части а рисунка показана ситуация, сложившаяся непосредственно перед первым проходом по ребрам. В частях б-д проиллюстрирована ситуация после каждого очередного прохода по ребрам. Значения атрибутов d и π, приведенные в части д, являются окончательными. Алгоритм Беллмана-Форда завершает свою работу в течение времени О (V+Е), поскольку инициализация в строке 1 занимает время θ(V), на каждый из |V| - 1 проходов по ребрам в строках 2-4 требуется время θ(Е), а на выполнение цикла for в строках 5-7 время О(Е). 12

13 Кратчайшие пути из одной вершины в ориентированных ациклических графах Ослабляя ребра взвешенного ориентированного ациклического графа G = (V, Е) в порядке, определенном топологической сортировкой его вершин, крат­чайшие пути из одной вершины можно найти в течение времени θ (V + Е). В ориентированном ациклическом графе кратчайшие пути всегда вполне определены, поскольку даже если у некоторых ребер вес отрицателен, циклов с отрицательными весами не существует. Работа алгоритма начинается с топологической сортировки ориентированного ациклического графа, чтобы установить линейное упорядочение вершин. Если путь из вершины и к вершине v существует, то в топологической сортировке вершина и предшествует вершине v. По вершинам, расположенным в топологическом порядке, проход выполняется только один раз. При обработке каждой вершины производится ослабление всех ребер, исходящих из этой вершины. 13

14 D AG _S HORTEST _P ATHS (G, w, s) 1. Топологическая сортировка вершин графа G 2.Initialize_Single_Source(G, S ) 3. for (для) каждой вершины и в порядке топологической сортировки 4. do for (Для) каждой вершины v Є Adj[u] 5. do R ELAX ( U, v, w) Работа этого алгоритма проиллюстрирована на след. Слайде. Вершины на рисунке топологический отсортированы слева направо. В роли истока выступает вершина s. В вершинах приведены значения атрибутов d, а выделенные ребра указывают значения π. В части а рисунка приведена ситуация перед первой итерацией цикла for в строках 3-5. В каждой из частей б-ж рисунка показаны ситуации, складывающиеся после каждой итерации цикла for в строках 3-5. Каждая новая черная вершина используется в соответствующей итерации в качестве и. В части ж приведены конечные значения. Время выполнения этого алгоритма легко поддается анализу. Топологическую сортировку в строке 1 можно выполнить в тече­ние времени θ (V + Е). 14

15 15

16 Вызов процедуры I NITIALIZE _S INGLE _S OURCE в строке 2 занимает время θ (E). На каждую вершину приходится по одной итерации цикла for в строках 3-5. Для каждой вершины все исходящие из нее ребра проверяются ровно по одному разу. Таким образом, всего выполняется |E| итераций внутреннего цикла for в строках 4-5. Поскольку каждая итерация внутреннего цикла for занимает время 0(1), полное время работы алгоритма равно θ (V + Е), т.е. оно выражается линейной функцией от размера списка смежных вершин графа. 16

17 Алгоритм Дейкстры Алгоритм Дейкстры решает задачу о кратчайшем пути из одной вершины во взвешенном ориентированном графе G = (V, Е) в том случае, когда веса ребер неотрицательны. Поэтому в настоящем разделе предполагается, что для всех ребер (и, v) Є Е выполняется неравенство w (и, v) 0. При хорошей реализации алгоритм Дейкстры производительнее, чем алгоритм Беллмана-Форда. В алгоритме Дейкстры поддерживается множество вершин S, для которых уже вычислены окончательные веса кратчайших путей к ним из истока s. В этом алгоритме поочередно выбирается вершина и Є V S, которой на данном этапе соответствует минимальная оценка кратчайшего пути. После добавления этой вершины и в множество S производится ослабление всех исходящих из нее ребер. В приведенной ниже реализации используется неубывающая очередь с приоритетами Q, состоящая из вершин, в роли ключей для которых выступают значения d. 17

18 Dijkstra(G, W, S ) 1. I NITIALIZE _S INGLE _S OURCE (G, s) 2. S 0 3. Q V[G) 4. while Q 0 5. do и Extract_Min(Q) 6. S S U {u} 7. for (для) каждой вершины v Є Adj [u] 8. do R ELAX (u, v, w) Процесс ослабления ребер в алгоритме Дейкстры проиллюстрирован на рис. Исток s расположен на рисунке слева от остальных вершин. В каждой вершине приведена оценка кратчайшего пути к ней, а выделенные ребра указывают предшественников. Черным цветом обозначены вершины, добавленные в множество S, а белым содержащиеся в неубывающей очереди с приоритетами Q = V S. 18

19 В части а рисунка проиллюстрирована ситуация, сложившаяся непосредственно перед выполнением первой итерации цикла while в строках 4-8. Выделенная серым цветом вершина имеет минимальное значение d и выбирается в строке 5 в качестве вершины и для следующей итерации. В частях б-е изображены ситуации после выполнения очередной итерации цикла while. В каждой из этих частей выделенная серым цветом вершина выбирается в качестве вершины и в строке 5. В части е приведены конечные значения величин d и π. 19

20 Работа рассматриваемого алгоритма. В строке 1 производится обычная инициализация величин d и π, а в строке 2 инициализируется пустое множество вершин S. В начале каждой итерации цикла while в строках 4-8 выполняется равенство Q = V S. В строке 3 неубывающая очередь с приоритетами Q инициализируется таким образом, чтобы она содержала все вершины множества V; поскольку в этот момент S = 0. При каждой итерации цикла while в строках 4-8 вершина и извлекается из множества Q = V S и добавляется в множество S. (Во время первой итерации этого цикла и = s.) Таким образом, вершина и имеет минимальную оценку кратчайшего пути среди всех вершин множества V S. 20

21 Затем строках 7-8 ослабляются все ребра (и, v), исходящие из вершины и. Если текущий кратчайший путь к вершине v может быть улучшен в результате прохождения через вершину и, выполняется ослабление и соответствующее обновление оценки величины d [v] и предшественника π[v]. Учитываем, что после выполнения строки 3 вершины никогда не добавляются в множество Q и что каждая вершина извлекается из этого множества и добавляется в множество S ровно по одному разу, поэтому количество итераций цикла while в строках 4-8 равно |V|. 21

22 Анализ Насколько быстро работает алгоритм Дейкстры? В нем поддерживается неубывающая очередь с приоритетами Q и тремя операциями, характерными для очередей с приоритетами: Insert (явно вызывается в строке 3), EXTRACT_MlN (строка 5) и Decrease_Key (неявно присутствует в процедуре Relax, которая вызывается в строке 8). Процедура Insert, как и процедура Extract_Min, вызывается по одному разу для каждой вершины. Поскольку каждая вершина v Є V добавляется в множество S ровно по одному разу, каждое ребро в списке смежных вершин Adj [v] обрабатывается в цикле for, заданном в строках 7-8, ровно по одному разу на протяжении работы алгоритма. Так как полное количество ребер во всех списках смежных вершин равно |E|, всего выполняется |E| итераций этого цикла for, а следовательно, не более |E| операций Decrease_Key. 22

23 Время выполнения алгоритма Дейкстры зависит от реализации неубывающей очереди с приоритетами. Сначала рассмотрим случай, когда неубывающая очередь с приоритетами поддерживается за счет того, что все вершины пронумерованы от 1 до |V|. Атрибут d[v] просто помещается в элемент массива с индексом v. Каждая операция I NSERT и D ECREASE _K EY занимает время 0(1), а каждая операция E XTRACT _M IN время О (V) (поскольку в ней производится поиск по всему массиву); в результате полное время работы алгоритма равно О (V 2 + Е) = О (V 2 ). Если граф достаточно разреженный, в частности, если количество вершин и ребер в нем связаны соотношением Е = O(V 2 /lgV), с практической точки зрения целесообразно реализовать неубывающую очередь с приоритетами в виде бинарной неубывающей пирамиды. Далее, каждая операция E XTRACT _M IN занимает время О (lg V). 23

24 Как и раньше, таких операций |V|. Время, необходимое для построения неубывающей пирамиды, равно О (V). Каждая операция D ECREASE _K EY занимает время О (lg V), и всего выполняется не более |E| таких операций. Поэтому полное время выполнения алгоритма равно О((V + Е) lg V), что равно О (Е lg V), если все вершины достижимы из истока. Это время работы оказывается лучшим по сравнению со временем работы прямой реализации О (V 2 ), если Е = O (V 2 /lgV). Фактически время работы алгоритма может достигать значения 0( V lg V+E), если неубывающая очередь с приоритетами реализуется с помощью пирамиды Фибоначчи. Амортизированная стоимость каждой из |V| операций E XTRACT _M IN равна О (lg V), и каждый вызов процедуры D ECREASE _K EY (все­го не более |E|), занимает лишь 0(1) амортизированного времени. 24

25 Исторически сложилось так, что развитие пирамид Фибоначчи было стимулировано наблюдением, согласно которому в алгоритме Дейкстры процедура D ECREASE K EY обычно вызывается намного чаще, чем процедура E XTRACT _M IN, поэтому любой метод, уменьшающий амортизированное время каждой операции DECREASE_KEY до величины O (lg V), не увеличивая при этом амортизированное время операции E XTRACT _M IN, позволяет получить реализацию, которая в асимптотическом пределе работает быстрее, чем реализация с помощью бинарных пирамид. 25

26 Алгоритм Дейкстры имеет некоторую схожесть как с поиском в ширину, так и с алгоритмом Прима, предназначенным для построения минимальных остовных деревьев. Поиск в ширину он напоминает в том отношении, что множество S соответствует множеству черных вершин, используемых при поиске в ширину; точно так же, как вершинам множества S сопоставляются конечные веса кратчайших путей, так и черным вершинам при поиске в ширину сопоставляются правильные расстояния. На алгоритм Прима алгоритм Дейкстры похож в том отношении, что в обоих этих алгоритмах с помощью неубывающей очереди с приоритетами находится самая легкая вершина за пределами заданного множества (в алгоритме Дейкстры это множество S, а в алгоритме Прима выращиваемое дерево), затем эта вершина добавляется в множество, после чего соответствующим образом корректируются и упорядочиваются веса оставшихся за пределами множества вершин. 26

27 Минимальные остовные деревья При разработке электронных схем зачастую необходимо электрически соеди­нить контакты нескольких компонентов. Для соединения множества из n контактов мы можем использовать некоторую компоновку из n 1 проводов, каждый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество провода. Мы можем смоделировать эту задачу при помощи связного неориентированного графа G = (V, Е), где V множество контактов, Е множество возможных соединений между парами контактов, и для каждого ребра (u, v) Є Е задан вес w(u,v), определяющий стоимость (количество необходимого провода) соединения и и v. 27

28 Мы хотим найти ациклическое подмножество ТЄЕ, которое соединяет все вершины и чей общий вес минимален. Поскольку множество Т ациклическое и связывает все вершины, оно должно образовывать дерево, которое мы назовем остовным деревом (spanning tree) графа G (иногда используется термин покрывающее дерево). Задачу поиска дерева Т мы назовем задачей поиска минимального остовного дерева (minimum- spanning-tree problem). По сути, термин минимальное остовное дерево означает остовное дерево с минимальным весом. Мы не минимизируем, например, количество ребер в Т, поскольку все остовные деревья имеют ровно |V| 1 ребер. На рис. показан пример связного графа и его минимального остовного дерева. На ребрах указан их вес, а ребра минимального остовного дерева отдельно выделены цветом. Общий вес показанного дерева равен

29 Приведенное дерево не единственное: удалив ребро (b, с) и заменив его ребром (a, h), мы получим другое остовное дерево с тем же весом 37. Далее мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева алгоритм Крускала (Kruskal) и Прима (Prim). Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О (E*lgV). При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до О (Е + VlgV), что является весьма существенным ускорением при |V| << |Е|. 29

30 Построение минимального остовного дерева Предположим, что у нас есть связный неориентированный граф G = (V, Е) с весовой функцией w : Е R, и мы хотим найти минимальное остовное дерево для G. В этой главе мы рассмотрим два жадных алгоритма решения поставленной задачи. Оба рассматриваемых алгоритма имеют общую схему, согласно которой ми­нимальное остовное дерево растет путем добавления к нему ребер по одному. Алгоритм работает с множеством ребер А, работает следующим образом: Перед каждой очередной итерацией А представляет собой подмножество некоторого минимального остовного дерева. 30

31 На каждом шаге алгоритма мы определяем ребро (и, v), которое можно добавить к А, в том смысле, что A U {(u,v)} также является подмножеством минимального остовного дерева. Мы назовем такое ребро безопасным (safe edge) для А. Generic_MST(G, W ) 1.А0 2. while А не является минимальным остовным деревом 3. do Найти безопасное для А ребро (и, v) 4. А A U {(u,v)} 5. return А 31

32 Самое важное, само собой разумеется, заключается в том, как именно найти безопасное ребро в строке 3. Оно должно существовать, поскольку когда выполняется строка 3, требуется, чтобы существовало такое остовное дерево Т, что A Є T. Внутри тела цикла while А должно быть истинным подмножеством Т, поэтому должно существовать ребро (и, v) Є Т, такое что (и, v) не Є А и (и, v) безопасное для А ребро. Далее мы приведем правило для распознавания безопасных ребер и рассмотрим два алгоритма, которые используют это правило для эффективного поиска безопасных ребер. 32