Поиск кратчайшего пути в графе

Поиск кратчайшего пути в графе Лекция 11 51 Поиск кратчайшего пути в графе ▪ Имеется взвешенный граф 𝐺 = (𝑉, 𝐸) ▪ Каждому ребру 𝑖, 𝑗 ∈ 𝐸 назначен вес 𝑤𝑖𝑗 ▪ Заданы начальная вершина 𝑠 ∈ 𝑉 и конечная 𝑑  𝑉 ▪ Требуется найти кратчайший путь из вершины 𝑠 в вершину 𝑑 (shortest path problem) ▪ Длина пути (path length, path cost, path weight) – это сумма весов ребер, входящих в него s (source) d (destination) Длина пути в графе ▪ Длина пути (5, 4, 6, 7) = w54 + w46 + w67 = 4 + 6 + 9 = 19 s (source) d (destination) 53 Длина пути в графе ▪ Длина пути (5, 4, 6, 7) = w54 + w46 + w67 = 4 + 6 + 9 = 19 ▪ Длина пути (5, 3, 8, 7) = 3 + 2 + 16 = 21 s (source) d (destination) 54 Длина пути в графе ▪ Длина пути (5, 4, 6, 7) = w54 + w46 + w67 = 4 + 6 + 9 = 19 ▪ Длина пути (5, 3, 8, 7) = 3 + 2 + 16 = 21 ▪ Длина пути (5, 3, 4, 6, 7) = 3 + 3 + 6 + 9 = 21 s (source) d (destination) 55 Длина пути в графе ▪ Длина пути (5, 4, 6, 7) = w54 + w46 + w67 = 4 + 6 + 9 = 19 ▪ Длина пути (5, 3, 8, 7) = 3 + 2 + 16 = 21 ▪ Длина пути (5, 3, 4, 6, 7) = 3 + 3 + 6 + 9 = 21 ▪ Альтернативные пути s (source)  (5, 1, 4, 3, 8, 7)  (5, 2, 3, 8, 7) … d (destination) 56 Постановка задачи о кратчайшем пути ▪ Задача о кратчайшем пути между парой вершин (single-pair shortest path problem) Требуется найти кратчайший путь из заданной вершины 𝑠 в заданную вершину 𝑑 ▪ Задача о кратчайших путях из заданной вершины во все (single-source shortest path problem) Найти кратчайшие пути из заданной вершины 𝑠 во все ▪ Задача о кратчайшем пути в заданный пункт назначения (single-destination shortest path problem) Требуется найти кратчайшие пути в заданную вершину 𝑣 из всех вершин графа ▪ Задача о кратчайшем пути между всеми парами вершин (all-pairs shortest path problem) Требуется найти кратчайший путь из каждой вершины 𝑢 в каждую вершину 𝑣 57 Алгоритмы поиска кратчайшего пути в графе 58 Алгоритм Дейкстры ▪ Алгоритм Дейкстры (Dijkstra’s algorithm, 1959) – алгоритм поиска кратчайшего пути в графе из заданной вершины во все остальные (single-source shortest path problem) ▪ Находит кратчайшее расстояние от одной из вершин графа до всех остальных ▪ Применим только для графов без ребер отрицательного веса и петель (𝑤𝑖𝑗 ≥ 0) ▪ Эдсгер Дейкстра (Edsger Wybe Dijkstra) – нидерландский ученый (структурное программирование, язык Алгол, семафоры, распределенные вычисления) ▪ Лауреат премии Тьюринга (ACM A.M. Turing Award) 1. Дейкстра Э. Дисциплина программирования = A discipline of programming. — М.: Мир, 1978. — С. 275. 2. Дал У., Дейкстра Э., Хоор К. Структурное программирование = Structured Programming. — М.: Мир, 1975. — С. 247. 59 Алгоритм Дейкстры 1 ▪ Пример: найти кратчайший путь из вершины 1 в 10 вершину 5 ▪ Введем обозначения: 2 30  𝐻 – множество посещенных вершин  𝐷[𝑖] – текущее известное кратчайшее 50 расстояние от вершины 𝑠 до вершины 𝑖 10  𝑝𝑟𝑒𝑣[𝑖] – номер вершины, 3 предшествующей 𝑖 в пути 20 100 5 60 4 60 Алгоритм Дейкстры 1. Устанавливаем расстояние 𝐷[𝑖] от начальной вершины 𝑠 до всех остальных в ∞ 2. Полагаем 𝐷[𝑠] = 0 3. Помещаем все вершины в очередь с приоритетом 50 𝑄 (min-heap): приоритет вершины 𝑖 это значение 𝐷[𝑖] 1 10 100 2 30 10 60 3 20 D[i] 1 2 ∞ 3 ∞ 4 ∞ 5 4 5 ∞ 61 Алгоритм Дейкстры 4. Запускаем цикл из 𝑛 итераций (по числу вершин) ▪ Извлекаем из очереди 𝑄 вершину 𝑣 с минимальным приоритетом – ближайшую к 𝑠 вершину ▪ Отмечаем вершину 𝑣 как посещенную (помещаем 𝑣 во множество 𝐻) ▪ Возможно пути из 𝑠 через вершину 𝑣 стали короче, выполняем проверку: для каждой вершины 𝑢, смежной с вершиной 𝑣 и не включенной в 𝐻 , проверяем и корректируем расстояние 𝐷[𝑢] if D[v] + w(v, u) < D[u] then // Путь из s до u через (v, u) короче D[u] = D[v] + w(v, u) PrioQueueDecrease(Q, u, D[u]) prev[u] = v end if 1 1 10 100 2 30 50 5 10 60 3 20 4 𝑫[𝟐] = 𝟏𝟎 𝑫[𝟒] = 𝟑𝟎 𝑫[𝟓] = 𝟏𝟎𝟎 D[i] 10 ∞ 30 100 62 Алгоритм Дейкстры 4. Запускаем цикл из 𝑛 итераций (по числу вершин) ▪ Извлекаем из очереди 𝑄 вершину 𝑣 с минимальным приоритетом – ближайшую к 𝑠 вершину ▪ Отмечаем вершину v как посещенную (помещаем 𝑣 во множество 𝐻) ▪ Возможно пути из 𝑠 через вершину v стали короче, выполняем проверку: для каждой вершины 𝑢, смежной с вершиной 𝑣 и не включенной в 𝐻 , проверяем и корректируем расстояние 𝐷[𝑢] if D[v] + w(v, u) < D[u] then // Путь из s до u через (v, u) короче D[u] = D[v] + w(v, u) PrioQueueDecrease(Q, u, D[u]) prev[u] = v end if 1 10 100 2 2 50 30 5 10 60 3 20 4 D[3] = 60 D[i] 10 60 30 100 63 Алгоритм Дейкстры 4. Запускаем цикл из 𝑛 итераций (по числу вершин) ▪ Извлекаем из очереди 𝑄 вершину 𝑣 с минимальным приоритетом – ближайшую к 𝑠 вершину ▪ Отмечаем вершину v как посещенную (помещаем 𝑣 во множество 𝐻) ▪ Возможно пути из 𝑠 через вершину v стали короче, выполняем проверку: для каждой вершины 𝑢, смежной с вершиной 𝑣 и не включенной в 𝐻 , проверяем и корректируем расстояние 𝐷[𝑢] if D[v] + w(v, u) < D[u] then // Путь из s до u через (v, u) короче D[u] = D[v] + w(v, u) PrioQueueDecrease(Q, u, D[u]) prev[u] = v end if 1 10 100 2 30 50 5 10 60 3 20 4 4 D[3] = 50 D[5] = 90 D[i] 10 50 30 90 64 Алгоритм Дейкстры 4. Запускаем цикл из 𝑛 итераций (по числу вершин) ▪ Извлекаем из очереди 𝑄 вершину 𝑣 с минимальным приоритетом – ближайшую к 𝑠 вершину ▪ Отмечаем вершину v как посещенную (помещаем 𝑣 во множество 𝐻) ▪ Возможно пути из 𝑠 через вершину v стали короче, выполняем проверку: для каждой вершины 𝑢, смежной с вершиной 𝑣 и не включенной в 𝐻 , проверяем и корректируем расстояние 𝐷[𝑢] if D[v] + w(v, u) < D[u] then // Путь из s до u через (v, u) короче D[u] = D[v] + w(v, u) PrioQueueDecrease(Q, u, D[u]) prev[u] = v end if 1 10 100 2 30 50 5 10 60 3 20 4 D[5] = 60 D[i] 10 50 30 60 65 Алгоритм Дейкстры 4. Запускаем цикл из 𝑛 итераций (по числу вершин) ▪ Извлекаем из очереди 𝑄 вершину 𝑣 с минимальным приоритетом – ближайшую к 𝑠 вершину ▪ Отмечаем вершину 𝑣 как посещенную (помещаем 𝑣 во множество 𝐻) ▪ Возможно пути из 𝑠 через вершину 𝑣 стали короче, выполняем проверку: для каждой вершины 𝑢, смежной с вершиной 𝑣 и не включенной в 𝐻 , проверяем и корректируем расстояние 𝐷[𝑢] if D[v] + w(v, u) < D[u] then // Путь из s до u через (v, u) короче D[u] = D[v] + w(v, u) PrioQueueDecrease(Q, u, D[u]) prev[u] = v end if 1 10 100 2 30 50 5 10 60 3 20 D[i] 10 4 50 30 60 66 Алгоритм Дейкстры ▪ В массиве 𝐷[1: 𝑛] содержатся длины кратчайших путей из начальной вершины 𝑠 = 1 o o o o o 𝐷[1] – длина пути из 1 в 1 𝐷[2] – длина пути из 1 в 2 𝐷[3] – длина пути из 1 в 3 𝐷[4] – длина пути из 1 в 4 𝐷[5] – длина пути из 1 в 5 ▪ Как определить, какие вершины входят в кратчайший путь из s = 1 в d = 5? ▪ Как восстановить путь? 11 10 100 22 50 30 5 5 10 60 3 3 20 D[i] 10 4 4 50 30 60 67 Алгоритм Дейкстры ▪ Восстановление кратчайшего пути 10 ▪ Массив 𝑝𝑟𝑒𝑣[𝑖] содержит номер вершины, предшествующей 𝑖 в пути prev[i] 1 2 3 4 5 -1 1 4 1 3 ▪ Восстанавливаем путь с конца  Вершина 5  Вершина prev[5] = 3  Вершина prev[3] = 4  Вершина prev[4] = 1 Кратчайший путь (1, 4, 3, 5) 1 100 2 30 50 5 10 60 3 20 D[i] 4 10 50 30 60 68 Алгоритм Дейкстры function ShortestPath_Dijkstra(G, src, d, prev) // Input: G = (V, E), src, dst // Output: d[1:n], prev[1:n] // prev[i] - узел, предшествующий i в пути // Помещаем вершины в очередь с приоритетом for each i in V \ {src} do d[i] = Infinity prev[i] = -1 PriorityQueueInsert(Q, i, d[i]) end for d[src] = 0 prev[src] = -1 PriorityQueueInsert(Q, src, d[src]) 69 Алгоритм Дейкстры for i = 0 to n – 1 do // Извлекаем узел ближайший к начальному v = PriorityQueueRemoveMin(Q) // Отмечаем v как посещенный H = H + {v} // Цикл по смежным вершинам узла v for each u in Adj(v) \ H do // Путь через u короче текущего пути? if d[v] + w(v, u) < d[u] then d[u] = d[v] + w(v, u) PriorityQueueDecrease(Q, u, d[u]) prev[u] = v end if end for end for end function 70 Восстановление кратчайшего пути function SearchShortestPath(G, src, dst) ShortestPath_Dijkstra(G, src, d, prev) // Восстановление пути из src в dst i = dst pathlen = 1 while i != src do pathlen = pathlen + 1 i = prev[i] end while j = 0 i = dst while i != s do path[pathlen – j] = i i = prev[i] j = j + 1 end while return path[], pathlen end function T = TDijikstra + O(|V|) 71 Вычислительная сложность алгоритма Дейкстры ▪ Вычислительная сложность алгоритма Дейкстры определяется следующими факторами: 1) выбором структуры данных для хранения графа (матрица смежности, списки смежных вершин) 2) способом поиска вершины с минимальным расстоянием 𝐷[𝑖]:  Очередь с приоритетом: Binary heap – 𝑂(𝑙𝑜𝑔𝑛), Fibonacchi heap, …  Сбалансированное дерево поиска: Red-black tree – 𝑂(𝑙𝑜𝑔𝑛), AVL-tree, …  Линейный поиск – 𝑂(𝑛) 72 Алгоритм Дейкстры function ShortestPath_Dijkstra(G, src, d, prev) // Input: G = (V, E), src, dst // Output: d[1:n], prev[1:n] // prev[i] - узел, предшествующий i в пути // Помещаем вершины в очередь с приоритетом for each i in V \ {src} do d[i] = Infinity BinaryHeap prev[i] = -1 𝑂(𝑛 log 𝑛) PriorityQueueInsert(Q, i, d[i]) end for d[src] = 0 prev[src] = -1 PriorityQueueInsert(Q, src, d[src]) 𝑂(log 𝑛) 73 Алгоритм Дейкстры for i = 0 to n – 1 do // Извлекаем узел ближайший к начальному v = PriorityQueueRemoveMin(Q) BinaryHeap // Отмечаем v как посещенный 𝑂(log 𝑛) H = H + {v} // Цикл по смежным вершинам узла v for each u in Adj(v) \ H do // Путь через u короче текущего пути? if d[v] + w(v, u) < d[u] then d[u] = d[v] + w(v, u) PriorityQueueDecrease(Q, u, d[u]) prev[u] = v end if 𝑂(log 𝑛) end for end for end function ▪ В худшем случае функция PriorityQueueRemoveMin() вызывается 𝑛 раз, суммарная сложность 𝑂(𝑛 log 𝑛) ▪ В худшем случае функция PriorityQueueDecrease() вызывается для каждого из 𝑚 ребер графа, суммарная сложность 𝑂(𝑚 log 𝑛) 74 Вычислительная сложность алгоритма Дейкстры ▪ Вариант 1. 𝐷[𝑖] – это массив или список (поиск за время 𝑂(𝑛)) 𝑇𝐷𝑖𝑗𝑖𝑘𝑠𝑡𝑟𝑎 = 𝑂 𝑛2 + 𝑚 = 𝑂( 𝑉 2 + 𝐸 ) ▪ Вариант 2. 𝐷[𝑖] хранятся в бинарной куче (Binary heap) 𝑇𝐷𝑖𝑗𝑖𝑘𝑠𝑡𝑟𝑎 = 𝑂 𝑛 log 𝑛 + 𝑚 log 𝑛 = 𝑂((𝑛 + 𝑚) log 𝑛) ▪ Вариант 3. 𝐷[𝑖] хранятся в Фибоначчиевой куче (Fibonacci heap) 𝑇𝐷𝑖𝑗𝑖𝑘𝑠𝑡𝑟𝑎 = 𝑂 𝑚 + 𝑛 log 𝑛 ▪ Вариант 4. … ▪ В ориентированных ациклических графах (Directed acyclic graph) кратчайший путь можно найти за время 𝑂(𝑛) 75 Разреженные и насыщенные графы Вариант реализации алгоритма Дейкстры Насыщенный граф 𝑚 = 𝑂(𝑛2 ) Разреженный граф 𝑚 = 𝑂(𝑛) Вариант 1 D[i] – это массив (поиск за время 𝑂(𝑛)) 𝑇 = 𝑂 𝑛2 + 𝑚 = 𝑶(𝒏𝟐 ) 𝑇 = 𝑂 𝑛2 + 𝑚 = 𝑶(𝒏𝟐 ) Вариант 2 D[i] хранятся в бинарной куче 𝑇 = 𝑂 𝑛 log 𝑛 + 𝑚 log 𝑛 = 𝑶(𝒏𝟐 𝐥𝐨𝐠 𝒏) 𝑇 = 𝑂 𝑛 log 𝑛 + 𝑚 log 𝑛 = 𝑶 𝒏 𝐥𝐨𝐠 𝒏 Вариант 3 D[i] хранятся в Фибоначчиевой куче 𝑇 = 𝑂 𝑚 + 𝑛 log 𝑛 = 𝑶(𝒏𝟐 ) 𝑇 = 𝑂 𝑛 + 𝑛 log 𝑛 = 𝑶(𝒏 𝐥𝐨𝐠 𝒏) 76 Алгоритм Дейкстры + бинарная куча ▪ Необходимые операции над очередью с приоритетом  int heap_insert(struct heap *h, int key, int value)  int heap_removemin(struct heap *h)  void heap_decreasekey(struct heap *node, int key) 77 Алгоритм Дейкстры + бинарная куча ▪ void heap_decreasekey(struct heap *node, int key) ▪ Изменяем у узла node приоритет на priority ▪ Восстанавливаем свойства кучи – поднимаем элемент вверх по дереву (min-heap) Prio: 3 Value: 6 Prio: 8 Value: 1 swap Prio: 13 Prio: 45 Value: 2 Value: 3 Prio: 9 Value: 4 heap_decreasekey(node, 2) 78 Литература ▪ Описание алгоритма Дейкстры в [CLRS, С. 696] 79