- Публикации Степа
Публикации Степа
2 публикаций создано Степа (учитываются публикации только с 14-мая 23)
По типу контента
По пользователю
Сортировать
Порядок
#1083 Алгоритм Флойда ★
Отправлено от Степа в 02 февраля 2020 - 15:48 in Графы
Разбор задачи на сайте 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
- → Публикации Степа