Перейти к содержимому


* * * * * 2 Голосов

Алгоритм Флойда ★

графы кратчайший путь

В этой теме нет ответов

#1 Степа

    Новичок

  • Пользователи
  • Pip
  • 1 сообщений
  • ГородВитебск

Отправлено 02 февраля 2020 - 15:48

Разбор задачи на сайте acmp.ru №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





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных