Разработка алгоритма кратчайшего пути

2. Строим множество вершин  инцидентных выделенным и определяем  для них новые цены. Новая цена  вершины это минимальная цена  пути от множества выделенных  вершин до данной вершины. Строится  новая цена так:

a. Для невыделенной вершины  во множестве выделенных определяется  подмножество вершин инцидентных  данной.

b. Для каждой вершины  выделенной подмножества определяется  цена пути до данной.

c. Определяется минимальная  цена. Эта цена и становится  ценой вершины.

Алгоритм работает с двумя  типами цен: ценой ребра и ценой  вершины. Цены ребер являются постоянной величиной. Цены же вершин постоянно  пересчитываются. Смысл этих цен различен. Цена ребра это цена перехода из вершины в вершину соединённую этим ребром. А цена вершины это цена минимального пути. Ещё одно важное замечание касается пересчета предварительных цен. Фактически, есть смысл пересчитывать предварительные цены только для тех вершин которые связаны с вершиной добавленной во множество выделенных на последнем шаге, так как для других вершин нет причин изменения предварительной цены.

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

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

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

 

 

 

 

 

 

2. РАЗРАБОТКА И АПРОБАЦИЯ АЛГОРИТМА

 

2.1 Составление  блок-схемы алгоритма

 

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

На рисунке 2.1 приведена блок-схема алгоритма нахождения кратчайшего пути между заданными вершинами.

 

 

 

 

 

Рисунок 2.1 -  блок-схема алгоритма нахождения кратчайшего пути между заданными вершинами

Алгоритм использует три  массива из N (= числу вершин графа) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие расстояния от и до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С [k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D [i,k] задает длины дуге D [i,k]; если такой дуги нет, то D [i,k] присваивается большое число Б, равное «бесконечности».

Описание алгоритма:

1. (инициализация). В цикле  от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести  i-ю строку матрицы D в массив B, A [i]: =1; C [i]: =0 (i - номер стартовой  вершины)

2. (общий шаг). Hайти минимум  среди неотмеченных (т.е. тех k, для которых A [k] =0); пусть минимум  достигается на индексе j, т.е. B [j] <=B [k] Затем выполняются следующие  операции: A [j]: =1; если B [k] >B [j] +D [j,k], то B [k]: =B [j] +D [j,k]; C [k]: = j. Условие означает, что путь Vi-Vk длиннее, чем путь Vi-Vj-Vk. Если все A [k] отмечены, то длина пути от Vi до Vk равна B [k]. Теперь надо перечислить вершины, входящие в кратчайший путь.

3. (выдача ответа). (Путь  от Vi до Vk выдается в обратном  порядке следующей процедурой:)

3.1. z: =C [k];

3.2. Выдать z;

3.3. z: =C [z]. Если z = 0, то конец, иначе перейти к 3.2.

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

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

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

 

 

2. Апробации работы алгоритма

 

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

Условие задачи: Найти кратчайший путь от вершины 1 к вершине 6 следующего графа , который изображен на рисунке 2.2.

Решение: Каждой вершине  графа сопоставим метку - минимальное  известное расстояние от этой вершины  до вершины 1. Метка самой вершины 1 полагается равной 0, метки остальных  вершин - бесконечности. Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины  графа помечаются как непосещённые.

 

Рисунок 2.2 - Исходный граф

Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки.

На каждом шаге из ещё  не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним  пунктом.

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

Шаг 1 (см. рисунок 2.3). Минимальную метку имеет вершина 1. Её соседями являются вершины 2 и 3.

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

Рисунок 2.3 - Граф с просмотренной первой вершиной

Аналогичным образом получаем новую метку 3-й вершины, равную 4.

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

Шаг 2 (см. рисунок 2.4). Ближайшей из непосещенных вершин является вершина 2 с меткой 3. Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину.

Рисунок 2.4 - Граф с посещенными вершинами: 1 и 2

 

Соседями вершины 2 являются вершины 1 и 4. Вершина 1 уже посещена. Рассмотрим вершину 4. Если идти в неё  через 2, то длина такого пути будет  равна 3 + 5 = 8. Присваиваем ей метку 8.

Помечаем вершину 2 как  посещенную.

Шаг 3. (см. рисунок 2.5.) Рассмотрим вершину 3. Ее соседями являются вершины 1, 4 и 5.

Вершина 1 уже посещена.

Следующий сосед вершины 3 - вершина 4, так имеет минимальную  метку из непосещённых вершин. Если идти в неё через 3, то длина такого пути будет равна 4 + 2 = 6. Это значение меньше текущей метки, поэтому меняем метку четвертой вершины на 6.

Рисунок 2.5 - Граф с посещенными вершинами 1, 2, и 3

 

Рассмотрим вершину 5. Если идти в неё через 3, то длина такого пути будет равна 4 + 3 = 7. Присваиваем  ей метку 7. Пометим стрелкой путь от вершины 1 к вершине 4 наименьшей длины.

Помечаем вершину 3 как  посещенную.

Шаг 4 (см. рисунок 2.6). Рассмотрим вершину 4. Ее соседями являются вершины 2, 3, 5 и 6.

Вершины 2 и 3 уже посещены.

Рассмотрим вершину 5. Если идти в неё через 4, то длина такого пути будет равна 6 + 6 = 12. Но это значение больше текущей метки, поэтому метку  вершины 5 не меняем. Пометим стрелкой путь от вершины 1 к вершине 5 наименьшей длины.

Рассмотрим вершину 6. Если идти в неё через 4, то длина такого пути будет равна 6 + 8 = 14. Присваиваем  ей метку 14.

Помечаем вершину 4 как  посещенную.

Рисунок 2.6 - Граф с посещенными вершинами 1, 2, 3 и 4

 

Шаг 5 (см. рисунок 2.7). Рассмотрим вершину 5. Ее соседями являются вершины 3, 4 и 6.

Рисунок 2.7 - Граф с посещенными вершинами 1, 2, 3, 4 и 5

 

Вершины 3 и 4 уже посещены.

Рассмотрим вершину 6. Если идти в неё через 5, то длина такого пути будет равна 7 + 9 = 16 < 14, значит, метку вершины 6 не меняем. Пометим  стрелкой путь от вершины 1 к вершине 6 наименьшей длины.

Помечаем вершину 5 как  посещенную.

У целевой вершины 6 не осталось непосещенных соседей. Алгоритм закончен.

Ответ: Кратчайший путь от вершины 1 к вершине 6: 1-3-4-6, его длина 14.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

Для его разработки мы не только создали алгоритм, но и ознакомили Вас и сами научились работать в среде быстрой разработке приложений – Delphi. Показали, что выбранная нами тема не случайна, и находит применение и является актуальной на сегодняшний день в различных сферах деятельности.

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

Анализ применения теории графов для решения задач показал, что графы нашли применение практически  во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике, и теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических  цепей и других систем сетевой  структуры;

Описание разработанного алгоритма позволило подробно изучить  процедуру нахождения кратчайшего  пути между двумя точками;

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

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

 

1. Алгоритмы: построение и анализ [Текст]/ К.Кормен, Ч. Лейзерсон, Р. Ривест . - М.: НЦНМО, 2009. - 960 с.
2. Зиглер К. Методы проектирования программных систем [Текст]  - М.: Мир, 2010. - 380с.
3. Построение и анализ вычислительных алгоритмов [Текст] / А. Ахо, Дж. Хопкрофт, Дж. Ульман.  - М.: Мир, 2010. - 436 с.
4. С. Лавров. Программирование. Математические основы, средства, теория [Текст]  - СПб.: БХВ-Петербург, 2009. - 320 с.
5. Структурное программирование [Текст]  / У. Дал, Э. Дейкстра, К. Хоор. - М.: Мир, 2010. - 248 с.