0
Алгоритм Флойда - алгоритм для нахождения кратчайших расстояний между всеми парами вершин графа. Также применяется для построения матрицы достижимости графа и построения множества истоков и множества стоков.
Рассмотрим задачу:
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
Входные данные:
В первой строке записано единственное число 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
