Алгоритм Дейкстры для решения задачи поиска кратчайшего пути в графе

Министерство образования и науки РФ

Казанский национальный исследовательский технический

университет им. А. Н. Туполева

Кафедра «Системы автоматизированного проектирования»

КУРСОВАЯ РАБОТА

по дисциплине «Методы программирования систем автоматизированного проектирования»

Тема: «Алгоритм Дейкстры для решения задачи поиска кратчайшего пути в графе»

                             Выполнил:

студент гр. 4213

И.С. Довбыш

       Проверил:

  ст. преп. И.В. Суздальцев

   Оценка:    _____________

  Подпись: _____________

Дата: «____» ______ ______20___ г.

Казань 2018

                                                       СОДЕРЖАНИЕ

Введение        3

1. Постановка задачи.        3

   1.1. Содержательная постановка задачи        4

   1.2. Математическая постановка задачи        5

2. Разработка последовательного алгоритма Дейкстры для решения задачи поиска кратчайшего пути в графе        5

   2.1. Описание последовательного алгоритма Дейкстры для решения задачи поиска кратчайшего пути в графе        5

   2.2. Решение задачи на контрольном примере        7

3. Программная реализация последовательного алгоритма Дейкстры для решения задачи поиска кратчайшего пути в графе        12

4. Исследование эффективности разработанного последовательного алгоритма Дейкстры для решения задачи поиска кратчайшего пути в графе        14

Заключение        16

Список источников        17

Приложение А        18

Приложение Б        21

1. ПОСТАНОВКА ЗАДАЧИ

1. Содержательная постановка задачи

Исходные данные задачи

Неориентированный взвешенный граф G(V, U), вес рёбер которого неотрицателен.

Результирующие данные задачи

Кратчайший путь от заданной начальной вершины s ∈ V до заданной конечной вершины t ∈ V.

Содержательная постановка задачи

Пусть дан взвешенный неориентированный граф G(V, U), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[cij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s ∈ V до заданной конечной вершины t ∈ V, при условии, что такой путь существует, т.е. при условии t ∈ R(s). Здесь R(s) - множество, достижимое из вершины s. Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями.

Практические примеры задачи нахождения кратчайшего пути

1. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Москвы до каждого города области (если двигаться можно только по дорогам).

1. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

1. Найти кратчайший путь между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

1. Математическая постановка задачи

Обозначения элементов математической модели представлено в таблице 1:

Таблица 1. Обозначение элементов математической модели

Целевая функция

Целевая функция, подлежащая оптимизации – минимизация общей длины пути.

[pic 1]

Ограничения задачи

Ограничением задачи является поиск кратчайшего пути. Если такого пути существовать не может или нет возможности связать первую и последнюю вершину, то решить задачу невозможно.