Алгоритм Флойда-Уоршелла (графы)

Google Drive Проекта

Краткое описание семестрового проекта. Следует отразить информацию по следующим пунктам:

• Алгоритм Флойда-Уоршелла
• Алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе
• Алгоритм работает за Θ(n3) времени и использует Θ(n2) памяти.
• Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Разработан в 1962 году.

Команда "Биллибой и ПК-боярин"

Фамилия Имя	Вклад (%)	Прозвище
Вагавиев Амирхан	50	Вор ОЗУ плашек
Гарипов Ризван	50	AlgorithmKing

Девиз команды

Если что-то заработало сразу - выключай и ищи ошибку!

Сегодня в маршрутке девчушка лет 4-х спросила маму: «А если всем попросить Бога, он выключит дедлайн?». С мамой плакала половина маршрутки… Боже, выключи дедлайны!!!

Структура проекта

Описание основных частей семестрового проекта.

Пример. Проект состоит из следующих частей:

• src/include - реализация структуры данных (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);
• examples - примеры работы со структурой данных;
• dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования (Prerequisites)

Рекомендуемые требования:

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Видеокарта: GTX 1060 6GB / GTX 1660 Super or Radeon RX 590
4. Рекомендуемый объем оперативной памяти - 12 GB ОЗУ
5. Место на диске: 70 GB
6. Процессор: Intel Core i7-4790 or AMD Ryzen 3 3200G

Минимальные требования:

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Рекомендуемый объем оперативной памяти - 8 GB ОЗУ
4. Место на диске - 300 мб

Сборка и запуск

Инструкция по сборке проекта, генерации тестовых данных, запуска контрольных тестов и примеров работы.

Постарайтесь написать инструкцию так, чтобы незнакомый с проектом человек смог самостоятельно всё запустить.

Пример (Windows)

Сборка проекта

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-floyd-warshall.git

Для ручной сборки проекта в терминале введите:

# переход в папку с проектом
cd C:\Users\username\asd-projects\semester-work-floyd-warshall

# создание папки для файлов сборки (чтобы не засорять папку с проектом) 
mkdir -p build && cd build 

# сборка проекта
cmake .. -DCMAKE_BUILD_TYPE=RelWithDebInfo && cmake --config RelWithDebInfo --build . 

Генерация тестовых данных

Тестовые данные хранятся в формате txt в dataset/data/

Для генерации тестовых данных необходимо запустить метод main в файле create_txt_dataset.cpp, находящемся в папке dataset. Или же создать иной метод, для этого можно воспользоваться методом из create_txt_dataset.cpp

Тестовые данные это файлы в формате txt, содержащие в матрицу размерами Sqrt(n)xSqrt(n), где где n одно из значений массива {100, 625, 1024, 2500, 5041, 10000, 24964, 50176, 75076, 99856, 250000, 499849, 749956, 1000000}.

Все тестовые данные необходимые для контрольного тестирования находятся в dataset/data

Контрольные тесты (benchmarks)

Для запуска контрольных тестов можно предварительно сгенерировать, или скачать готовый набор тестовых данных. Также можно создать иной метод для запуска контрольных тестов, используя методы из benchmarks.cpp, который во вход принимают размер тестовых данных(100, 625, 1024 и т.д) и номер набора(число от 1 до 10).

После получения необходимых тестовых данных необходимо запустить benchmarks.cpp, который напишет в консоль время необходимое для выполнения алгоритма для матриц.

Список контрольных тестов

Название	Описание	Метрики
time_for_algorithm	выполнения алгоритма	время
time_for_getShortestPath	получение кратчайшего пути между двумя вершинами для матрицы, над которой уже выполнили алгоритм Флойда-Уоршолла	время

Запуск контрольных тестов

Для запуска контрольных тестов можно запустить main в benchmark/benchmarks.cpp

Или же написать свою программу для запуска контрольных тестов, воспользовавшись методами в benchmarks.cpp, которые на вход принимают два int значения:

первое - кол-во входных данных(100, 625, 1024...);

второе - номер тестовых данных с таким кол-вом входящих данных.

Источники

Алгоритм Флойда — Викиконспекты

Алгоритм Флойда - Википедия