Кратчайшие расстояния на графах

Дисциплина «Алгоритмы и структуры данных» Лекция № 11 Кратчайшие расстояния на графах Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Пример использования матричной формы представления графа: обнаружение цепей и циклов Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму). 1 2 3 1 1 1 2 1 1 3 1 1 A = 2 3 Произвольная цепь длиной 2 (k=2)будет, если A[i][0]=1 и A[i][1]=1 и A[i][2]=1 и A[i][3]=1 и строка i логическое умножение A[0][j]=1или A[1][j]=1 или A[2][j]=1 или A[3][j]=1 столбец j логическое сложение Пример использования матричной формы представления графа: обнаружение цепей и циклов Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму). 1 2 3 1 1 1 2 1 1 3 1 1 A = 2 3 A[i][0]=1 * A[i][1]=1 * A[i][2]=1 * A[i][3]=1 * A[0][j]=1 A[1][j]=1 A[2][j]=1 A[3][j]=1 = A * A = A2, т.е. Aк + + + = Пример использования матричной формы представления графа: обнаружение цепей и циклов Логическое умножение матрицы на себя: 1 M2 = M  M матрица путей длины 2 M2 = 2 1 1 1 1 1  1 2 3 1 1 1 1 =1 1 1 1 2 1 1 3 1 3 M2[2][0] = 0·0 + 1·1 + 0·0 + 1·1 = 1 маршрут 2-1-0 маршрут 2-3-0 Пример использования матричной формы представления графа: обнаружение цепей и циклов Матрица существования путей длины 3: M3 = M 2  M M3 = M4 = 1 1 1 1 1 1 1 1 1 1 1   2 1 2 3 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 2 3 1 1 1 = 1 1 1 1 2 1 1 1 3 1 = 1 3 на главной диагонали – циклы! Пример использования матричной формы представления графа: обнаружение цепей и циклов: Cохранение информации о цепях и циклов длиной не более k 1 Логическое сложение матрицы на себя (k>1): k Mk = Mk-1 or M M2 = 1 1 1 1 1  2 1 2 3 1 1 1 1 =1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 M2 = 1 1 1 1 1 2 1 1 1 1 1 1 3 1 1 1 1 or = 3 Пример использования матричной формы представления графа: достижимость узлов Пусть для графа G=(V,Е) имеется матрица смежности A: 1 только в том случае, если есть дуга i  j, (i,j) ∈ E a[i,j] = 0, если такой дуги не существует. Пример использования матричной формы представления графа: достижимость узлов Пусть для графа G=(V,Е) имеется матрица смежности A : 1 только в том случае, если есть дуга i  j, (i,j) ∈ E ; A[i,j] = 0, если такой дуги не существует. Мы хотим вычислить матрицу M такую, что 1, тогда и только тогда, когда ∃ путь от вершины i до вершины j M[i,j] = 0, в противном случае. Матрицу M часто называют транзитивным замыканием матрицы смежности A. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) i j Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) k i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) М[i][k] k М[k][j] i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) М[i][j] = М[i][j] or (М[i][k] and М[k][j]) М[i][k] k М[k][j] i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) М[i][j] = М[i][j] or (М[i][k] and М[k][j]); М[i][k] k М[k][j] i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) М[i][j] = М[i][j] or (М[i][k] and М[k][j]) М[i][k] k М[k][j] i j М[i][j] М[i][j] = М[i][j] or (М[i][k] and М[k][j]) Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: достижимость узлов (Алгоритм Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) М[i][j] = М[i][j] or (М[i][k] and М[k][j]); М[i][k] k М[k][j] i j М[i][j] Задача: Требуется определить: достижим узел j из узла i, т.е. определить, существует ли на графе какой-либо путь (цепь) из узла i в узел j. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) Определим матрицу кратчайших расстояний F[|V|][|V|]: F[i][j] – (кратчайшее) расстояние между узлом i и узлом j F[i][k] k F[k][j] i j F[i][j] Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) Определим матрицу кратчайших расстояний F[|V|][|V|]: F[i][j] – (кратчайшее) расстояние между узлом i и узлом j F[i][k] k F[k][j] i j F[i][j] Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k! Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) F[i][j] = min(=F[i][j], (F[i][k] + F[k][j]) ) F[i][k] k F[k][j] i j F[i][j] Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k! Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) F[i][j] = F[i][j] > (F[i][k] + F[k][j]) ? (F[i][k] + F[k][j]) : F[i][j]; F[i][k] k + F[k][j] i j F[i][j] Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k! Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) if ( F[i][j] > F[i][k] + F[k][j] ) F[i][j] = F[i][k] + F[k][j]; F[i][k] k + F[k][j] i j F[i][j] Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k! Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Пример использования матричной формы представления графа: нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) ! Нет информации о маршруте, только кратчайшие расстояния! for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) if ( F[i][j] > F[i][k] + F[k][j] ) F[i][j] = F[i][k] + F[k][j]; F[i][k] k + F[k][j] i j F[i][j] Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k! Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. Нахождение попарных кратчайших расстояний (алгоритм Флойда-Уоршала) с указанием (сохранение) маршрута for ( i = 0; i < N; i ++ ) Признак дуги { for ( j = 0; j < N; j ++ ) {F[i,j]=C[i,j]; p[i][j] = -1; } F[i,i]=0; } «убираем» for ( k = 0; k < N; k ++ ) петли for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) if ( F[i][j] > F[i][k] + F[k][j] ) { F[i][j] = F[i][k] + F[k][j]; p[i][j] = k; } Путь из i в j через k ? Какова сложность алгоритма? O(N3) Кратчайшие пути (алгоритм Дейкстры) Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов. Строго: Пусть дан связный граф G=(V,E) с N вершинами, веса ребер заданы матрицей С. Найти кратчайшие расстояния от заданной вершины (источника) до всех остальных. Алгоритм Дейкстры (E.W. Dijkstra, 1959) 4 9 6 5 расстояний) 2 11 3 2 14 9 15 10 7 1 1) присвоить всем вершинам метку unvisited, кроме источника. Отметить источник как visited. 2) для каждой вершины j хранить значение длины пути от источника до неё самой. (в начале алгоритма это значение равно … 3) … C[источник, j]. (инициализация массива кратчайших 4) среди нерассмотренных вершин найти вершину w с наименьшим значением в узле, отметить вершину w как посещенную; 5) для каждой необработанной вершины i: если путь к вершине i через вершину w меньше существующего в ней значения, заменить значение на новое расстояние,; 6) если остались необработанные вершины, то перейти к шагу 4; 26 7) значение в узле = минимальное расстояние. Алгоритм Дейкстры ∞ 5 14 2 ∞ 2 9 ∞ 4 9 11 7 11 9 4 2 9 9 2 ∞ 7 9 7 2 9 9 2 ∞ 14 7 4 20 11 7 7 2 9 15 1 7 4 20 9 6 2 9 9 2 7 3 20 11 15 10 3 22 11 10 7 14 15 1 9 2 5 3 20 11 6 10 3 ∞ 4 9 5 6 5 15 1 9 14 14 15 1 7 11 3 20 11 10 ∞ 11 10 2 6 5 14 9 2 15 1 14 ∞ ∞ 6 5 3 10 14 6 4 9 1 7 27 Реализация алгоритма Дейкстры Массивы: 1) массив mark, такой что mark[i]=1, если вершина уже рассмотрена, и mark[i]=0, если нет. 2) массив D, такой что D[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i; 3) массив p, такой что p[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути. Инициализация: 1) заполнить массив mark нулями (вершины не обработаны); 2) записать в D[i] значение C[x][i], i=0..N-1; 3) заполнить массив p значением … 4) записать mark[x]=1, p[x]=… (нужно ли?). 4 9 14 6 5 14 2 9 9 2 11 7 3 15 10 ∞ 1 7 ∞ 1 2 3 4 5 mark 1 D 7 9 ∞ ∞ 14 p 28 Реализация алгоритма Дейкстры Массивы: 1) массив mark, такой что mark[i]=1, если вершина уже рассмотрена, и mark[i]=0, если нет. 2) массив D, такой что D[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i; 3) массив p, такой что p[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути. Инициализация: 1) заполнить массив mark нулями (вершины не обработаны); 2) записать в D[i] значение C[x][i], i=0..N-1; 3) заполнить массив p значением p[i] = x; 4) записать mark[x]=1, p[x]= -1 (или p[x]= х) – признак 4 9 14 6 5 14 2 9 9 2 11 7 3 15 10 ∞ 1 7 ∞ источника 1 2 3 4 5 mark 1 D 7 9 ∞ ∞ 14 p 29 Реализация алгоритма Дейкстры Основной цикл: 1) если все вершины рассмотрены, то стоп. 2) среди всех нерассмотренных вершин (mark[i]=0) найти вершину w, для которой D[i] – минимальное; w = i; 3) записать mark[w]=1; 4) для всех непосещенных вершин j: если путь в вершину j через вершину w короче, чем найденный ранее кратчайший путь, т.е. D[w]+C[w][j] < D[j], то запоминаем его D[j]=D[w]+C[w][j] и p[j]=w. Шаг 1: 4 9 14 6 5 14 2 9 9 2 7 3 22 11 1 2 3 4 5 mark 1 1 D 7 9 22 ∞ 14 p 1 15 10 ∞ 1 7 30 Реализация алгоритма Дейкстры Шаг 2: 11 9 2 2 9 11 7 1 11 9 4 20 Шаг 3: 2 3 4 5 3 20 mark D 1 1 1 7 9 20 ∞ 11 p 2 2 1 2 3 4 5 mark 1 1 1 1 D 7 9 20 20 11 p 2 5 2 7 6 5 2 9 9 2 7 3 20 11 15 10 1 15 10 14 6 5 14 ∞ 4 9 1 7 ! Дальше массивы не изменяются! 31 Как вывести маршрут? Результат работа алгоритма Дейкстры: 1 2 3 4 5 mark 1 1 1 1 1 1 D 7 9 20 20 11 p 2 5 2 длины путей Маршрут из вершины 0 в вершину 4: 4 5 2 Вывод маршрута в вершину i (использование массива p): 1) установить z=i; 2) пока p[z]!=z: присвоить z=p[z] и вывести z Сложность алгоритма Дейкстры: два вложенных цикла по N шагов O(N2) 32 Спасибо за внимание!