Поиск кратчайшего пути в графе
Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 23.09.2013 |
| Размер файла | 929,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
ОГЛАВЛЕНИЕ
- ЗАДАНИЕ
- Постановка задачи и сфера ее применения
- Общие сведения о графах
- Алгоритм Дейкстры
- Алгоритм, реализованный в программе
- ОСОБЕННОСТИ ПРОГРАММНОЙ РЕАЛИЗАЦИИ
- ПРИМЕР ИСПОЛЬЗОВАНИЯ ПРОГРАММНОЙ РЕАЛИЗАЦИИ
- ЗАКЛЮЧЕНИЕ
- ЛИТЕРАТУРА
ЗАДАНИЕ
1. Разработать алгоритм реализации на ЭВМ процесса поиска кратчайшего пути в графе (методом Дейкстры). Предусмотреть проверку допустимости весов дуг графа.
2. Написать и отладить программу, реализующую разработанный алгоритм.
3. Проверить работоспособность программы на тестовых примерах.
Постановка задачи и сфера ее применения
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
· алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
· алгоритм Флойда;
· алгоритм Йена.
Основной задачей данной курсовой работы является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.
Программа должна работать так, чтобы пользователь вводил количество вершин и длины рёбер графа, а после обработки этих данных на экран выводился кратчайший путь между двумя заданными вершинами и его длина. Необходимо предусмотреть различные исходы поиска, чтобы программа не выдавала ошибок и работала правильно. Данная программа может использоваться в дискретной математике для исследования графов или в качестве наглядного пособия, демонстрирующего применение алгоритма Дейкстры на практике.
Общие сведения о графах
алгоритм граф путь работоспособность
Граф G (рис.1.1) задается множеством точек (вершин) х1, х2,..., хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,...,аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение).
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй.
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Так, на рис. 1.2 путями являются последовательности дуг:
а6, а5, а9, а8, а4. (1)
а1, а6, а5, а9. (2)
а1, а6, а5, а9, а10, а6, а4. (3)
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза.
Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2).
Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер д1, д2,..., дq, в которой каждое ребро аi, за исключением первого и последнего ребер, связано с ребрами аi-1 и аi+1 своими концевыми вершинами.
В графе, изображенном на рис. 1.2, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х2, х5, х4, х3, х5, х6. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (д1, д2,..., дq), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.
Алгоритм Дейкстры
Алгоритм Дейкстры строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этого графа (если таковые имеются).
В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные.
Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.
Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:
1. Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
2. Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.
Алгоритм завершится, когда будут помечены все достижимые вершины.
В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.
Алгоритм, реализованный в программе
Задаются:
1. Матрица весов дуг W[i,j], веса дуг между вершинами i и j. Матрица симметричная и положительная. Если i и j не связаны дугой, то W[i,j]=-1
2. Начальная вершина x1
3. Конечная вершина х2
Рабочие данные:
1. Массив distance[i]. В нем будут хранится длины кратчайших путей из x1 в i.
2. Массив path[i]. В нем будет хранится шаг кратчайшего пути между i и х1.
3. front[i]=1, если вершина во фронте волны, 0 иначе
4. newfront[i] массив, где будет готовится новый фронт.
Начало.
1.Заполняется массив distance значениями 10000 (символизирует бесконечность).
2. front[x1]=1; остальные элементы 0
3. Обнуляем все элементы в newfront
Шаг алгоритма.
1. Ищем ненулевые элементы front[i]. Для каждого такого front[i] != 0 делаем шаг 1.1
1.1 Ищем смежные с i вершины, т.е. ищем неотрицательные элементы W[i,j].
Для таких элементов делаем шаги 1.1.1-1.1.2
1.1.1 newdist=distance[i]+W[i,j]
1.1.2 если newdist<distance[j], то делаем шаги 1.1.2.1-1.1.2.3
1.1.2.1 distance[j]=newdist - то есть до j вершины существует путь длины newdist
1.1.2.2 path[j]=i - то есть кратчайший путь в j лежит через вершину i
1.1.2.3 newfront[j]=1 - добавляем j вершину в новый фронт
2. Анализируем newfront.
2.1. Если newfront[x2]=1 (то есть в новом фронте присутствует конечная вершина), то путь найден и переходим к шагу 3
2.2. Если newfront[i]=0 для всех i то пути между x1 и х2 не существует, завершаем алгоритм.
2.3. Иначе для всех i front[i]=newfront[i]; newfront[i]=0; то есть обновляем фронт, и обнуляем новый фронт, и повторяем шаг 1.
3. Шаг 3. Распечатка пути. Видимо кратчайший путь из x1 в х2 найден.
Длина этого пути лежит в distance[x2].
Печатаем путь их х2 в х1:
t=x2;
while(t != x1)
{
print(x2);
t=path[t];
}
Получили распечатку кратчайшего пути из х2 в х1, для вывода результата этот путь записываем в обратном направлении.
ОСОБЕННОСТИ ПРОГРАММНОЙ РЕАЛИЗАЦИИ
Входные данные: матрица смежности, где нулями обозначены отсутствующие дуги, а числа - веса дуг соединяющих соответствующие вершины. Отрицательных весов быть не может. Матрица инцидентности задается в файле testdata.xls, откуда впоследствии программа их будет считывать. Ограничений на размер матрицы не накладывается.
Выполнение программы: алгоритм реализован в среде Matlab в виде функции deikstra(initialPoint, endPoint), которая в качестве аргументов принимает начальную и конечную точку для поиска кратчайшего пути между ними. Начальная и конечная точки задаются по номеру соответствующей вершины графа.
Анализ входных данных: так как отрицательные веса невозможны, то в самом начале программа анализирует введенные входные данные; при обнаружении отрицательного веса возвращает ошибку и завершает выполнение.
Результат: выводится в командное окно в виде столбца, в котором сверху вниз написаны номера вершин, через которые проходит кратчайший путь. При этом начальная и конечная точка также отображаются в этом столбце.
ПРИМЕР ИСПОЛЬЗОВАНИЯ ПРОГРАММНОЙ РЕАЛИЗАЦИИ
Пусть имеется ориентированный взвешенный граф на пяти вершинах. Его матрица смежности имеет вид:
Таблица 1. Матрица смежности.
|
вершина |
1 |
2 |
3 |
4 |
5 |
|
|
1 |
0 |
10 |
0 |
30 |
90 |
|
|
2 |
0 |
0 |
50 |
0 |
0 |
|
|
3 |
0 |
0 |
0 |
0 |
15 |
|
|
4 |
0 |
0 |
20 |
0 |
60 |
|
|
5 |
0 |
0 |
0 |
0 |
0 |
Необходимо найти кратчайший путь между вершинами 1 и 5.
1. Данная матрица смежности записывается в файл testdata.xls:
Рис. 2. Задание матрицы смежности.
2. В командном окне Matlab вызывается функция deikstra(1, 5), где в качестве аргументов указываются соответствующие номера начальной и конечной вершины:
Рис. 3. Вызов функции, реализующей алгоритм Дейкстры
3. На экран выводится результат:
Рис. 4. Вывод результата.
ЗАКЛЮЧЕНИЕ
В данной работе была изучена тема «Поиск кратчайшего пути в графе» на основе алгоритма Дейкстры. Для изучения работы данного алгоритма была написана соответствующая программа. Программа реализована в среде Matlab. Работоспособность написанной программы была проверена на тестовых примерах, один из которых приведен в работе.
Изученный алгоритм является достаточно простым в понимании и программной реализации.
Полученные результаты согласуются с теорией.
ЛИТЕРАТУРА
Статья в Интернете: http://www.tspu.tula.ru/ivt/old_site/umr/trpo/tasks/t13.htm
Размещено на Allbest.ru
Подобные документы
Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
курсовая работа [411,6 K], добавлен 25.04.2013Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.
курсовая работа [43,8 K], добавлен 19.10.2010Графы: определения, примеры, способы изображения. Смежные вершины и рёбра. Путь в ориентированном и взвешенном графе. Матрица смежности и иерархический список. Алгоритм Дейкстры - алгоритм поиска кратчайших путей в графе. Работа в программе "ProGraph".
презентация [383,8 K], добавлен 27.03.2011Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа [653,5 K], добавлен 18.02.2013Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.
курсовая работа [78,2 K], добавлен 24.09.2010Алгоритм поиска по первому наилучшему совпадению на графе. Основные классы для поиска пути в лабиринте. Тестирование нахождения кратчайшего пути в лабиринте. Порядок обхода вершин. Тестирование поведения программы при отсутствии пути в лабиринте.
курсовая работа [888,7 K], добавлен 19.12.2013Составление для водителей путевого листа, в котором отображается маршрут посещения городов по минимальному пути. Выбор языка программирования, алгоритма, типа данных и структуры программы. Города, обслуживаемые компанией. Спецификация переменных.
контрольная работа [134,2 K], добавлен 01.01.2014Разработка программы в среде Delphi для нахождения кратчайшего пути между стартом, лежащим в одной из вершин многоугольника, и финишем, находящимся на одной из сторон. Установка опорных точек, контроль целостности вводимых данных, методы решения задачи.
курсовая работа [778,8 K], добавлен 19.10.2010Разработка в среде Delphi программы "Поиск кратчайшего пути", которая создает лабиринт, находит кратчайший путь его прохождения и отображает его. Структура данных задачи и методы ее решения. Общая схема организации и взаимодействия модулей, их описание.
курсовая работа [86,5 K], добавлен 19.10.2010
