Кратчайшие пути в графе. Топологическая сортировка - Презентация

КРАТЧАЙШИЕ пути в графе , Топологическая сортировка Лекция 17-18План лекции Кратчайшие пути Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршелла Топологическая СОРТИРОВКАКРАТЧАЙШИЕ пути Пусть G = (V, E) - ориентированный граф и w : E ? R - функция стоимости ребер G Длиной ребра e называется значение w (e) Длиной пути p = (v 0 , v 1 , … , v k ) называется сумма w(p) = ? w(v i-1 , v i ) длин ребер, входящих в РКРАТЧАЙШИЕ пути Длиной кратчайшего пути из u в v называется ? (u , v) = min {w(p) | p = (u, …, v) путь в графе G } Считаем минимум пустого множества min ? = ? Кратчайшим путем из u в v называется путь из u в v , для которого w(p) = ? (u, v) Кратчайших путей может быть НЕСКОЛЬКОПРИМЕР 10 2 3 6 1 8 5 7 4 9 1 1 1 2 2 2 3 4 3 3 4 4 5 5 5 Кратчайшие пути из вершины 10: V Длина Путь через 1 3 2 2 2 3 3 4 6 2, 1 5 4 2 6 4 3 7 8 2, 8 или 3 , 6 8 6 2 9 7 2, 8Корректность определения и ребра отрицательной длины Условие w(e) > = 0 можно заменить на менее строгое условие отсутствия циклов отрицательной длины Если циклов отрицательной длины нет, то длина кратчайшего пути определена корректно Кратчайший путь не содержит циклов Путей без циклов конечное число Если есть цикл отрицательной длины, то для любых вершин u, v из такого цикла ? (u, v) = - ? , но кратчайшего пути нет длину любого пути из u в v можно уменьшить, обойдя цикл еще один РАЗАЛГОРИТМ Дейкстры - схема Эдсгер Вибе Дейкстра 1930 - 2002 Edsger Wybe Dijkstra Dijkstra , E. W. Numerische Mathematik 1: 269-271.Алгоритм Дейкстры - схема Вычисляем расстояния от вершины-источника до остальных вершин графа Строим множество S вершин графа, кратчайшие расстояния от которых до источника известны На каждом шаге добавляем в S вершину v min , которая ближе всего к источнику среди оставшихся вершин V \ S обновляем расстояния от источника до соседей v min В каком алгоритме используется похожая идея ?Пример (Википедия) - шаг 1 S = ? , d[] = {0 , ? , ? , ? , ? , ? } ==> v min = 1 ==> S = {1} ==> d [] = {0 , 7 , 9 , ? , ? , 14 } ?Пример - шаг 2 S = {1}, d[] = {0 , 7 , 9 , ? , ? , 14 } ==> v min = 2 ==> S = {1, 2} ==> d[] = {0 , 7 , 9 , 22 , ? , 14 }Пример - шаг 3 S = {1, 2}, d[] = {0 , 7 , 9 , 22 , ? , 14 } ==> v min = 3 ==> S = {1, 2, 3} ==> d [] = {0 , 7 , 9 , 20 , ? , 11 } ?Пример - шаг 4 S = {1, 2}, d[] = {0 , 7 , 9 , 20 , ? , 11 } ==> v min = 6 ==> S = {1, 2, 3, 6} ==> d [] = {0 , 7 , 9 , 20 , 20 , 11 } ?Пример - шаг 5 S = {1, 2, 3, 6 }, d [] = {0 , 7 , 9 , 20 , 20 , 11 } ==> v min = 4 (зависит от того, как мы ищем минимум) ==> S = {1, 2, 3, 4, 6 } ==> d[] = {0 , 7 , 9 , 20 , 20 , 11 } ^Пример - шаг 6 S = {1, 2, 3, 6}, d[] = {0 , 7 , 9 , 20 , 20 , 11 } ==> v min = 5 ==> S = {1, 2, 3, 4, 5, 6 } ==> d[] = {0 , 7 , 9 , 20 , 20 , 11 }Алгоритм Дейкстры // S - множество вершин v , для которых min // расстояние ? (s,v ) от источника s уже найдено // d[v ] - известная оценка сверху для ? (s,v ) Пока S != V Выбираем вершину u ?V \ S c наименьшим d[u] Добавляем вершину u к множеству S Обновляем d[v] для всех соседей u Почему шаг 3 не нарушает корректность алгоритма?Алгоритм Дейкстры Dijkstra (граф G = (V,E), вершина s из V ) S ? {s}; D[s] ? 0; D[v] = w (s, v) для всех v != s; пока S ? V выбрать вершину u ? V \ S, для которого D[u] принимает наименьшее значение; добавить u к S; для каждого соседа v вершины u D[v] = min (D[v], D[u] w(u, v));Алгоритм Дейкстры С // N - число вершин в графе, s - источник void sp (const int G[], int N, int s, int dmin []) {int *blue = calloc (N, sizeof (*blue ) ), i; if (blue == 0) return; for (i = 0; i ? (s, v min ) если есть вершина v ? S и путь p отрицательной длины из v в v min по вершинам V\S - см. рисунок Как вычислять кратчайшие пути в этом случае? s-2 3 2Алгоритм Беллмана-Форда Вычисление кратчайших путей в графе в общем случае Допускает ребра отрицательной длины Находит циклы отрицательной длины Сложность по времени O(|V| ? |E|) Беллман, Форд , Мур (другой) Bellman, Richard (1958). Лестер Форд Ричард БЕЛЛМАНАЛГОРИТМ Беллмана-Форда - схема /* Вычисляем длины кратчайших путей от источника до вершин графа в порядке увеличения числа ребер в пути */ dmin [s] = 0 , dmin [v] = ? для v != s Для i = 1, …, |V|-1 // кратчайшем пути dmin [u] G[u* N v ]) dmin [v ] = dmin [u] G[u* N v ]; for (v = 0; v dmin [u] G[u* N v ] ) return 0; return 1; }Алгоритм Флойда-Уоршелла Вычисление кратчайших расстояний между всеми парами вершин графа Флойд, Уоршелл 1962 Warshall , Stephen (January 1962).