Лабораторная №6
.docxМинистерство цифрового развития, связи и массовых коммуникаций Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра «Математическая кибернетика и информационные технологии»
Лабораторная работа №6
«Сетевые алгоритмы. Динамические алгоритмы поиска путей»
по дисциплине «Структуры и алгоритмы обработки данных»
Проверил:
Чайка А.Д.
Москва 2022
Содержание
3.1. Алгоритм Джонсона 3
Цель работы: Реализовать алгоритм поиска кратчайшего расстояния между двумя вершинами ориентированного взвешенного графа в соответствии с вариантом.
2. Задание:
Реализовать алгоритм Джонсона - поиска кратчайшего расстояния между двумя вершинами ориентированного взвешенного графа. Предусмотреть задание графа в виде матрицы смежности, читаемой из файла. Разработать графический интерфейс пользователя с визуализацией графа и отображением кратчайшего расстояния между задаваемыми пользователем вершинами.
3. Ход выполнения лабораторной работы
3.1. Алгоритм Джонсона
Код алгоритма Белламана-Форда представлен на рисунке 1.
Рисунок 1 – Код алгоритма Белламана-Форда
Код алгоритма Дейкстры представлен на рисунке 2.
Рисунок 2 – Код алгоритма Дейкстры
Код алгоритма Джонсона представлен на рисунке 3.
Рисунок 3 – Код алгоритма Джонсона
Код графической составляющей работы представлен на рисунке 4.
Рисунок 4 – Код графической составляющей работы
Наполнение файла, с которого происходит считывание матрицы смежности представлено на рисунке 5.
Рисунок 5 – Матрица смежности
Результат работы всего кода представлен на рисунке 6.
Рисунок 6 – Результат работы кода
4. Вывод
Я реализовала алгоритм Джонсона - поиска кратчайшего расстояния между двумя вершинами ориентированного взвешенного графа. Предусмотрела задание графа в виде матрицы смежности, читаемой из файла. Разработала графический интерфейс пользователя с визуализацией графа и отображением кратчайшего расстояния между задаваемыми пользователем вершинами.