Графы

Графы Лекция 10 Понятие графа ▪ Граф (graph) – это совокупность непустого множества 𝑉 вершин и множества 𝐸 ребер 𝐺 = 𝑉, 𝐸 , 𝑛 = 𝑉 , 𝑚 = |𝐸|, 𝑉 = 1,2, … , 𝑛 , 𝐸 = { 𝑢1 , 𝑣1 , 𝑢2 , 𝑣2 , … , (𝑢𝑚 , 𝑣𝑚 )} vertex edge 𝑽 = 𝟏, 𝟐, 𝟑, 𝟒, 𝟓 𝑬 = 𝟏, 𝟓 , 𝟐, 𝟓 , 𝟐, 𝟑 , 𝟐, 𝟒 , (𝟑, 𝟒) (1, 5) и (5, 1) – это одно и тоже ребро 2 Виды графов Граф ы (graphs) Неориентированные граф ы (undirected graphs) Ориентированные граф ы (directed graphs) Ребра (edges) не имеют направлений Ребра – дуги (arcs, edges) имеют направления (1, 2) и (2, 1) – одно и тоже ребро (1, 3) и (3, 1) – разные дуги! 3 Основные определения Вершина (vertex, node) Ребро (edge, link) Смежные вершины (adjacent vertices) Ребро (4, 6) инцидентно (incident) вершинам 4 и 6 Путь (path) – последовательность вершин, в которой следующая вершина (после первой) является смежной с предыдущей (все вершины и ребра в пути различны) Путь: (10, 8, 3, 5) 4 Основные определения Цикл (cycle) – путь, в котором первая и последняя вершины совпадают: (4, 6, 7, 8, 3, 4) Степень вершины (vertex degree) – количество ребер, инцидентных вершине deg(7) = 2, deg(1) = 3 Связный граф (connected graph) – граф, в котором существует путь из каждой вершины в любую другую 5 Основные определения ▪ Взвешенный граф (weighted graph) – это граф, ребрам (дугам) которого назначены веса ▪ Вес ребра (𝑖, 𝑗) обозначим как 𝑤𝑖𝑗 𝑤34 = 5, 𝑤42 = 24, … 6 Основные определения Полный граф (complete graph) – это граф, в котором каждая пара различных вершин смежна (каждая вершина соединена со всеми) Количество ребер в полном неориентированном графе: 𝑛(𝑛 − 1) 𝑚= 2 Насыщенность D неориентированного граф а (density): 2𝑚 𝐷= 𝑛(𝑛 − 1) У полного графа насыщенность D = 1 2∙4 8 𝐷= = = 0.66 4 ∙ 3 12 7 Основные определения Насыщенный граф (dense graph) – это граф, в котором количество ребер близко к максимально возможному 𝐸 = 𝑂( 𝑉 2 ) 𝐷= 2∙19 7∙6 = 0.9, 𝐷 > 0.5 Разреженный граф (sparse graph) – граф, в котором количество ребер близко к количеству вершин в графе 𝐸 = 𝑂(|𝑉|) 𝐷= 2∙7 7∙6 = 0.33, 𝐷 < 0.5 8 Представление графов в памяти ▪ Представление графа в памяти (формат его хранения) определяет вычислительную сложность операций над графом и объем требуемой памяти ▪ Основные способы представления графов в памяти:  Матрица смежности (adjacency matrix) эффективна для насыщенных графов  Списки смежных вершин (adjacency lists) эффективны для разреженных графов 9 Матрица смежности ▪ Матрица A смежности (adjacency matrix) – это матрица n × n элементов, в которой 1, если 𝑖, 𝑗 ∈ 𝐸, 𝑎𝑖𝑗 = ቊ 0, иначе. ▪ Объем требуемой памяти 𝑂( 𝑉 2 ) ▪ Быстрое определение присутствия ребра (𝑖, 𝑗) в графе ▪ За время 𝑂(1) получаем доступ к элементу 𝑎𝑖𝑗 матрицы Эффективна для насыщенных графов (|𝐸| ≈ |𝑉|2) 10 Матрица смежности ▪ Какого размера граф можно разместить в оперативной памяти объемом 8 Гб, используя матрицу смежности? int a[n][n]; 11 Матрица смежности ▪ Какого размера граф можно разместить в оперативной памяти объемом 8 ГиБ, используя матрицу смежности? int a[n][n]; sizeof(int)= 4 байта 8 ГиБ = 8 ∙ 230 байт 8 ∙ 230 / 4 = 2 ∙ 230 – можно разместить 231 = 2 147 483 648 элементов типа int 𝑛= 231 = 46340 – количество строк и столбцов int a[46340][46340]; ▪ Надо учесть, что часть памяти занята ОС и другими программами (предполагаем, что доступно 90% памяти (~ 7 ГиБ), тогда n = 43347) ▪ ▪ ▪ ▪ 12 Списки смежных вершин ▪ Списки смежных вершин (adjacency lists) – это массив 𝐴[𝑛], каждый элемент 𝐴[𝑖] которого содержит список узлов, смежных с вершиной Эффективен для разреженных графов (|𝐸| ≈ |𝑉|) 13 Списки смежных вершин ▪ Реализация списка смежных вершин на основе массивов 𝐴[𝑛 + 1] и 𝐿[2𝑚] ▪ Список смежных вершин узла 𝑖: 𝐿[𝐴[𝑖]], 𝐿[𝐴[𝑖] + 1], … , 𝐿[𝐴[𝑖 + 1] – 1] 1 A: 1 2 3 4 3 7 10 12 13 15 – индексы начала и конца списка смежных вершин в массиве L 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 4 1 3 5 6 2 4 6 1 3 2 2 3 6 L: 5 6 7 14 Списки смежных вершин // Обход смежных вершин узла i for (j = A[i]; j < A[i + 1]; j++) { v = L[j]; // Обработать вершину v } 𝑻 = 𝑶(𝒎) ▪ Количество смежных узлов вершины 𝑖: 𝐴[𝑖 + 1] – 𝐴[𝑖] A: L: 1 2 3 4 5 6 7 1 3 7 10 12 13 15 – индексы начала и конца списка смежных вершин в массиве L 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 4 1 3 5 6 2 4 6 1 3 2 2 3 6 15 Графы в реальной жизни ▪ Задан начальный пользователь (узел графа) ▪ Как, начиная со стартового узла, найти пользователя с заданным именем? ▪ Как перебрать всех пользователей и применить к ним некоторую процедуру?  изменить профиль  вычислить число пользователей старше 20 лет Граф социальной сети 16 Графы в реальной жизни ▪ Обход граф а (graph traversal) – это процедура перебора (посещения) всех вершин графа, начиная с заданной 17 Поиск в глубину (depth-first search) ▪ Поиск в глубину (depth-first search – DFS) – процедура посещения всех вершин графа, начиная с заданного узла v ▪ Сперва посещаем (обрабатываем) все самые “глубокие” вершины function DFS(v) visited[v] = true // Обрабатываем данные вершины v for each u in Adj(v) do // Перебор смежных вершин if visited[u] = false then DFS(u) // Рекурсивно обрабатываем вершину u end if end for end function 18 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 19 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 20 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 21 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 22 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ▪ Все смежные вершины узла 5 ... посещены end for ▪ Возвращаемся к узлу 3 ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 23 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 24 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 25 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... ▪ Все смежные вершины узла 6 посещены end for ▪ Возвращаемся к узлу 7, затем к 8 ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 26 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ▪ Все смежные вершины узла 9 ... посещены end for ▪ Возвращаемся к узлу 8 ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 27 Поиск в глубину (depth-first search) ▪ Обход в глубину с вершины 2: DFS(2) for each u in Adj(2) do ... end for ▪ Обход в глубину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в глубину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 28 Поиск в ширину (breadth-first search) ▪ Поиск в ширину (breadth-first search – BFS, обход в ширину) – процедура посещения всех вершин графа, начиная с заданного узла v ▪ Сперва посещаем (обрабатываем) свои дочерние вершины 29 Поиск в ширину (breadth-first search) function BFS(v) visited[v] = true // Обрабатываем вершину v QueueEnqueue(v) // Помещаем v в очередь вершин while QueueSize() > 0 do u = QueueDequeue() // Извлекаем вершину for each x in Adj(u) do if visited[x] = false then QueueEnqueue(x) visited[x] = true // Обрабатываем узел x end if end for end while end function 30 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 2 ▪ В очереди: 1, 3, 5 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 31 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 1 ▪ В очереди: 3, 5, 4 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 32 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 3 ▪ В очереди: 5, 4, 8 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 33 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 5 ▪ В очереди: 4, 8 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 34 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 4 ▪ В очереди: 8, 6 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 35 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 8 ▪ В очереди: 6, 7, 9, 10 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 36 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 6 ▪ В очереди: 7, 9, 10 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 37 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 7 ▪ В очереди: 9, 10 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 38 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 9 ▪ В очереди: 10 ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 39 Поиск в ширину (breadth-first search) ▪ Обход в ширину с вершины 2: BFS(2) ▪ Извлекли из очереди: 10 ▪ В очереди: ▪ Обход в ширину графа, представленного матрицей смежности, имеет трудоемкость 𝑂(|𝑉|2) ▪ Обход в ширину графа, представленного списком смежности, имеет трудоемкость 𝑂(|𝑉| + |𝐸|) 40 Реализация графа на базе матрицы смежности #include #include #include "queue_array.h" struct graph { int nvertices; int *m; int *visited; }; /* Число вершин */ /* Матрица n x n */ 41 Реализация графа на базе матрицы смежности struct graph *graph_create(int nvertices) { struct graph *g; TCreate = O(n2) g = malloc(sizeof(*g)); g->nvertices = nvertices; g->visited = malloc(sizeof(int) * nvertices); g->m = malloc(sizeof(int) * nvertices * nvertices); graph_clear(g); // Опционально, O(n^2) return g; Memory = O(n2) } 42 Реализация графа на базе матрицы смежности void graph_clear(struct graph *g) { int i, j; } for (i = 0; i < g->nvertices; i++) { g->visited[i] = 0; for (j = 0; j < g->nvertices; j++) { g->m[i * g->nvertices + j] = 0; } } TClear = O(n2) 43 Реализация графа на базе матрицы смежности void graph_free(struct graph *g) { free(g->m); free(g); } 44 Реализация графа на базе матрицы смежности /* * graph_set_edge: Назначает ребру (i, j) вес w * i, j = 1, 2, ..., n */ void graph_set_edge(struct graph *g, int i, int j, int w) { g->m[(i - 1) * g->nvertices + j - 1] = w; g->m[(j - 1) * g->nvertices + i - 1] = w; } int graph_get_edge(struct graph *g, int i, int j) { return g->m[(i - 1) * g->nvertices + j - 1]; } 45 Обход графа в глубину (DFS) – рекурсивная версия void graph_dfs(struct graph *g, int v) { int i; g->visited[v - 1] = 1; printf("Vertex %d\n", v); } for (i = 0; i < g->nvertices; i++) { if (g->m[(v - 1) * g->nvertices + i] > 0 && g->visited[i] == 0) { graph_dfs(g, i + 1); } } TDFS = O(n2) 46 Обход графа в ширину (BFS) void graph_bfs(struct graph *g, int v) { int i, j; struct queue *q; for (i = 0; i < g->nvertices; i++) g->visited[i] = 0; // Создаем очередь q = queue_create(g->nvertices); // Обрабатываем стартовую вершину g->visited[v - 1] = 1; printf("Vertex %d\n", v); queue_enqueue(q, v - 1); 47 Обход графа в ширину (BFS, продолжение) } while (queue_size(q) > 0) { i = queue_dequeue(q); for (j = 0; j < g->nvertices; j++) { if (g->m[i * g->nvertices + j] > 0 && g->visited[j] == 0) { queue_enqueue(q, j); g->visited[j] = 1; printf("Vertex %d\n", j + 1); } } } queue_free(q); TBFS = O(n2) 48 Пример int main() { struct graph *g; g = graph_create(10); graph_set_edge(g, 1, 2, 1); graph_set_edge(g, 1, 4, 1); /* ... */ printf("DFS:\n"); graph_dfs(g, 2); printf("BFS:\n"); graph_bfs(g, 2); } graph_free(g); return 0; 49 Литература ▪ Доказательство вычислительной сложности процедур BFS и DFS [Aho, C. 217], [CLRS, С. 630, С. 639] ▪ Формат хранения графов в сжатом виде  Compressed Sparse Row Graph (CSR) http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/compressed_sparse_row.html  Sparse matrix http://en.wikipedia.org/wiki/Sparse_matrix 50 Поиск кратчайшего пути в графе 51 поиск кратчайшего пути в графе ▪ Имеется взвешенный граф G = (V, E) ▪ Каждому ребру (i, j)  E назначен вес wij ▪ Заданы начальная вершина s  V и конечная d  V ▪ Требуется найти кратчайший путь из вершины s в вершину d (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 ▪ Альтернативные пути  (5, 1, 4, 3, 8, 7)  (5, 2, 3, 8, 7)  … s (source) d (destination) 56 постановка задачи о кратчайшем пути ▪ Задача о кратчайшем пути между парой вершин (single-pair shortest path problem) Требуется найти кратчайший путь из заданной вершины s в заданную вершину d ▪ Задача о кратчайших путях из заданной вершины во все (single-source shortest path problem) Найти кратчайшие пути из заданной вершины s во все ▪ Задача о кратчайшем пути в заданный пункт назначения (single-destination shortest path problem) Требуется найти кратчайшие пути в заданную вершину v из всех вершин графа ▪ Задача о кратчайшем пути между всеми парами вершин (all-pairs shortest path problem) Требуется найти кратчайший путь из каждой вершины u в каждую вершину v 57 Алгоритмы поиска кратчайшего пути в графе 58 Алгоритм Дейкстры ▪ Алгоритм Дейкстры (Dijkstra’s algorithm, 1959) – алгоритм поиска кратчайшего пути в графе из заданной вершины во все остальные (single-source shortest path problem) ▪ Находит кратчайшее расстояние от одной из вершин графа до всех остальных ▪ Применим только для графов без ребер отрицательного веса и петель (wij ≥ 0) ▪ Эдсгер Дейкстра (Edsger Wybe Dijkstra) – нидерландский ученый (структурное программирование, язык Алгол, семафоры, распределенные вычисления) ▪ Лауреат премии Тьюринга (ACM A.M. Turing Award) 1. Дейкстра Э. Дисциплина программирования = A discipline of programming. — М.: Мир, 1978. — С. 275. 2. Дал У., Дейкстра Э., Хоор К. Структурное программирование = Structured Programming. — М.: Мир, 1975. — С. 247. 59 Алгоритм Дейкстры ▪ Пример: найти кратчайший путь из вершины 1 в вершину 5 1 ▪ Введем обозначения: 10  H – множество посещенных вершин 100 2  D[i] – текущее известное 30 кратчайшее расстояние 50 5 от вершины s до вершины i 10  prev[i] – номер вершины, 60 3 предшествующей i в пути 20 4 60 Алгоритм Дейкстры 1. Устанавливаем расстояние D[i] от начальной вершины s до всех остальных в ∞ 10 2 2. Полагаем D[s] = 0 50 3. Помещаем все вершины в очередь с приоритетом Q (min-heap): 3 приоритет вершины i это значение D[i] D[i] 1 2 3 ∞ ∞ 1 4 5 ∞ ∞ 100 30 5 10 60 20 4 61 Алгоритм Дейкстры 1 1 10 4. Запускаем цикл из n итераций (по числу вершин) 1. 2. 3. Извлекаем из очереди Q вершину v с 2 минимальным приоритетом – ближайшую к s вершину Отмечаем вершину v как посещенную 50 (помещаем v во множество H) Возможно пути из s через вершину v стали 3 короче, выполняем проверку: для каждой вершины u, смежной с вершиной v и не включенной в H, проверяем и корректируем расстояние D[u] 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 100 30 5 10 60 20 4 D[2] = 10 D[4] = 30 D[5] = 100 D[i] 10 ∞ 30 100 62 Алгоритм Дейкстры 11 10 4. Запускаем цикл из n итераций (по числу вершин) 1. 2. 3. Извлекаем из очереди Q вершину v с 2 минимальным приоритетом – ближайшую к s 2 вершину Отмечаем вершину v как посещенную 50 (помещаем v во множество H) Возможно пути из s через вершину v стали 3 короче, выполняем проверку: для каждой вершины u смежной с вершиной v и не включенной в H проверяем и корректируем расстояние D[u] 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 100 30 5 10 60 20 4 D[3] = 60 D[i] 10 60 30 100 63 Алгоритм Дейкстры 11 10 4. Запускаем цикл из n итераций (по числу вершин) 1. 2. 3. Извлекаем из очереди Q вершину v с 2 минимальным приоритетом – ближайшую к s 2 вершину Отмечаем вершину v как посещенную 50 (помещаем v во множество H) Возможно пути из s через вершину v стали 3 короче, выполняем проверку: для каждой вершины u смежной с вершиной v и не включенной в H проверяем и корректируем расстояние D[u] 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 D[i] 10 100 30 5 10 60 20 44 D[3] = 50 D[5] = 90 50 30 90 64 Алгоритм Дейкстры 11 10 4. Запускаем цикл из n итераций (по числу вершин) 1. 2. 3. Извлекаем из очереди Q вершину v с 2 минимальным приоритетом – ближайшую к s 2 вершину Отмечаем вершину v как посещенную 50 (помещаем v во множество H) Возможно пути из s через вершину v стали короче, выполняем проверку: для каждой 33 вершины u смежной с вершиной v и не включенной в H проверяем и корректируем расстояние D[u] 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 D[i] 10 100 30 5 10 60 20 4 4 D[5] = 60 50 30 60 65 Алгоритм Дейкстры 11 10 4. Запускаем цикл из n итераций (по числу вершин) 1. 2. 3. Извлекаем из очереди Q вершину v с 2 минимальным приоритетом – ближайшую к s 2 вершину Отмечаем вершину v как посещенную 50 (помещаем v во множество H) Возможно пути из s через вершину v стали 3 короче, выполняем проверку: для каждой 3 вершины u смежной с вершиной v и не включенной в H проверяем и корректируем расстояние D[u] 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 D[i] 10 100 30 5 5 10 60 20 4 4 50 30 60 66 Алгоритм Дейкстры ▪ В массиве D[1:n] содержатся длины кратчайших путей из начальной вершины s = 1 o o o o o D[1] – длина пути из 1 в 1 D[2] – длина пути из 1 в 2 D[3] – длина пути из 1 в 3 D[4] – длина пути из 1 в 4 D[5] – длина пути из 1 в 5 11 10 22 50 100 30 5 5 10 3 3 60 20 4 4 D[i] 0 10 50 30 60 ▪ Как определить, какие вершины входят в кратчайший путь из s = 1 в d = 5? ▪ Как восстановить путь? 67 Алгоритм Дейкстры ▪ Восстановление кратчайшего пути 10 ▪ Массив prev[i] содержит номер вершины, предшествующей i в пути prev[i] 1 2 3 4 5 -1 1 4 1 3 2 50 ▪ Восстанавливаем путь с конца  Вершина 5  Вершина prev[5] = 3  Вершина prev[3] = 4  Вершина prev[4] = 1 Кратчайший путь (1, 4, 3, 5) 1 100 30 5 10 60 3 20 D[i] 10 50 4 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) способом поиска вершины с минимальным расстоянием D[i]:  Очередь с приоритетом: Binary heap – O(logn), Fibonacchi heap, …  Сбалансированное дерево поиска: Red-black tree – O(logn), AVL-tree, …  Линейный поиск – O(n) 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 prev[i] = -1 PriorityQueueInsert(Q, i, d[i]) end for d[src] = 0 prev[src] = -1 PriorityQueueInsert(Q, src, d[src]) BinaryHeap 𝑂(𝑛 log 𝑛) 𝑂(log 𝑛) 73 алгоритм дейкстры for i = 0 to n – 1 do // Извлекаем узел ближайший к начальному v = PriorityQueueRemoveMin(Q) // Отмечаем v как посещенный H = H + {v} BinaryHeap 𝑂(log 𝑛) // Цикл по смежным вершинам узла v for each u in Adj(v) \ H do // Путь через u короче текущего пути? if d[v] + w(v, u) < d[u] then 𝑂(log 𝑛) d[u] = d[v] + w(v, u) PriorityQueueDecrease(Q, u, d[u]) prev[u] = v end if ▪ В худшем случае функция PriorityQueueRemoveMin() вызывается n end for раз, суммарная сложность 𝑂(𝑛 log 𝑛) end for ▪ В худшем случае функция PriorityQueueDecrease() вызывается для end function каждого из m ребер графа, суммарная сложность 𝑂(𝑚 log 𝑛) 74 вычислительная сложность алгоритма дейкстры ▪ Вариант 1. D[i] – это массив или список (поиск за время O (n)) 𝑇𝐷𝑖𝑗𝑖𝑘𝑠𝑡𝑟𝑎 = 𝑂 𝑛2 + 𝑚 = 𝑂( 𝑉 2 + 𝐸 ) ▪ Вариант 2. D[i] хранятся в бинарной куче (Binary heap) 𝑇𝐷𝑖𝑗𝑖𝑘𝑠𝑡𝑟𝑎 = 𝑂 𝑛 log 𝑛 + 𝑚 log 𝑛 = 𝑂(𝑚 log 𝑛) ▪ Вариант 3. D[i] хранятся в Фибоначчиевой куче (Fibonacci heap) 𝑇𝐷𝑖𝑗𝑖𝑘𝑠𝑡𝑟𝑎 = 𝑂 𝑚 + 𝑛 log 𝑛 ▪ Вариант 4. … ▪ В ориентированных ациклических графах (Directed acyclic graph) кратчайший путь можно найти за время O (n) 75 разреженные и насыщенные графы Насыщенный граф Разреженный граф 𝑚 = 𝑂(𝑛2 ) 𝑚 = 𝑂(𝑛) Вариант 1 D[i] – это массив (поиск за время O(n)) 𝑇 = 𝑂 𝑛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