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

 

 

 

 

 

 

 

 

 

 

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

 

«Нахождение кратчайшего маршрута в графе с помощью алгоритма Дейкстры»

 

Выполнил: Дубихин В.С.

 

Группа: П-452

Москва 2009 г. 
Оглавление

 

 

Введение

 

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

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

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

Существуют три наиболее эффективных  алгоритма нахождения кратчайшего  пути:

• алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
• алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
• алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).

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

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

Количество объектов усложнялись, увеличивались, и  натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства,  формулы  и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.

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

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

Большие программы из-за своей сложности  нередко содержат ошибки, которые  могут стать причиной материального  ущерба, а иногда и угрожать жизни  людей (например, при управлении авиа-полётами). В результате борьбы с проблемой сложности программного кода были выработаны три новые концепции программирования:

а) объектно-ориентированное программирование (ООП);

б) унифицированный язык моделирования (UML);

в) специализированные средства разработки программного обеспечения;

Из всех объектно-ориентированных  языков Delphi является наиболее удобным и простым. И именно с его помощью в данном курсовом проекте реализуется алгоритм Дейкстры.

 

Задание

 

Определить кратчайший маршрут  из пункта 1 в пункт 10. Задачу решить с помощью алгоритма Дейкстры. Исходные данные приведены в таблице 1.

 

	1	2	3	4	5	6	7	8	9	10
1
2	2
3	5
4	1
5		10	5
6		12	10	15
7			7	13
8					7	3	7
9					5	4	1
10								1	4

 

 

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

 

Алгори́тм Де́йкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием кратчайший путь — первый (Shortest Path First).

 

Неформальное определение

 

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

 

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого  известна стоимость. Найти маршрут  минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

 

Формальное определение

 

Дан простой  взвешенный граф G(V,E) без петель и  дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

 

Неформальное объяснение

 

Каждой  вершине из V сопоставим метку —  минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

 

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

 

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

 

Пример

 

Рассмотрим  выполнение алгоритма на примере  графа, показанного на рисунке. Пусть  требуется найти расстояния от 1-й  вершины до всех остальных.

Кружками  обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма  Дейкстры для нашего примера. Минимальную  метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина  пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем  с двумя другими соседями 1-й  вершины — 3-й и 6-й.

 

Все соседи вершины 1 проверены. Текущее  минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно  так, впервые доказал Дейкстра). Вычеркнем  её из графа, чтобы отметить, что  эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки  соседей выбранной вершины, пытаясь  пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина  такого пути будет = 7 + 10 = 17. Но текущая  метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина  такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<, устанавливаем  метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки»  получим такие результаты:

Дальнейшие шаги. Повторяем шаг  алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

 

 

 

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда  вычеркнуты все вершины. Результат  его работы виден на последнем  рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

Обозначения

V — множество вершин графа

E — множество ребер графа

w[ij] — вес (длина) ребра ij

a — вершина, расстояния от  которой ищутся

U — множество посещенных вершин

d[u] — по окончании работы  алгоритма равно длине кратчайшего пути из a до вершины u

p[u] — по окончании работы  алгоритма содержит кратчайший  путь из a в u

 

 

Описание

 

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.

 

В начале алгоритма расстояние для  начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным  числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется  нулями. Затем запускается основной цикл.

 

На каждом шаге цикла мы ищем вершину  с минимальным расстоянием и  флагом равным нулю. Затем мы устанавливаем  в ней флаг в 1 и проверяем все  соседние с ней вершины. Если в  ней расстояние больше, чем сумма  расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен, если и только если граф G несвязан.

 

Сложность алгоритма

 

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.

В простейшем случае, когда для  поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.

Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из  станет logn, при том, что время модификации d[i] возрастет до logn. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(nlogn + mlogn)

Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(logn), а уменьшение значения в среднем за O(1), то время работы алгоритма составит O(nlogn + m) 
Создание приложения

На основе контрольного примера  было создано приложение для его  решения.

Необходимо найти кратчайший путь из 1 вершины в 5.

Решение найдено верно.

 

Алгоритмы решения задачи

 

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

 

fillchar(b,sizeof(b),0);

  fillchar(d,sizeof(d), 10000);

  d[q] := 0;//расстояние до начальной  вершины

  for i:=1 to n do

  begin

    m := 1000;

    for j := 1 to n do

    if ( (d[j] <= m) and (not b[j]) ) then

    begin

      m:=d[j];

      v:=j;

    end;

    b[v] := true;

    for j := 1 to n do

     if ((a[v,j] <> 0) and (not b[j]) and (d[v]+a[v,j]<d[j])) then

       d[j] := d[v] + a[v,j];

  end;

 

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

 

while f<>q do

  for i:=1 to n do

  if a[i, f] <> 0 then

  if d[f] = d[i]+a[i, f] then

    begin

      path:=inttostr(i)+ ' >> ' + path;

      f:=i;

      break;

    end;

 

Решение поставленной задачи

 

Инструкция пользователя

После запуска приложения на экране отображается такой интерфейс:

 

 

1. Матрица смежности графа, где по горизонтальная вершина соединяется с вертикальной вершиной ребром длинны указанной в ячейке их пересечении.
2. Окно в котором будет указаны кратчайшие расстояния от начальной точки до всех других.
3. Этим ползунком регулируется радиус круга при круговом графическом построении графа.
4. Количество вершин графа.
5. Сохранение матрицы смежности в файл.
6. Загрузка матрицы смежности из файла.
7. Генерирование случайных координат для вершин графа и его отображение.
8. Генерирование круговых координат для вершин графа и его отображение.
9. При нажатии на кнопку path будет просчитан путь между двумя указанными точками.
10. Место для отображения графа.
11. Тут отображается путь между двумя вершинами графа.