Метод Дейкстры нахождения кратчайшей цепи в связанном графе

Глава 1. Теоретическая часть

1.1 Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг

1.2 Задача с методическим описанием

1.3 Алгоритмизация задачи

Глава 2. Практическая часть

Задание 1

Задание 2

Задание 3

Задание 4

Задание 5

Задание 6

Задание 7

Задание 8

Заключение

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

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

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

Глава 1. Теоретическая часть

1.1 Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг

Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[c_ij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sX до заданной конечной вершины tX, при условии, что такой путь существует, т. е. при условии tR (s). Здесь R (s) — множество, достижимое из вершины s. Элементы c_ij матрицы весов C могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл Ф все же существует и x_i — некоторая его вершина, то, двигаясь от s к x_i, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует.

Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между s и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t. Это можно усмотреть из следующего факта. Если из каждого элемента c_ij матрицы весов C вычесть достаточно большое число L, то получится новая матрица весов C'=[c_ij'], все элементы c_ij' которой отрицательны. Тогда кратчайший путь от s к t — с исключением отрицательных циклов — необходимо будет гамильтоновым, т. е. проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постоянную величину (n-1)ЧL, то кратчайший путь (простая цепь) от s к t с матрицей C' будет кратчайшим гамильтоновым путем от s к t при первоначальной матрице C. Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути. Поэтому мы будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

Следующие задачи являются непосредственными обобщениями сформулированной выше задачи о кратчайшем пути.

1) Для заданной начальной вершины s найти кратчайшие пути между t и всеми другими вершинами x_iX.

2) Найти кратчайшие пути между всеми парами вершин.

Частные случаи, когда все c_ij неотрицательны, встречаются на практике довольно часто (например, когда c_ij являются расстояниями), так что рассмотрение этих специальных алгоритмов оправдано. Мы будем предполагать, что матрица не удовлетворяет, вообще говоря, условию треугольника, т. е. не обязательно для всех. В противном случае кратчайший путь между x_j и x_j состоит из одной единственной (x_j x_j) дуги, если такая дуга существует, и задача становится тривиальной. Если в графе G дуга (x_j x_j) отсутствует, то ее вес полагается равным .

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

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

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

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

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

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

Пусть l (x_i) — пометка вершины x_i.

Присвоение начальных значений

Шаг 1. Положить и считать эту пометку постоянной. Положить для всех x_is и считать эти пометки временными. Положить p=s.

Обновление пометок

Шаг 2. Для всех, пометки которых временные, изменить пометки в соответствии со следующим выражением:

.

Превращение пометки в постоянную

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой

.

Шаг 4. Считать пометку вершины x_i* постоянной и положить p= x_i*.

Шаг 5. (1) (Если надо найти лишь путь от s к t.)

Если p=t, то l (p) является длиной кратчайшего пути. Останов.

Если pt, перейти к шагу 2.

(Если требуется найти пути от s ко всем остальным вершинам.)

Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов.

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

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S₁ — множество вершин с этими пометками, а S₂ — множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l (x_i) дает кратчайший путь от s к x_i, проходящий полностью по вершинам множества S₁. (Так как при каждой итерации во множество S₁ включается только одна вершина, то обновление пометки l (x_i) требует только одного сравнения на шаге 2.)

Пусть кратчайший путь от s к x_i* не проходит целиком по S₁ и содержит по крайней мере одну вершину из S₂, и пусть x_jS₂ — первая такая вершина в этом пути. Так как по предположению c_ij неотрицательны, то часть пути от x_j к x_i* должна иметь неотрицательный вес и. Это, однако, противоречит утверждению, что l (x_i*) — наименьшая временная пометка, и, следовательно, кратчайший путь к x_i* проходит полностью по вершинам множества S₁, и поэтому l (x_i*) является его длиной.

Так как вначале множество S₁ равно (s) при каждой итерации к S₁ добавляется x_i*, то предположение, что l (x_i*) равно длине кратчайшего пути x_iS₁, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

Если требуется найти кратчайшие пути между s и всеми другими вершинами полного связного графа с n вершинами, то в процессе работы алгоритма выполняются операций сложения и сравнения на шаге 2 и еще операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины временные, а для этого нужно еще операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами s и t. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку.

Как только длины кратчайших путей от s будут найдены (они будут заключительными значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения (*). Так как вершина x_i' непосредственно предшествует вершине x_i в кратчайшем пути от s к x_i, то для любой вершины x_i соответствующую вершину x_i' можно найти как одну из оставшихся вершин, для которой

''. (*)

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

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти кратчайшие расстояния от 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.

1.2 Задача с методическим описанием

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

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа.

Неориентированное ребро будем рассматривать как пару противоположно ориентированных дуг равного веса. Воспользуемся алгоритмом Дейкстры. Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.

Алгоритм работает так:

Шаг 1.

.

Первая итерация

Шаг 2. — все пометки временные.

; ;

;

Шаг 3. соответствует x₇.

Шаг 4. x₇ получает постоянную пометку l (x₇)=3⁺, p=x₇.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Вторая итерация

Шаг 2.- все пометки временные.

; ;

;

Шаг 3. соответствует x₂.

Шаг 4. x₂ получает постоянную пометку l (x₂)=5⁺, p=x₂.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Третья итерация

Шаг 2. — только вершины x₃ и x₉ имеют временные пометки.

;

Шаг 3. соответствует x₈.

Шаг 4. x₈ получает постоянную пометку l (x₈)=6⁺, p=x₈.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Четвертая итерация

Шаг 2. — только вершины x₅, x₆ и x₉ имеют временные пометки.

; ;

Шаг 3. соответствует x₄.

Шаг 4. x₄ получает постоянную пометку l (x₄)=7⁺, p=x₄.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Пятая итерация

Шаг 2. — только вершины x₅, x₆ и x₃ имеют временные пометки.

; ;

Шаг 3. соответствует x₉.

Шаг 4. x₉ получает постоянную пометку l (x₉)=11⁺, p=x₉.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шестая итерация

Шаг 2. — только вершина x₆ имеет временную пометку.

Шаг 3. соответствует x₅.

Шаг 4. x₅ получает постоянную пометку l (x₅)=12⁺, p=x₅.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Седьмая итерация

Шаг 2. — только вершина x₆ имеет временную пометку.

Шаг 3. соответствует x₆.

Шаг 4. x₆ получает постоянную пометку l (x₅)=17⁺, p=x₆.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Восьмая итерация

Шаг 2. — только вершина x₃ имеет временную пометку.

Шаг 3. x₃ получает постоянную пометку l (x₃)=23⁺.

1.3 Алгоритмизация задачи

1) Вводим количество вершин неориентированного графа.

2) Если количество вершин больше 5, то переходим к пункту 3; иначе переходим к пункту 4.

3) Генератором случайных чисел произвольно задаются связи между вершинами в матрице смежностей, переходим к пункту 5.

4) Вводим связи между вершинами, исходя из следующего условия:

если не существует пути длиной в одно ребро из одной вершины в другую, то ставим «100»,

если существует путь между двумя вершинами, то ставим произвольное положительное ненулевое значение веса дуги.

Все введенные данные заносятся в матрицу смежностей.

5) Вводим номера вершин, путь между которыми нужно найти.

6) Задаем начальные значения длин путей равных 100 (в программе это обозначает бесконечность), а пометки всех вершин обнуляем.

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

8) Измененяем длины путей между вершинами «i» и начальной при условии, что рассматриваемая дуга не идет из вершины в саму себя и пометка этой вершины равна нулю, то тогда:

а) просматриваем длину пути в вершину «i» и сравниваем с длиной пути из начальной вершины «Nac»

б) получаем, что длина пути из вершины «s» меньше начального значения пути в вершину «i», то запоминаем в T[i]-ом элементе новую длину пути (меньшую) и H[i]-му присваиваем значение «s».

9) Присваиваем переменной `t" значение 100 (бесконечность), а переменной для хранения текущей вершины «k» присваиваем значение нуль.

10) Производим попытку уменьшить длину пути. Если вершина не помечена (ее пометка равна нулю), то если длина пути меньше значения «t» то значению «t» присваиваем текущее значение пути, а переменной для хранения текущей вершины «k» даем значение этой переменной.

11) Если переменная для хранения текущей вершины имеет значение нуля, то пути нет, переходим к пункту 14, иначе переходим к пункту 12.

12) Если переменная для хранения текущей вершины имеет значение конечной вершины, то путь найден, он кратчайший, переходим к пункту 14, иначе переходим к пункту 13.

13) Пометку на вершину, которую хранит переменная «k», изменяем на единицу и переходим к пункту 8.

14) Выводим на экран сообщение о длине пути между вершинами, если такой путь существует (т.е. путь имеет неотрицательную длину).

Экранная форма интерфейса и инструкция пользователя

Пункты меню:

1. Алгоритм реализации поставленной задачи.

2. Изображение исходного графа.

3. Выход из программы.

Для выбора пункта необходимо нажать на соответствующую клавишу:

если это пункт 1, то нажмите «A» или «a»;

если это пункт 2, то нажмите «D» или «d»;

если это пункт 3, то нажмите «E» или «e».

Глава 2. Практическая часть

Задание 1

Доказать тождество

При решении используем свойства дистрибутивности, двойного отрицания и закона де Моргана:

= (АХ)(ВХ)=(АХ)(ВХ)=

=(АХ)(ВХ)= (АХ)(ВХ)=(АХ)(ВХ)

Задание 2

Определить свойства отношения:

R=(x,y).

1.1 R-рефлексивно, т.к. для всех (х, х) х=х верно;

1.2 R-симметрично, х=у, следовательно у=х — верно;

1.3 R-транзитивно, х=у, у=z и х=z

Задание 3

Для отношения, заданного матрицей, определить является ли оно отношением эквивалентности. Если является, то определить класс эквивалентности.

Приведем матрицу отношения R к блочно-диагональному виду: переставим местами столбцы и строки. Поменяем местами строки и столбцы b и f:

Классы эквивалентности: К1={a, f}, К2= {c, d, e}, К3={b}.

Отношение является отношением эквивалентности.

Задание 4

Для графа построить матрицу смежности, матрицу инцидентности; получить матрицу достижимостей; найти сильные компоненты и построит граф конденсации.

Матрица смежности определяется следующим образом:

1, если вершины Хi и Хj смежны,

Aij = 0 — в противном случае Матрица смежности для графа G:

Матрицей инцидентности для графа называется матрица n х m B= {b ij} n х m, элементы которой определяются:

1, если Хi — начальная вершина дуги Vj,

b ij = -1, если Хi — конечная вершина дуги Vj,

0, если Хi не инцидентна Vj

Матрица инцидентности графа G:

Матрицей достижимостей R= {r ij} n х n графа называется матрица, элементы корой определяются:

r ij= 1, если вершина достижима из Хi,

0 в противном случае

(I) СК: RQ={x1,x2,x3,x5,x6,x7}, т. к

R (x1)={ x1, x2,x3,x5,x6,x7},

Q (x1)={ x1, x2,x3,x4,x5,x6,x7}

(II) CK: R (x4)={ x1, x2,x3,x4,x5,x6,x7}

Q (x4)={4} RQ=(x4)

Граф конденсации:

x2=(x4)

x1={ x1, x2,x3,x4,x5,x6,x7}.

Задание 5

Упростить ПФ, используя равносильные преобразования:

((ХУ)Х)(Х (ХУ))=[(ХУ)Х][Х (ХУ)]=

=[(ХУ) Х] [Х (ХУ)=[ХУХ] [Х (ХУ)]=

=(ХХУ) (ХХ) (ХУ)=(ХУ) (ХУ)=Х (УУ)=Х

Задание 6

Составить таблицу истинности ПФ и определить тип ПФ.

Составим таблицу истинности:

Данная ПФ является тождественно-истинной, т. к все значения переменных равны 1.

Задание 7

Привести ПФ к нормальным и совершенным нормальным формам.

Т.к. ПФ тождественно истинна, то она имеет СДНФ и представляется в виде:

СДНФ: ХУХУХУХУ Х (ХУ)=Х (ХУ)=Х (ХУ)=1У=1

ПФ тождественно истинная, то она не имеет СКНФ, причем единственную.

Функция, которая принимает два значения 0 или 1 и аргументы которой принимают эти же значения, называется булевой функцией.

Задание 8

Исследовать систему булевых функций на полноту.

Для полноты системы необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один «минус». Составим таблицу Поста:

К: 001, не сохраняют 0 К, К1: 111, сохраняют 1 К1

Км: ХУ, не монотонные функции, т. к Км (класс монотонных функций)

(1,0)(0,0), (10)(00) Км Кл (класс линейных функций). Построим многочлен Жегалкина:

ХУ=ХУ=ХУ=1+(Х (1+У))=1+Х+ХУКл, 0Кл, Кс (класс самодвойственных функций):

Ксf (Х, У)=f (Х, У)=ХУ=ХУ=ХУХУ Кс

0:f=f=0=10 0Кс Таблица Поста показывает, что система булевых функций является полной.

Заключение

В соответствии с поставленной задачей в курсовой работе было выполнено следующее:

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

2) Решена задача по изученной теме с методическим описанием.

3) Разработан и реализован в виде программы алгоритм по изученной теме. Разработан программный интерфейс.

В практической части курсовой работы проведены решения и доказательства.

1. Аттетков А. В., Галкин С. В., Зарубин В. С. Методы оптимизации. — М.: Издательство МГТУ им. Н. Э. Баумана, 2001. — 440 с.

2. Берж К. Теория графов и ее применение. — М.: Мир, 1962. — 512 с.

3. Глаголев В. В. Методы дискретной математики. — Тула: ТулГУ, 2000. — 232 с.

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

5. Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974. — 457 с.

6. Новиков Ф. А. Дискретная математика для программистов — СПб.: Питер, 2002 год.

7. Немнюгин С. А. Turbo Pascal: практикум — СПб.: Питер, 2002 год.