75

Лабораторной работе №4. Алгоритмы и структуры данных. Тема: Графы. ЛЭТИ.

ID: 234325
Дата закачки: 23 Марта 2023
Продавец: DiKey (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Сдано в учебном заведении: Санкт-Петербургский государственный электротехнический университет ЛЭТИ

Описание:
Лабораторной работе №4. Алгоритмы и структуры данных.
Тема: Графы. ЛЭТИ.
Вариант 35

Содержание
Введение ........................................................................................................ 3
Задание ........................................................................................................... 3
Постановка задачи и описание решения ..................................................... 3
Контрольные тесты ...................................................................................... 5
Вывод ............................................................................................................. 8
Список использованных источников........................................................... 9
Текст программы ........................................................................................... 10


Цель работы
Исследование алгоритмов для работы с ориентированными графами
Задание
Отыскание кратчайшего пути между заданной парой вершин в произвольном ориентированном графе с нагруженными ребрами
Математическая формулировка: ориентированный граф G = <V, E>, заданный в форме весового списка ребер edge [v, u], который может содержать циклы с отрицательной длиной, и вершина-источник s. Результатом является вектор расстояний d.
Постановка задачи и описание решения
Для алгоритма Форда-Беллмана более удобно представлять граф в виде списка всех рёбер (вектор структур ребра). Для такого алгоритма матрица смежности получается довольно трудно затратной.
Было решено сделать меню, в котором пользователь выбирает характеристики графа: в первом подменю он выбирает, вводить ли ему вручную или позволить компьютеру сгенерировать граф: если пользователь выбрал первый вариант, то он просто вводит данные графа с клавиатуры, иначе выводится следующее меню, в котором пользователь выбирает, какими должны быть числа в графе: положительными или положительными и отрицательными (это было сделано для того, чтобы удостовериться в правильности алгоритма Беллмана - Форда) – в таком случае генерируются однозначные числа (чтобы красиво выводилась “матрица” и наглядно показать действие алгоритма, ведь для демонстрации алгоритма можно использовать и целые числа)
Важное уточнение: если между вершинами связи нет, то вводится и выводится именно ноль
Формируется список ребер размером n*n, где n – кол-во ребер (однако обрабатываться будут только ребра с ненулевым весом, поэтому одна итерация будет повторяться [кол-во ребер] раз)
Заведём массив расстояний d[n], который после обработки будет содержать ответ на задачу: сначала мы заполняем расстояние вершины старта нулем, остальные бесконечностью. Если после действий алгоритма расстояние все равно бесконечности, значит, что эта вершина недостижима
Также в программе была учтена возможность обнаружения отрицательного цикла – такого, что алгоритм может бесконечно улучшать свою оценку, уходя в минус бесконечность.
Для восстановления пути был инициализирован p[n], в котором соответствующие вершины будут хранить предшественника. Алгоритм, предполагая, что кратчайшее расстояние до одной вершины уже посчитано, пытается улучшить кратчайшее расстояние до другой вершины. Следовательно, в момент улучшения нам надо просто запоминать в массиве “предков”, из какой вершины это улучшение произошло.
Общая сложность алгоритма – О(ne), где n – кол-во вершин, e - кол-во ребер, однако в худшем случае она может достигать O(n^3) (так как тройной цикл)


Комментарии: 2020

Размер файла: 711,5 Кбайт
Фаил: (.rar)
-------------------
Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные!
Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку.
Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот.
-------------------

Скачать

Добавить в корзину

Занесено в корзину

        Коментариев: 0

Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них.
Опять не то? Мы можем помочь сделать!

Некоторые похожие работы:

Лабораторной работе №3. Алгоритмы и структуры данных. Тема: Деревья. ЛЭТИ. 2020
Ещё искать по базе с такими же ключевыми словами.