Алгоритм Флойда ★
Степа 02 фев 2020
Разбор задачи на сайте acmp.ru №135
Алгоритм Флойда - алгоритм для нахождения кратчайших расстояний между всеми парами вершин графа. Также применяется для построения матрицы достижимости графа и построения множества истоков и множества стоков.
Рассмотрим задачу:
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные:
В первой строке записано единственное число N - количество вершин графа.
В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j).
Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.
Выходные данные:
Выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин.
j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.
Решение:
Введем N и матрицу смежности:
Реализуем алгоритм Флойда, т. е. найдем кратчайшие расстояния между всеми парами вершин графа.
Три вложенных цикла содержат операцию, исполняемую за константное время O(n3), то есть алгоритм имеет кубическую сложность.
Выведем результат, т. е. массив d:
Полный код:
Сдать задачу: https://acmp.ru/inde...ask&id_task=135
Алгоритм Флойда - алгоритм для нахождения кратчайших расстояний между всеми парами вершин графа. Также применяется для построения матрицы достижимости графа и построения множества истоков и множества стоков.
Рассмотрим задачу:
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные:
В первой строке записано единственное число N - количество вершин графа.
В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j).
Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.
Выходные данные:
Выведите N строк по N чисел - матрицу кратчайших расстояний между парами вершин.
j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.
Решение:
Введем N и матрицу смежности:
int n; cin >> n; int d[n][n]; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> d[i][j];
Реализуем алгоритм Флойда, т. е. найдем кратчайшие расстояния между всеми парами вершин графа.
for (int l = 0; l < n; ++l) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][l] + d[l][j]);
Три вложенных цикла содержат операцию, исполняемую за константное время O(n3), то есть алгоритм имеет кубическую сложность.
Выведем результат, т. е. массив d:
for (int i = 0; i < n; ++i){ for (int j = 0; j < n; ++j) cout << d[i][j] << " "; cout << endl; }
Полный код:
#include <bits/stdc++.h> using namespace std; int32_t main() { int n; cin >> n; int d[n][n]; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> d[i][j]; for (int l = 0; l < n; ++l) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][l] + d[l][j]); for (int i = 0; i < n; ++i){ for (int j = 0; j < n; ++j) cout << d[i][j] << " "; cout << endl; } return 0; }
Сдать задачу: https://acmp.ru/inde...ask&id_task=135