Поиск кратчайших путей в графе методом Дейкстры

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

2

1

ВОЕННАЯ АКАДЕМИЯ

ВОЙСКОВОЙ ПРОТИВОВОЗДУШНОЙ ОБОРОНЫ

ВООРУЖЁННЫХ СИЛ РОССИЙСКОЙ ФЕДЕРАЦИИ

им. МАРШАЛА СОВЕТСКОГО СОЮЗА А. М. ВАСИЛЕВСКОГО

факультет радиотехники и информационных технологий

кафедра естественнонаучных и математических дисциплин

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

Тема: Поиск кратчайших путей в графе методом Дейкстры

Студента

Майорова Никиты Валерьевича

Введение

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

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

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

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

* алгоритм Форда-Беллмана;

* алгоритм Шимбелла.

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

теория граф кратчайший алгоритм

1. Основные понятия теории графов

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

Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X , состоящее из n элементов (X = {1, 2,..., n}), называемых вершинами графа, и подмножество V декартова произведения, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X , V) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X). Дугу между вершинами i и j будем обозначать (i , j). Число дуг графа будем обозначать m (V = (v1, v2,..., vm)).

Рис.1

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

Приведем ряд примеров приложений теории графов.

* «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами - дороги (автомобильные, железные и др.) или другие транспортные (например, авиационные) маршруты. Другой пример - сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами - возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

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

Завершив краткое описание прикладных областей, вернемся к введению основных понятий теории графов.

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

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вер шинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.

Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вер шина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Граф, для которого из следует называется симметрическим. Если изследует, что то соответствующий граф называется антисимметрическим.

Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь - последовательность смежных вершин. Замкнутая цепь называется циклом. По аналогии с простым и элементарным путем, можно определить соответственно простые и элементарные цепь и цикл. Любой элементарный цикл является простым, обратное утверждение в общем случае неверно. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно - циклом, путем, кон туром). Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой цепью (соответственно - циклом, путем, контуром).

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Известно, что: связность графа не может быть больше, чем [2m /n], где [x] - целая часть числа x; существуют графы с n вершинами и m ребрами, имеющие связность [2m /n]; в сильно связном графе через любые две вершины проходит контур.

Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом.

В неориентированном графе степенью вершины i называется число d_i инцидентных ей ребер. Очевидно, d_j < n - l , i eX . Граф, степени всех вершин которого равны n - 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Вершина, для которой не существует инцидентных ей ребер (d_i = 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро (d_i = 1) называется висячей.

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

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны (теорема Эйлера). Обозначим щ -- число вершин, имеющих степень k, k = 0, 1, 2,... . Известно, что:

Для ориентированных графов для каждой вершины можно ввести два числа - полустепень исхода[число выходящих из нее вершин) и полустепень захода d [ (число входящих в нее вершин). В дальнейшем, если не оговорено особо, будем рассматривать графы без петель, то есть без дуг, у которых начальная и конечная вершины совпадают. Известно, что: эйлеров граф является объединением контуров, попарно не имеющих общих ребер.

Определим матрицу смежности графа как квадратную матрицу n хп, элемент a которой равен единице, еслинулю, если

Для неориентированного графа матрица смежности всегда симметрическая.

Определим матрицу инциденций для ребер графа как прямо угольную матрицу n х m, элемент Гц которой равен единице, если вершина i инцидентна ребру j , и нулю в противном случае,

Аналогично определяется матрица инциденций для дуг графа - как прямоугольная матрицу m хп, элемент Гц которой равен плюс единице, если дуга U_j исходит из вершины i , минус единице, если дуга Ц заходит в вершину i , и нулю в остальных случаях,

Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m=n-1, а число висячих вершин равно

Легко показать, что в дереве любые две вершины связаны единственной цепью.

Прадеревом называется ориентированное дерево, у которого одна из вершин, называемая корнем, не имеет заходящих дуг, а степени захода остальных вершин равны единице.

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

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

Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G * , определяемый следующим образом: каждой грани графа G соответствует вершина графа G *, каждому ребру V графа G , являющемуся граничным для граней z1 и z2 , соответствует ребро V * графа G *, соединяющее соответствующие граням z1 и z2 вершины. Понятие двойственного графа тесно связано с понятием двойственности в линейном программировании.

2. Методы определения кратчатчайших путей в графе

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опираются на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов A[u, v], u,vV, вычисляются некоторые верхние ограничения D[u] на расстоянии от s до всех вершин vV. Каждый раз, когда мы устанавливаем, что

D[u] + A[u, v] < D[v], (1)

оценку D[u] улучшаем:

D[u] = D[u] + A[u, v].

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко можно показать, что значение каждой из переменных D[u] тогда равно d(s,u) - расстоянию от s до v. Заметим, что для того, чтобы определить расстояние от s до t, мы вычисляем расстояния от s до всех вершин графа. На данный момент не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.

Описанная общая схема является не полной, так как она не определяется очередности, в которой выбираются вершины u и v для проверки условия (1). Эта очередность оказывает очень сильное влияние на эффективность алгоритма. Далее изучим более детально методы нахождения расстояния от фиксированной вершины, называемой источником, которую будем обозначать через s, до всех остальных вершин графа.

Рассмотрим алгоритм Форда-Беллмана

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

Заметим, что всякий кратчайший путь - это простая цепь, поэтому в любом кратчайшем пути в графе G с множеством вершин {s, v₁, v₂,…, v_n} не более n дуг.

Обозначим через d^?k(v_i) - длину пути от вершины s до вершины v_i, кратчайшего из всех путей от s до v_i, в которых не более k дуг. Тогда

d¹(v_i) = (2)

d^k+1(v_i)= (d ^k(v_i); d ^k(v_j) + l(v_j, v_i)) (3)

Здесь d ^k(v_j) + l(v_j, v_i) - это длина пути до вершины v_i, предпоследней вершина которого - v_j. Причём путь до v_j - кратчайший из всех путей до этой вершины, в которой не более чем k дуг.

Зная числа d¹(v_i), i = 1, 2,…, n, можно шаг за шагом рассчитать числа d²(v_i),…d ⁿ(v_i), i=1, 2,…,n. Если задача о кратчайшем пути имеет решение, величины d ⁿ(v_i), i= 1, 2,…, n. - это заведомо длины кратчайших путей от вершины s до вершин v₁, v₂,…, v_n.

Чтобы определить, если в графе G контур отрицательной длины, нужно рассчитать числа d ⁿ⁺¹(v_i), i= 1, 2,…, n. Если окажется, что в хотя бы одно число из этих чисел меньше соответствующего значения предыдущего шага, в графе есть контур отрицательной длины: путь от вершины s до некоторой вершины v, содержащий n+1 дугу, оказался короче пути от s до v, состоящего из n дуг.

Алгоритм может окончить работу быстрее, чем за n шагов. Не обязательно, чтобы в графе существовали кратчайшие пути, содержащие n дуг. Если все числа d^k+1(v_i), i= 1, 2,…, n, найденные на k+1 шаге, совпадают с соответствующими величинами, определенными на k-ом шаге, то кратчайшие пути найдены, а максимальное число дуг в кратчайших путях равно k.

Рассмотрим реализацию этого алгоритма на примере.

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

Рис. 2

В этом графе содержатся дуги отрицательных длин. Результаты будем заносить в таблицу 1, где столбцы соответствуют вершинам графа, а в k-ой строке будем записывать числа d^k(v_i), i= 1, 2,…, n. Первый столбец соответствует вершине s (вершине 1), он содержит одни нули.

Таблица 1

	1	2	3	4	5	6	7	8	9
1	0	6	?	2	7	?	?	?	?
2	0	5	9	2	7	2	3	8	11
3	0	5	7	2	5	1	3	3	6
4	0	5	6	2	2	1	3	2	1
5	0	5	4	2	1	1	3	2	0
6	0	5	3	2	1	1	3	2	0
7	0	5	3	2	1	1	3	2	0

На первом шаге найдём пути из вершины 1 до вершин 2, 4, 5. Значит, пути, состоящие не более чем из двух дуг, следует искать только до вершин, в которых входят дуги, выходящие из вершин 2, 4, 5 (рисунок 3).

Рис. 3

Над кружками с номерами вершин на рисунке 2 стоят длины путей до этих вершин, найденные на предыдущем шаге. Найдём пути в другие вершины из вершин 2, 4, 5:

d²(2) = min(6;2+3;7+5) = 5,

d²(3) = min(?;6+4;7+2) = 9,

d²(4) = min(2;6+3;7+8) = 2,

d²(5) = min(7;6+6;2+8) = 7,

d²(6) = min(?;6+(-4);7+3) = 2,

d²(7) = min(?;2+1;7+5) = 3,

d²(8) = min(?;2+6) = 8,

d²(9) = min(?;7+4) =11,

и заполним вторую строку таблицы.

Уменьшились длины путей до вершин 2, 3, 6, 7, 8, 9. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги перечисленных вершин (рисунок 4):

Рис. 4

d³(2) = min(5;9+4) = 5,

d³(3) = min(9;5+4;2+5) = 7,

d³(4) = min(2;5+3;3+1;8+6) = 2,

d³(5) = min(7;5+5;9+2;2+3;3+5;8+(-1);11+4) = 5,

d³(6) = min(2;9+5;5+(-4);8+1;11+4) = 5,

d³(7) = min(2;9+5;5+(-4);8+1;11+7) = 1,

d³(8) = min(8;2+1;3+3) = 3,

d³(9) = min(11;8+(-2);2+7) = 6.

Заполняем третью строку таблицы. На третьем шаге уменьшились длины путей до вершин 3, 5, 6, 7, 8, 9. Постараемся найти более короткие пути до тех вершин графа, в которые входят дуги, выходящие из перечисленных вершин:

Рис. 5

d⁴ (2) = min(5;7+4;5+5) = 5,

d⁴ (3) = min(7;5+2;1+5) = 6,

d⁴ (5) = min(5;7+2;1+3;3+(-1);6+4) = 2,

d⁴ (6) = min(1;7+5;5+3;3+1;6+7) = 1,

d⁴ (7) = min(3;5+5;3+3) = 3,

d⁴ (8) = min(3;1+1) = 2,

d⁴ (9) = min(6;5+4;1+7;3+(-2)) = 1.

Заполняем четвертую строку таблицы. Уменьшились длины путей до вершин 3, 5, 8, 9. Продолжаем действовать по алгоритму Беллмана (рисунок 6):

Рис. 6

d⁵ (2) = min(5;6+4;2+5) = 5,

d⁵ (3) = min(6;2+2) = 4,

d⁵ (4) = min(2;2+8;2+6) = 2,

d⁵ (5) = min(2;6+2;2+(-1);1+4) = 1,

d⁵ (6) = min(1;6+5;2+3;2+1;1+7) = 1,

d⁵ (7) = min(3;2+5;2+3) = 3,

d⁵ (8) = min(1;2+4;2+(-2)) = 0.

Заполняем пятую строку таблицы. Уменьшились длины путей до вершин 3, 5, 9. Следовательно, нужно перечислить длины путей до вершин 2, 3, 4, 5, 6, 7, 9:

d⁶ (2) = min(5;6+4;2+5) = 5,

d⁶ (3) = min(4;1+2) = 3,

d⁶ (4) = min(2;1+8) = 2,

d⁶ (5) = min(1;4+2;0+4) = 1,

d⁶ (6) = min(1;1+5;4+5;0+7) = 1,

d⁶ (7) = min(3;1+5) = 3,

d⁶ (9) = min(0;1+4) = 0.

Заполняем шестую строку таблицы. Уменьшилась длина пути до вершины 3. Нужно пересчитать длины путей до вершин 2, 5, 6:

d⁷ (2) = min(5;3+4) = 5,

d⁷ (5) = min(1;3+2) = 1,

d⁷ (6) = min(1;3+5) = 1.

Заполняем седьмую строку таблицы. Длины седьмой строки повторяют длины шестой строки. Кратчайшие пути найдены и среди них есть пути, состоящие из шести дуг. Построим дерево кратчайших путей (рисунок 7).

Рис. 7

Длина кратчайшего пути до вершины 4 была найдена уже в первой строке. Значит, этот путь состоит из одной дуги. Включаем в дерево дугу (1,4). Во второй строке стоят длины кратчайших путей по вершин 2 и 7. Следовательно, эти пути включают в себя две дуги. Из расчётов (и диаграммы) вытекает, что предпоследняя вершина кратчайшего пути как до вершины 2, так и до вершины 7 - это вершина 4. В дерево кратчайших путей добавляем дуги (4.2) и (4,7).

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

Теперь рассмотрим случай, когда алгоритм обнаруживает контур отрицательной длины. На рисунке 7 изображен граф, для которого задача о кратчайшем пути не имеете решения из-за присутствия контура 2 - 3 - 4 - 2 длины -1.

Рис. 8

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

Таблица 2

	1	2	3	4
1	0	3	?	4
2	0	3	6	4
3	0	3	6	1
4	0	2	6	1

В четвертой строке таблицы 2 уменьшилась длина пути до второй вершины. Путь из четырех дуг 1 - 2 - 3 - 4 - 2 оказался короче пути из одной дуги (1,2). Алгоритм обнаружил в графе контур отрицательной длины.

Рассмотрим метод нахождения кратчайших (или максимальных) путей, предложенный Шимбеллом. Для этого введём специальные операции над элементами матрицы смежности вершин, позволяющие находить кратчайшие или максимальные пути между вершинами, состоящие из заданного количества ребер. Эти операции таковы:

1) операция умножения двух величин a и b при возведении матрицы в степень соответствует алгебраической сумме, то есть

2) операция сложения двух величин a и b заменяется выбором из этих величин минимального (максимального) элемента, то есть нули при этом игнорируются.

, (4)

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

Аналогично определяются элементы k-ой степени матрицы A. Рассмотрим пример. Составим для графа, изображенного на рисунке 9, матрицу смежности.

Рис. 9

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

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

и так далее. Например, длина кратчайшего пути из трех ребер из вершины D в вершину С равна 7. Это путь D - B - A - C.

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

Алгоритм Демйкстры (Dijkstra's algorithm) -- алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях.

Примеры

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

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

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

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

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

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

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

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых 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, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 -- вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояние до 2-ой вершины и расстояния между вершинами 2 и 4, то есть 22 (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

Псевдокод

Присвоим

Для всех отличных от a

присвоим

Пока

Пусть -- вершина с минимальным d[v]

Для всех таких, что

если d[u] > d[v] + w[vu] то

изменим

изменим

Описание

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

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

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

Доказательство корректности.

Пусть l(v) -- длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z).База. Первой посещается вершина a. В этот момент d(a)=l(a)=0.Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P -- кратчайший путь из a в z, y -- первая непосещённая вершина на P, x -- предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.

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

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

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

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

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

Альтернативами им служат толстые кучи, тонкие кучи и кучи Бродала, обладающие теми же асимптотическими оценками, но меньшими константами.

4. РЕШЕНИЕ ЗАДАЧ ПРАКТИЧЕСКОЙ ЧАСТИ

Задание №1.

По заданной матрице весов Щ графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины t = x₆ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами.

Решение:

В вершину	2	3	4	5	6
Длина пути	6	9	13	12	?
Из вершины	1	1	1	1	1
В вершину	2	3	4	5	6
Длина пути	6	11	15	12	?
Из вершины	1	2	2	2	1
В вершину	2	3	4	5	6
Длина пути	6	11	17	12	26
Из вершины	1	2	3	2	3
В вершину	2	3	4	5	6
Длина пути	6	11	17	12	20
Из вершины	1	2	3	2	5
В вершину	2	3	4	5	6
Длина пути	6	11	15	23	26
Из вершины	1	2	2	4	4

Кратчайший путь из вершины s = x₁ в вершину s = x₆ будет проходить по маршруту x₁ > x₂ > x₅ > x₆ и иметь длину 20.

Решение:

В вершину	2	3	4	5	6
Длина пути	6	9	13	12	?
Из вершины	1	1	1	1	1
В вершину	2	3	4	5	6
Длина пути	6	9	13	21	22
Из вершины	1	1	1	4	4
В вершину	2	3	4	5	6
Длина пути	6	11	13	12	22
Из вершины	1	2	1	2	4
В вершину	2	3	4	5	6
Длина пути	6	11	13	12	20
Из вершины	1	2	1	2	5
В вершину	2	3	4	5	6
Длина пути	6	11	13	12	26
Из вершины	1	2	1	2	3

Максимальный путь из вершины s = x₁ в вершину s = x₆ будет проходить по маршруту x₁ > x₂ > x₃ > x₆ и иметь длину 26.

Задание №2

По заданной матрице весов Щ графа G найти величину минимального пути и сам путь от вершины s = x₁ до вершины t = x₇ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами.



Решение:

В вершину	2	3	4	5	6	7
Длина пути	?	9	?	?	?	?
Из вершины	1	1	1	1	1	1
В вершину	2	3	4	5	6	7
Длина пути	13	9	12	15	16	?
Из вершины	3	1	3	3	3	1
В вершину	2	3	4	5	6	7
Длина пути	13	9	12	15	16	17
Из вершины	3	1	3	3	3	4
В вершину	2	3	4	5	6	7
Длина пути	13	9	12	15	16	17
Из вершины	3	1	3	3	3	4
В вершину	2	3	4	5	6	7
Длина пути	13	9	24	18	26	17
Из вершины	3	1	2	2	2	4
В вершину	2	3	4	5	6	7
Длина пути	13	9	24	18	23	37
Из вершины	3	1	2	2	5	5

Кратчайший путь из вершины s = x₁ в вершину s = x₆ будет проходить по маршруту x₁ > x₃ > x₄> x₇ и иметь длину 17.

Решение:

В вершину	2	3	4	5	6	7
Длина пути	?	9	?	?	?	?
Из вершины	1	1	1	1	1	1
В вершину	2	3	4	5	6	7
Длина пути	13	9	12	15	16	?
Из вершины	3	1	3	3	3	1
В вершину	2	3	4	5	6	7
Длина пути	13	9	12	15	16	20
Из вершины	3	1	3	3	3	6
В вершину	2	3	4	5	6	7
Длина пути	13	9	24	18	16	20
Из вершины	3	1	2	2	3	6
В вершину	2	3	4	5	6	7
Длина пути	13	9	24	18	16	29
Из вершины	3	1	2	2	3	4
В вершину	2	3	4	5	6	7
Длина пути	13	9	24	15	16	32
Из вершины	3	1	2	3	3	5

Максимальный путь из вершины s = x₁ в вершину s = x₇ будет проходить по маршруту x₁ > x₃ > x₅ > x₇ и иметь длину 32.

Выводы

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

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

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

Заключение

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

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

Литература

1. Ревчук И.Н., Пчельник В.К. Прикладная математика. ГрГУ им. Я. Купалы, 2007.

2. Белов В.В. и др. Теория графов. М., Высшая школа, 1976.

3. Липский В. Комбинаторика для программистов. М., Наука, 1989.

4. Харари Ф. Теория графов. М., Мир, 1973.

5. Шапорев С.Д. Дискретная математика. СПб., БХВ-Петербург, 2007.

6. Галкина В.А. Дискретная математика: комбинаторные методы оптимизации. М., Гелиос АРВ, 2003.

7. Вотяков А.А., Фридман А.А., Литвак Б.Г., Исследования по дискретной математике: Сборник статей. М.: Наука, 1973.

8. Басакер Р., Саати Т., Конечные графы и сети, М., Наука, 1974.

9. Уилсон Р., Введение в теорию графов, М., Мир, 1977. 17. Харрари Ф., Теория графов, М., Мир, 1973.

10. Берж К., Теория графов и ее применения, М., ИЛ,1962

11. Оре О., Теория графов, М., Наука, 1968.

12. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.

Размещено на Allbest