Реализация и сравнительный анализ алгоритма Дейкстры на основе различных приоритетных очередей

В исследовании рассматривается задача нахождения кратчайшего пути на графах. Данная проблема реализуется с помощью алгоритма Дейкстры на основе различных приоритетных очередей. В настоящее время произведено множество исследований и разработок на данную тему, но тем не менее задача не была освещена в полном объеме. В работе приводятся базовые модели объекта исследования в виде матриц расстояний, описывающие задаваемый граф и отображение набора вершин. Также приводится модель визуализации задаваемого графа и оптимальной сети, построенной с помощью алгоритма Дейкстры. Выполнена практическая реализация решения поставленной задачи в виде программы, реализующей работу алгоритма Дейкстры. Программный код будет включать в себя реализацию отобранного набора куч, с целью проведения экспериментальных исследований. Структура и объем работы: Выпускная квалификационная работа состоит из введения, пяти разделов, заключения и списка используемой литературы. Во введении дается общая характеристика работы, обосновывается актуальность исследований, формулируется цель работы, раскрывается научная новизна и практическая значимость полученных результатов. Дается краткий обзор содержания работы по разделам. В первом разделе делается постановка задачи, даётся описание алгоритма Дейкстры, а также рассматриваются различные приоритетные очереди (кучи). Во втором разделе проводится теоретический анализ поставленной задачи. Приводится базовая модель объекта исследования в виде матрицы расстояний, описывающей задаваемый граф, а также выходной бинарной матрицы, которая используется для отображения набора вершин, входящих в пути от выбранной вершины до других вершин графа. Также приводится модель визуализации задаваемого графа и оптимальной сети, построенной с помощью алгоритма Дейкстры. В третьем разделе приводится подробное описание методики решения поставленной задачи. В четвертом разделе приводится практическая реализация решения поставленной задачи в виде программы, реализующей работу алгоритма Дейкстры, а также включающей в себя реализацию отобранного набора куч, с целью проведения экспериментальных исследований. В пятом разделе описываются проведённые эксперименты по оценке времени работы алгоритма Дейкстры с использованием синтезированных приоритетных очередей. Формулируются выводы и выносятся рекомендации по их использованию. В заключении подробно изложены основные результаты проведенных исследований.