Программная реализация алгоритма Дейкстры

Содержание

 

 

 

1. Алгоритм поиска кратчайшего пути в ориентированном графе

 

Ориентированный граф (сокращенно орграф) G = (V, E) состоит из множества вершин V  и множества дуг E. Вершины также называют узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w – концом дуги.

Кратчайший  путь из u в v – это любой путь p из u в v, для которого w(p) = δ(u, v), где:

• w(p) = сумма весов всех ребер пути p
• δ(u, v) = min{w(p): по всем путям p из u в v}, если существует путь из u в v; ∞ - в противном случае

Алгоритм Дейкстры решает задачу о кратчайших путях из одной  вершины для взвешенного ориентированного графа G = (V, E)  с исходной вершиной s, в котором веса всех ребер неотрицательны.

Алгоритм.

d[u] – расстояние до вершины u из исходной вершины s

Q – очередь с приоритетами. Извлекается вершина, для которой d[u] минимально

 

Initialize-Single-Source(G, s)

 for (для) всех вершин v из V[G]

  do d[v] = ∞

        родитель[v] = NIL

 d[s] = 0

 

Relax(u, v, w)

 if d[v] > d[u] + w(u, v)

  then d[v] = d[u] + w(u, v)

предок[v] = u

 

Dijkstra(G, w, s)

Initialize-Single-Source(G, s)

S = Ø

Q ← V[G]

 while Q <> Ø

do u ← извлечь вершину, для которой d[u] минимально

   S = S U {u}

   for (для) всех вершин v смежных с u

      do Relax(u, v, w)

Суть алгоритма. d[u] – эта оценка пути по каждой из вершин на данном шаге. Изначально нам известно, что до исходной вершины путь 0, до остальных оценка на первом шаге бесконечность. На каждом шаге берем вершину u для которой оценка минимальна. Для неё можно доказать, что оценка является кратчайшим путем. Для смежных с ней вершин v, если оценка через вершину u оказывается меньше, чем текущая оценка вершины v, то уменьшаем оценку (релаксация).

Оценка времени  работы. Оценка времени работы зависит от эффективности реализации очереди с приоритетами. При использовании массива, оценка получается O(V²); при использовании двоичной кучи оценка будет O(E log V); при использовании фибоначчиевой кучи оценка O(V log V + E).

Алгоритм Беллмана-Форда  решает задачу о кратчайших весах  из одной вершины для случая, когда  весам ребер разрешено быть отрицательными. Этот алгоритм возвращает TRUE, если в графе нет цикла отрицательного веса, достижимого из исходной вершины, и FALSE, если таковой цикл имеется. В первом случае алгоритм находит кратчайшие пути и их веса; во втором случае кратчайших путей (по крайней мере, для некоторых вершин) не существует.

Алгоритм.

d[u] – расстояние до вершины u из исходной вершины s

 

Initialize-Single-Source(G, s)

 for (для) всех вершин v из V[G]

  do d[v] = ∞

        родитель[v] = NIL

 d[s] = 0

 

Relax(u, v, w)

 if d[v] > d[u] + w(u, v)

  then d[v] = d[u] + w(u, v)

предок[v] = u

 

Bellman-Ford(G, w, s)

Initialize-Single-Source(G, s)

 for i = 1 to |V[G]| - 1

  do for (для) каждого ребра (u, v) из E[G]

do Relax(u, v, w)

 for (для) каждого ребра (u, v) из E[G]

do if d[v] > d[u] + w(u, v)

then return FALSE

 return TRUE

Оценка времени работы. Время работы алгоритма есть O(VE).

Может возникнуть задача, когда требуется найти кратчайшее расстояние между всеми парами вершин. Алгоритм Флойда-Уоршолла использует идею динамического программирования и позволяет за O(V³) найти кратчайшие пути между всеми парами вершин ориентированного взвешенного графа. Веса ребер могут быть отрицательными, но не допускается существования циклов отрицательного веса.

Алгоритм.

W – матрица весов n x n

D – матрица расстояний n x n

 

Floyd-Warshall(W)

D = W

for k = 1 to n

do for i = 1 to n

do for j = 1 to n

do D[i, j] = min(D[i, j], D[i, k] + D[k, j])

Результатом работы алгоритма  будет матрица D кратчайших расстояний между вершинами.

 

 

 

 

2. Алгоритм поиска эйлерова  цикла

 

Эйлеровым циклом называется замкнутый маршрут, в котором каждое ребро графа встречается точно один раз. Для существования такого маршрута в связном графе необходимо и достаточно, чтобы степени всех вершин были четными. Рассмотрим алгоритм, который находит эйлеров цикл в заданном графе при условии, что условия связности и четности степеней выполнены.

Этот алгоритм похож на алгоритм поиска в глубину: начиная с произвольно выбранной  стартовой вершины a, строим путь, выбирая каждый раз для дальнейшего продвижения еще не пройденное ребро. Главное отличие от поиска в глубину состоит в том, что как пройденные помечаются именно ребра, а не вершины. Поэтому одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза, так что в полученном маршруте ребра не будут повторяться. Вершины пути накапливаются в стеке S.

Через некоторое  количество шагов неизбежно наступит тупик - все ребра, инцидентные активной (последней посещенной) вершине x, уже пройдены. Так как степени всех вершин графа четны, в этот момент x=a и пройденные ребра образуют цикл, но он может включать не все ребра графа. Для обнаружения еще не пройденных ребер возвращаемся по пройденному пути, перекладывая вершины из стека S в другой стек C, пока не встретим вершину x, которой инцидентно не пройденное ребро. Так как граф связен, такая вершина обязательно встретится. Тогда возобновляем движение вперед по непройденным ребрам, пока не дойдем до нового тупика и т.д. Процесс заканчивается, когда в очередном тупике обнаруживается, что S пуст. В этот момент в стеке C находится последовательность вершин эйлерова цикла.

Алгоритм 1. Построение эйлерова цикла

1. выбрать произвольно вершину a
2. a->S
3. while s!=O do
4. x:=top(S)
5. if имеется непройденное ребро (x,y)
6. then пометить ребро (x,y) как пройденное
7. y->S
8. else переместить вершину x из S в C

Для обоснования  алгоритма заметим сначала, что  первой в стек S помещается вершина a, и она будет последней перемещена из S в C. Следовательно, она будет последней вершиной в стеке C. Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены (т.е. будет выполняться ветвь else в строке 8), активной будет стартовая вершина a. Значит, эта вершина будет первой перемещена из S в C. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в стеке C, находится вершина a. Иначе говоря, если эта последовательность представляет маршрут (а далее будет показано, что так оно и есть), то этот маршрут замкнут.

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

Будем говорить, что ребро (x,y) представлено в стеке (S или C), если в какой-то момент работы алгоритма в стеке рядом находятся вершины x и y. Ясно, что каждое ребро графа будет представлено в стеке S и что каждые две вершины, расположенные рядом в этом стеке, образуют ребро.

Допустим, в какой-то момент из стека S в стек C перемещается вершина x, а непосредственно под ней в стеке S находится вершина y. Возможно, что вершина y будет перемещена из S в C при следующем повторении цикла while, тогда ребро (x,y) будет представлено в стеке C. Другая возможность - между перемещением вершины x и следующим перемещением, т.е. следующим выполнением ветви else, будет несколько раз выполнена ветвь then (строки 6, ,7). Это означает, что будет пройдена некоторая последовательность ребер, начинающаяся в вершине y. Ввиду четности степеней эта последовательность может закончиться только в вершине y. Значит, и в этом случае следующей за вершиной x будет перемещена из S в C вершина y. В любом случае ребро (x,y) будет представлено в стеке C. Из этого рассуждения видно, что последовательность вершин в стеке C является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.

При каждом повторении цикла while в рассмотренном алгоритме либо проходится одно ребро, либо одна вершина перемещается из S в C. Последнее можно трактовать как прохождение уже пройденного однажды ребра в обратном направлении. Каждое ребро в каждом направлении будет пройдено один раз, поэтому общая трудоемкость этого алгоритма оценивается как O(m).

Необходимо  только оговориться, что этот вывод справедлив лишь при определенных предположениях о том, как задан граф. Способ задания должен обеспечить возможность быстрого просмотра множества ребер, инцидентных данной вершине. Подходящим является, например, задание графа списками инцидентности, в которых для каждой вершины перечисляются инцидентные ей ребра. Необходимо также иметь возможность быстро пометить ребро как пройденное или проверить, пройдено ли данное ребро. Для этого подходящей структурой может служить характеристический массив на множестве ребер.

 

 

3. Алгоритм топологической  сортировки

 

Бинарным отношением на множестве A будем называть подмножество декартова произведения M x M, т.е. некоторое множество упорядоченных пар, каждый элемент которых является элементом множества A. Например, отношение > (больше) является бинарным отношением на множестве {1, 2, 3, 4} и содержит пары (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3). Будем говорить, что истинно утверждение a R b, если пара (a, b) принадлежит бинарному отношению R.

Пусть дано некоторое  бинарное отношение R на конечном множестве A. Задачей топологической сортировки является выстраивание элементов множества A в последовательность a₁, a₂, ..., a_N так, что для любой пары (a_i, a_j) такой, что истинно a_i R a_j, выполняется условие i < j.

Если представить отношение  в виде ориентированного графа (элементы множества являются вершинами, ребро  из вершины a в вершину b существует тогда и только тогда, когда истинно a R b), то задача может быть сформулирована следующим образом: перечислить вершины графа в таком порядке, чтобы для любого ребра графа его начальная вершина была перечислена раньше конечной. На рисунке слева изображен исходный граф, справа его вершины перечислены в требуемом порядке.

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

Ясно, что выполнить  топологическую сортировку возможно не в любом графе, а только в таком, в котором отсутствуют циклы. Описанный ниже алгоритм выполняет  топологическую сортировку графа без  циклов.

1. Помечаем все вершины графа как неиспользованные.
2. Ищем неиспользованную вершину, в которую не входит ни одно ребро (в соответствующем столбце матрицы смежности стоят только нули). Если такой вершины нет, то либо мы перебрали все вершины (топологическая сортировка закончена), либо в графе есть цикл (топологическая сортировка невозможна).
3. Помечаем найденную вершину как использованную, печатаем ее номер.
4. Удаляем из графа все ребра с началом в этой вершине (зануляется соответствующая строка матрицы смежности).
5. Переходим к шагу 2.

Для ускорения работы алгоритма можно хранить в  массиве количество ребер, входящих в данную вершину, и обновлять  это количество при удалении каждого  ребра.

 

4. Задача (алгоритм Дейкстры)

 

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6.

Первый по очереди  сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7. На графике изначально рассмотрена вершина №3.

Аналогичную операцию проделываем  с двумя другими соседями 1-й  вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным  и пересмотру не подлежит (то, что  это действительно так, впервые  доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.