Цель работы: Разработать программу, которая позволяет осуществлять следующие действия:
1)Задания графа с весами ребер в ручном и автоматическом (случайная генерация) режиме.
2)Алгоритм Дейкстры с использованием приоритетной очереди написанной на следующий структурах данных: стандартный поиск (АВЛ-дерево, красно-черное дерево), d-куча и сложные кучи (Биномиальная куча или Фибоначчиева куча - на выбор). Распределение структур по таблицы.
Особенности реализации:
- Должна быть проверка на односвязаность графа, и удволетворение условиям для Алгоритма Дейкстры.
- Пользователь может задавать начальную точку для всего алгоритма.
- После работы алгоритма пользователь может запросить кратчайший путь и стоимость до любой точки.
- Пользователь может запросить вывод графа на экран, в любом удобном для вас виде.
- Система контроля версий Git. Рекомендуется использовать один из следующих клиентов на выбор студента:
- Фреймворк для написания автоматических тестов Google Test. Не требует установки, идет вместе с проектом-шаблоном.
Структура проекта:
gtest— библиотека Google Test.samples— каталог с пользовательским приложением (Необходимо создать собственный файл кода).test— каталог с проектом с модульными тестами (Необходимо создать собственные файлы с тестами).includesrc- каталоги с основными файлами ЛР (Необходимо создать собственные файлы кода).sln- каталог с файлами с решениями (solution) для Microsoft Visual Studio (Необходимо добавить настроенный проект).README.md— информация о проекте, которую вы сейчас читаете.- Служебные файлы
.gitignore— перечень расширений файлов, игнорируемых Git при добавлении файлов в репозиторий.