ФЛОЙД АЛГОРИТМ. V во взвешенном Graph, где вес его ребер w(u, v) может быть отрицательным, найти веса
 Скачать 0.78 Mb.
|
|
Кратчайшие пути для всех пар - алгоритм Флойда Уоршелла Дан набор вершин V во взвешенном Graph , где вес его ребер w(u, v) может быть отрицательным, найти веса кратчайших путей d(s, v) из каждого источника s для всех вершин v присутствует на Graphе Если граф содержит отрицательный вес цикл , доложите об этом. Например, рассмотрим следующий Graph : The adjacency matrix containing the shortest distance is: 0 -1 -2 0 4 0 2 4 5 1 0 2 3 -1 1 0 The shortest path from: • vertex 0 to vertex 1 is [0 —> 2 —> 3 —> 1] • vertex 0 to vertex 2 is [0 —> 2] • vertex 0 to vertex 3 is [0 —> 2 —> 3] • vertex 1 to vertex 0 is [1 —> 0] • vertex 1 to vertex 2 is [1 —> 0 —> 2] • vertex 1 to vertex 3 is [1 —> 0 —> 2 —> 3] • vertex 2 to vertex 0 is [2 —> 3 —> 1 —> 0] • vertex 2 to vertex 1 is [2 —> 3 —> 1] • vertex 2 to vertex 3 is [2 —> 3] • vertex 3 to vertex 0 is [3 —> 1 —> 0] • vertex 3 to vertex 1 is [3 —> 1] • vertex 3 to vertex 2 is [3 —> 1 —> 0 —> 2] мы уже рассмотрели кратчайшие пути из одного источника в отдельных постах. Мы видели, что: Для graphs с неотрицательными весами ребер Алгоритм Дейкстры вбегает O(E + V × log(V)) Для graphs, содержащих отрицательные веса ребер, Bellman– Ford вбегает O(V × E). Для DAG, один проход Беллмана-Форда (так называемый этап релаксации) достаточно, что займет O(V + E) время. Здесь, V это общее количество вершин и E - общее количество ребер в Graph Кратчайшие пути для всех пар которые возвращают кратчайшие пути между каждой парой вершин в Graph , содержащем отрицательные веса ребер. Алгоритм Флойда-Уоршалла — это алгоритм поиска кратчайших путей во взвешенном Graph с положительными или отрицательными весами ребер (но без отрицательных циклов). Это делается путем сравнения всех возможных путей через граф между каждой парой вершин, а также с помощью O(V 3 ) сравнения на Graphе. Ниже приведен псевдокод Флойда Уоршалла, Реализация берет graph, представленный матрицей смежности, и заполняет dist[] с информацией о кратчайшем пути (наименьшей стоимости): let dist be V × V matrix of minimum distances initialized to INFINITY for each vertex v dist[v][v] = 0 for each edge (u, v) dist[u][v] = weight(u, v) for k from 0 to |V| – 1 for i from 0 to |V| – 1 for j from 0 to |V| – 1 if (dist[i][k] + dist[k][j]) is less than dist[i][j] then dist[i][j] = dist[i][k] + dist[k][j] Над псевдокодом поднимается вершина k между 0 и V-1, по одному, и включить эту вершину в качестве промежуточной вершины в кратчайший путь между каждой парой ребер i—>j на Graphе. Он обновляет матрицу стоимости всякий раз, когда более прямой путь от i к j через вершину k найден. Так как для заданного k, мы уже рассмотрели вершины 0…k-1 в качестве промежуточных вершин этот подход работает. Рассмотрим приведенный выше Graph, Перед первой итерацией внешнего цикла для k , единственные известные пути соответствуют одиночным ребрам в Graph. В k = 0, пути, проходящие через вершину 0, найдены: в частности, путь [1, 0, 2] найден, заменив путь [1, 2] который имеет меньше ребер, но является дорогостоящим. В k = 1, пути, проходящие через вершины {0, 1} найдены. На следующем рисунке показано, как путь [3, 1, 0, 2] собирается из двух известных путей [3, 1] а также [1, 0, 2] встречались в предыдущих итерациях, с 1 на пересечении. Путь [3, 1, 2] не считается, потому что [1, 0, 2] это кратчайший путь, встречающийся до сих пор от 1 к 2. В k = 2, пути, проходящие через вершины {0, 1, 2} найдены. Наконец, в k = 3, все кратчайшие пути найдены. Алгоритм Флойда-Уоршалла прост в программировании и традиционно эффективен. Его также можно использовать для поиска Транзитивное замыкание Graph а также обнаружить циклы с отрицательным весом на Graphе Чтобы обнаружить отрицательные циклы с помощью алгоритма Флойда- Уоршалла, проверьте диагональ матрицы расстояний на наличие отрицательного числа, поскольку оно указывает, что graph содержит по крайней мере один отрицательный цикл. Как это работает? Алгоритм Флойда-Уоршалла итеративно пересматривает длины путей между всеми парами вершин. (i, j), в том числе где i = j. Первоначально размер пути (i, i) равен нулю. Путь [i, k…i] может улучшить это только в том случае, если он имеет длину меньше нуля, т. е. обозначает отрицательный цикл. Таким образом, после алгоритма (i, i) будет отрицательным, если существует путь отрицательной длины из i вернуться к i. Алгоритм может быть реализован следующим образом на C++, Java и Python: C++ Java Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include #include #include // Рекурсивная функция для печати пути заданной вершины `u` из исходной вершины `v` void printPath(vector { if (path[v][u] == v) { return; } printPath(path, v, path[v][u]); cout << path[v][u] << ", "; } // Функция для вывода кратчайшей стоимости с информацией о пути между // все пары вершин void printSolution(vector { int n = cost.size(); for (int v = 0; v < n; v++) { 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 for (int u = 0; u < n; u++) { if (u != v && path[v][u] != -1) { cout << "The shortest path from " << v << " —> " << u << " is [" << v << ", "; printPath(path, v, u); cout << u << "]" << endl; } } } } // Функция для запуска алгоритма Флойда-Уоршалла void floydWarshall(vector { // общее количество вершин в `adjMatrix` int n = adjMatrix.size(); // базовый вариант if (n == 0) { return; } // cost[] и path[] сохраняют кратчайший путь // информация (кратчайшая стоимость/кратчайший маршрут) vector // инициализируем cost[] и path[] for (int v = 0; v < n; v++) { 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 for (int u = 0; u < n; u++) { // изначально стоимость будет равна весу ребра cost[v][u] = adjMatrix[v][u]; if (v == u) { path[v][u] = 0; } else if (cost[v][u] != INT_MAX) { path[v][u] = v; } else { path[v][u] = -1; } } } // запускаем Флойда-Уоршалла for (int k = 0; k < n; k++) { for (int v = 0; v < n; v++) { for (int u = 0; u < n; u++) { // Если вершина `k` находится на кратчайшем пути из `v` в `u`, // затем обновить значение cost[v][u] и path[v][u] if (cost[v][k] != INT_MAX && cost[k][u] != INT_MAX && cost[v][k] + cost[k][u] < cost[v][u]) { cost[v][u] = cost[v][k] + cost[k][u]; path[v][u] = path[k][u]; 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 } } // если диагональные элементы становятся отрицательными, // graph содержит цикл отрицательного веса if (cost[v][v] < 0) { cout << "Negative-weight cycle found!!"; return; } } } // Выводим кратчайший путь между всеми парами вершин printSolution(cost, path); } int main() { // определить бесконечность int I = INT_MAX; // заданное представление смежности матрицы vector { { 0, I, -2, I }, { 4, 0, 3, I }, { I, I, 0, 2 }, { I, -1, I, 0 } }; // Запуск алгоритма Флойда-Уоршалла 120 121 122 123 floydWarshall(adjMatrix); return 0; } Скачать Выполнить код Output: The shortest path from 0 —> 1 is [0, 2, 3, 1] The shortest path from 0 —> 2 is [0, 2] The shortest path from 0 —> 3 is [0, 2, 3] The shortest path from 1 —> 0 is [1, 0] The shortest path from 1 —> 2 is [1, 0, 2] The shortest path from 1 —> 3 is [1, 0, 2, 3] The shortest path from 2 —> 0 is [2, 3, 1, 0] The shortest path from 2 —> 1 is [2, 3, 1] The shortest path from 2 —> 3 is [2, 3] The shortest path from 3 —> 0 is [3, 1, 0] The shortest path from 3 —> 1 is [3, 1] The shortest path from 3 —> 2 is [3, 1, 0, 2] Временная сложность алгоритма Флойда-Уоршалла равна O(V 3 ), куда V это общее количество вершин в Graph. |