75

Лабораторная работа №6. Структуры и алгоритмы обработки данных. Нахождение кратчайших путей в графе. Алгоритм Дейкстры.

ID: 227095
Дата закачки: 30 Июня 2022
Продавец: DiKey (Напишите, если есть вопросы)
    Посмотреть другие работы этого продавца

Тип работы: Работа Лабораторная
Форматы файлов: Microsoft Office
Сдано в учебном заведении: УГАТУ

Описание:
Лабораторная работа №6. Структуры и алгоритмы обработки данных. Нахождение кратчайших путей в графе. Алгоритм Дейкстры.


Постановка задачи:
Найти кратчайший путь между двумя фиксированными вершинами заданного графа с помощью алгоритма Дейкстры.

Теория
Задача о кратчайшем пути – задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.

Алгоритм нахождения кратчайшего пути между двумя фиксированными вершинами графа
1. Задаем метки всех вершин максимально возможными значениями.
2. Метку начальной вершины задаем нулем.
3. Текущую вершину задаем значением начальной вершиной.
4. Пока не посещены все вершины графа:
4.1.  Посещаем вершину.
4.2.  Если текущая вершина равна конечной вершине, то
4.2.1. Переходим к шагу 5.
4.3.  Перебираем все смежные вершины текущей вершины:
4.3.1. Новую метку задаем суммой метки текущей вершины и расстоянием от смежной вершины к текущей вершине.
4.3.2. Если новая метка меньше метки текущей вершины, то
4.3.2.1. Метке текущей вершины задаем значение новой метки.
4.4.  Текущей вершине задаем значение не посещённой вершины с наименьшим значением метки.
5. Заносим в стек вершин кратчайшего пути конечную вершину.
6. Пока вершина стека не равна начальной вершине:
6.1.  Перебираем все смежные вершины вершины стека:
6.1.1. Если метка смежной вершины равна разности метки вершины стека и расстоянием от смежной вершиной к вершине стека, то
6.1.1.1. Заносим смежную вершину в стек.
6.1.1.2. Переходим к шагу 6.2.
6.2.  Если ни одна смежная вершина не была занесена в стек вершин кратчайшего пути, то
6.2.1. Выводим сообщение «Между вершинами нет пути».
6.2.2. Завершаем алгоритм.
7. Выводим кратчайший путь на экран.
8. Выводим метку конечной вершины (длину пути) на экран.

Входные данные:
• matrix[,] – матрица смежности графа.
• start – номер начальной вершины.
• end – номер конечной вершины.

Выходные данные:
• status – текстовое поле для вывода вершин кратчайшего пути между вершинами и длины пути.
• path – стек для хранения вершин кратчайшего пути между вершинами.
• distance – длина кратчайшего пути между заданными вершинами.


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

Размер файла: 98,9 Кбайт
Фаил: (.docx)

Скачать

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

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

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

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

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

К сожалению, точных предложений нет. Рекомендуем воспользоваться поиском по базе.