Алгоритм Дейкстры

НИС Введение в специальность
1





Алгоритм Дейкстры



Свинцицкая Е.Б., руководитель: Белов А.В.




Аннотация.

    Фаил является отчетом по работе, проделаннои в рамках научно-исследовательского семинара ?Введение в специальность?. Целью данной работы является изучение алгоритма Дейкстра, раз-работка и оттестрирование программы, которая формирует наиболее короткий путь из вершины А в вершину В.

Для цитирования: Свинцицкая Е.Б., "Алгоритм Дейкстры", НИС, 0:0 (2000), 1–0.

Об авторах:

Свинцицкая Екатерина Борисовна, студент,

НИУ ВШЭ МИЭМ им. А.Н.Тихонова

ул. Мясницкая, 20, г.Москва, Россия, 101000

e-mail: ebsvintsitskaya@edu.hse.ru

Белов Александр Владимирович, канд. техн. наук, доцент,

НИУ ВШЭ МИЭМ им. А.Н.Тихонова

ул. Мясницкая, 20, г.Москва, Россия, 101000

e-mail: avbelov@hse.ru


Введение

Главной задачей данного исследовательского проекта является написание програм-мы , которая реализует нахождение кратчайшего пути между двумя вершинами графа с помощью алгоритма Дейкстры, также известного как алгоритм расстанов-ки меток. Программа написана на языке СИ (используется Visual Studio 2017). В первой части рассматривается актуальность и история данной теории, далее по-дробно описывается суть алгоритма Дейкстры. Третья часть содержит описание программы, в четвертой рассказывается о влиянии алгоритма на развитие теории графов. В заключении будет сказано об основных результатах проделанной работы.

1. История появления и актуальность алгоритма Дейкс-тры

Данный алгоритм изобрел нидерландский ученый Эдсгер Вибе Дейкстра в 1959 году. За достижения в области динамического программирования и теории графов был удoстоен премии Тьюринга.

   Раздел дискретной математики, изучающий графы, применяется в решении за-дач, связанных с геоинформационными системами, со строительством дорог, с се-тевыми коммуникациями и другими сферами жизни людей.

   Актуальность теории нахождения минимального расстояния растет , поскольку ранее алгоритм Дейкстры и ему подобные использовались только при вычислении


1

2	НИС Введение в специальность



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

2. Метод Дейкстры и область его применения

Граф G – объект, который состоит из двух конечных множеств:

1. Множество вершин V

2. Множество ребер E

G = (V, E) [1]

   Ребро соединяет две вершины графа, которые называются концевыми вершина-ми этого ребра. Для каждого ребра концевые вершины разные (то есть не суще-ствует петель в графе). Две вершины могут быть соединены лишь одним ребром или не соединены.

   Этот алгоритм применяется только для связных графов, не имеющих ребер от-рицательного веса. Но это замечание не уменьшает популярность алгоритма, так как в большинстве практических случаях данное условие выполняется. [2]

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

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

1. Первый шаг. (Инициализация меток)

Метке исходной вершины присваивается значение 0 и статус посещенной, осталь-ным меткам – статус не посещенной и число, стремящееся к бесконечности (максимально большое). Этим мы показываем, что расстояния от исходной вершины до остальных еще не известны. Пусть A – исходная вершина, A = p (p – номер вершины с посещенной меткой)

2. Второй шаг. (Обновление меток)

Изменяем метки соседей вершины с постоянной меткой: Пусть l(Xi) – значе-ние длины от исходной вершины то текущей i ; m[p][ Xi] – расстояние между текущей вершиной и вершиной с посещенной меткой; Тогда l[i] = minimal(l[i], l[p] + m[p][i]);

3. Третий шаг. (Меняем статус метки на ?посещенный?)

Среди всех вершин, которые имеют не посещенные метки, выбираем ту, у ко-торой она минимальна (точку, расстояние до которой является минимальным) и меняем ее метку на ?посещенную?. Тогда p = Xi .


2

НИС Введение в специальность
3

4. Четвертый шаг.

Четвертый шаг. Пусть B – конечная вершина. Тогда если p = B, следовательно l(B) – длина минимального пути, если нет – переходим ко второму шагу.

   Подробный алгоритм можно изучить в книге "Теория графов. Алгоритмический подход"(Глава 8, пункт 2, 177 - 183 стр.). [3]

3. Реализация решения задачи

При создании программы были использованы некоторые стандартные функции биб-лиoтек < iostream.h>, , , , , а также функ-ции minimal и min1, которые будут определены по мере описания программы.

   После запуска программы на консольное окно выводится сообщение с просьбой ввести количество вершин графа.
   Далее пользователь должен ввести расстояния между вершинами (то есть длину ребер графа). Граф будет определен в виде матрицы инцидентности M=[mij], где в соответствующей ячейке стоит длина ребра. Расстояния от mi до mi +1 и mi +1 до хi одинаковы, а расстояния от mi до mi – не существуют. В том случае, когда ребра между вершинами не существует, пользователь должен ввести нулевое значение.

   После пользователю будет предложено ввести начальную и конечную точки ис-комого пути. Если данный путь не существует (то есть если начальная и конечная точки равны) , будет выведено сообщение на консоль, говорящее пользователю об этом. В обратном случае программа переходит к выполнению алгоритма Дейкстры.
   После того как пользователь введет все необходимые данные, на окно консоли будут выведены результирующие значения наиболее короткого пути и минимальной длины этого пути.

Переменные в коде программы:

1. N – переменная целочисленного типа, определяющая количество вершин гра-фа;

2. x, y – счетчики целочисленного типа, используемые в циклах;

3. m[ ][ ] – массив, в котором хранятся расстояния между вершинами графа;

4. A – целочисленная переменная, обозначающая номер начальной точки пути;

5. B - целочисленная переменная, обозначающая номер конечной точки пути;

6. p – целочисленная переменная, содержащая промежуточные номера вершин (при завершении программы р содержит номера минимальной длины пути и кратчайшего пути);

7. flag[ ] – массив, элемент которого определяется нулем ‘0’, когда путь и длина пути временные, и единицей ‘1’, когда они постоянны;

8. c[ ] – массив, в который записываются временные значения путей;


3

4	НИС Введение в специальность



9. l[ ] – массив, содержащий длины путей (конечное содержание массива при (p = B) – длина кратчайшего пути);

10. path[ ][ ] – массив, содержащий пути (конечное содержание массива при (p = B) – описание кратчайшего пути);

В программе используется функция void main().

   Также в программе определена функция min1, которая возвращает номер эле-мента массива l[i] c наименьшей не посещенной длиной пути.

Функция minimal возвращает наименьшее из двух значений.

   Схема алгоритма Дейкстра и схемы алгоритмов функций main, min1 и minimal ,а также код программы представлены в приложении (пункт 6).


4. Выводы

Программа вывела последовательность точек(от начальной до конечной), которые образуют наиближайший путь. Также определена длина этого пути. Результат ком-пиляции можно найти в приложении.

   Эффективность алгоритма напрямую зависит от структур данных, в которых реализуется очередь приоритета и осуществляется инициализация исходного гра-фа.(В данном случае информация о массиве хранится в матрице инцидентности; очередь с приотритетами реализуется в виде неупорядоченного массива). При ис-пользовании связанных списков смежности для представления графа и очереди с приоритетами, определенной как неубывающая пирамида можно увеличить эфеек-тивность. Если очередь с приоритетами определить в структуре данных "Пирамида Фибоначчи можно получить наивысшую эффективность. [2]


5. Заключение

Алгоритм Дейкстры был мною изучен, написана требуемая программа с использо-ванием этого метода.


Список литературы / References

[1] Кочетков, Ю., МИЭМ, “Комбинаторика и теория графов. “, 2009.

[2] Левитин, Ананий, М.: Вильямс, “Глава 9. Жадные методы: Алгоритм Дейкстры //

Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. “, 2006.

[3] Кристофидес, Н., М.: Мир, “Теория графов. Алгоритмический подход. “, 1977.







4

НИС Введение в специальность
5

6. Приложение


#define _CRT_SECURE_NO_WARNINGS

#include 

#include 

#include 

#include 

#include  

#define word unsigned int

#pragma warning(disable : 4996)

int x, y, N, p, A, B, temp;

int flag[20];

word m[20][20], l[20];

char c[1000], path[1000][20];


int min1(int N)

{

int x, result;

for (x = 0; il[x]) && (!flag[x])) result = x; return result;

}

word minimal(word x, word y)

{

if (x l[p] + m[p][x])

{

itoa(x + 1, c , 10);

strcpy(path[x + 1], path[p + 1]);

strcat(path[x + 1], "-X");

strcat(path[x + 1], c);

}

l[x] = minimal(l[x], l[p] + m[p][x]);

}

}

p = min1(N);

flag[p] = 1;

}while (p != B);

if (l[p] != 10000)

{

printf("Кратчаший путь: %s\n", path[p + 1]);

printf("Длина пути: %u\n", l[p]);

}

else

        printf("Такого пути не существует!"); getchar(); getchar(); getchar();

}





























7

8	НИС Введение в специальность








































































8

НИС Введение в специальность
9








































































9

10	НИС Введение в специальность








































































10

НИС Введение в специальность
11








































































11
.......................