Алгоритм Дейкстры

В данном семестровом проекте реализуется алгоритм Дейкстры:

Алгоритм голландского ученого Эдсгера Дейкстры находит все кратчайшие пути из одной изначально заданной вершины графа до всех остальных. С его помощью, при наличии всей необходимой информации, можно, например, узнать какую последовательность дорог лучше использовать, чтобы добраться из одного города до каждого из многих других, или в какие страны выгодней экспортировать нефть и тому подобное. Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом, т. е. если, например, некоторая система предусматривает убыточные для Вашей фирмы маршруты, то для работы с ней следует воспользоваться отличным от алгоритма Дейкстры методом.

Пример работы алгоритма:

Применение алгоритма:

Алгоритм Дейкстры имеет много применений. Например, в дорожных и телефонных сетях, IP маршрутизации, A* алгоритме (алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной). Алгоритм так же широко применяется в программировании и технологиях, например, его используют для протоколов маршрутизации OSPF (протокол динамической маршрутизации, основанный на технологии отслеживания состояния канала) и IS-IS (протокол внутренних шлюзов (IGP), стандартизированный ISO и использующийся в основном в крупных сетях провайдеров услуг).

Сложность алгоритма:

T=O(mlog(n)), где m - количество ребер, n - количество вершин, в худшем случае O(n²log(n)), т.к. в полном графе количество ребер равно квадрату количества вершин. Сложность работы алгоритма оценена сверху, практически время работы будет меньше O(mlog(n)).

Команда "IWS"

Заполните таблицу с указанием вклада каждого из участников в проект.

Фамилия Имя	Вклад (%)	Прозвище
Михайлов Алексей	40	Альфонсо Мудрый Кастильский
Курочкин Даниил	30	Фридрих I Барбаросса
Зарипова Эрика	30	Ингеборга Датская

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

Allons enfants de la Patrie, le jour de gloire est arrivé !

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

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

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

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

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

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Интерпретатор Python (версия 3.7.x и выше).
4. Рекомендуемый объем оперативной памяти - не менее 16 ГБ.
5. Свободное дисковое пространство объемом ~ 3 ГБ (набор данных для контрольных тестов).

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

Пример (Windows)

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

Склонируйте проект к себе на устройство через Git for Windows:

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-dijkstra-11-006.git

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

Для генерации тестовых наборов данных использовался язык программирования Python. Был создан класс “Creator”, который генерировал матрицу смежности для определенного количества вершин с элементами в диапазоне от 0 до 1000 и записывал ее в виде массива из массивов в csv файл. Всего для теста использовалось 100 файлов с наборами данных от 5 вершин до 2500 вершин. Ссылка на папку с тестовыми наборами данных: https://drive.google.com/drive/folders/1F5_vqvXM8XoLKlCWH-Jz_fjgm_gMxObZ

Генерация тестового набора данных в формате comma-seperated values (CSV):

# переход в папку генерации набора данных
cd dataset

# запуск Python-скрипта
python generate_dataset_csv.py 

Пример данных в файле Random_1000x1000.csv

0,234,123 ... 123
123,0,234 ... 536
...
834,28,53 ... 0

**Для удобства запуска контрольных тестов данные организованы в директориях: **

dataset/data/database
  include/
    01/
      Random_5x5.csv
      ...
      Random_2500x2500.csv
    02/ ...
    03/ ...
    ...
    10/ ...

По названию директории /dataset/data/database можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов Random_5x5.csv. Random_2500x2500.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

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

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

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

Название	Описание	Метрики
benchmark.cpp	измерение времени работы алгоритма на тестовых данных	время

Запуск

Запуск производится без дополнительных параметров. Нужно запустить файл benchmarks.cpp и по завершении данные метрик записываются в файл ./data/database/main_statistic.csv.

Пример запуска в IDE

Источники

Список использованных при реализации алгоритма источников.

1. Видео Алгоритм Дейкстры за O(M log N)
2. Статья Википедии
3. https://e-maxx.ru/algo/dijkstra
4. Жадные алгоритмы. Алгоритм Дейкстры
5. Applications of Dijkstra’s shortest path algorithm
6. https://habr.com/ru/post/111361/
7. https://stackoverflow.com/how-can-i-use-binary-heap-in-the-dijkstra-algorithm и прочее